对称r-循环矩阵的快速算法和并行算法

Fast and parallel algorithms for symmetric r-circulant matrices

借助于快速付立叶变换(FFT),给出了一种判断对称r-循环线性系统是否有解的快速算法,并且在有解的情况下求出其解,该算法的计算复杂度为O(nlogn),且具有很好的并行性,若使用n台处理机并行处理该算法则只需要O(logn)步.当r=0时,对称r-循环矩阵变成一个上三角型Hankel矩阵,我们也给出了此类矩阵求逆的一种算法.最后将该算法推广到线性同余系统,其运算量仅为O(nlogn).

Symmetric r-circulant matrix linear systems is considered in this paper. Basing on the fast Fourier transform （FFT） ,a fast algorithm for determining whether such a system is solvable or not is presented and its solutions are found if it is solvable. The cost of the algorithm is only O（nlogn ） operations. If n processors are available, O（logn） steps are sufficient. When r is zero, symmetric r -circulant matrices become upper triangular Hankel matrices. A algorithm for inverting such matrices is presented. Finally, A method is given to turn such a system into n linear congruences with only one variable for each at the cost of O（nlogn） operations.