g-r循环矩阵求逆的快速算法和并行算法

Fast and Parallel Algorithms for g-r Circulant Matrices

借助于快速付立叶变换(FFT),给出了n阶g-r循环矩阵求逆的快速算法,该算法的计算复杂性为O(nlogn)+(g+1)n,且具有很好的并行性,若使用n台处理机并行处理该算法,则只需要O(nlogn)+(g+1)n步。

g-r circulant matrix is considered in this paper. Basing on the fast Fourier transform （FFT）, a fast algorithm for inverting such matrices is presented .The cost of the algorithm is only Olog （n log n）＋ （g＋1）n operations. Ifn processors are available, Olog（n log n）＋（g＋1）n steps are sufficient.