解对称带状Toeplitz矩阵特征值问题的一种并行算法

A Parallel Algorithm for Solving the Eigenvalue Problem of Symmetric Band Toeplitz Matrices

提出了解对称带状Ｔｏｅｐｌｉｔｚ矩阵特征值问题的一种新的并行算法。该算法首先将Ｔｏｅｐｌｉｔｚ矩阵嵌入到一个更高阶的对称循环矩阵，得到对称循环矩阵的特征值之后，采用二分法计算Ｔｏｅｐｌｉｔｚ矩阵特征值。新算法的计算复杂性为Ｏ（ｒ２ｎ２／ｐ），其中ｎ是矩阵维数，ｒ是半带宽，ｐ为处理机台数，并行加速比为Ｏ（ｐ）。文中给出了数值实验的结果。

Abstract A parallel algorithm for solving the eigenvalue problem of symmetric band Toeplitz matrices is presented. The first step of our algorithm is to embed the Toeplitz matrix in a symmetric circulant matrix of high order. After computing the eigenvalues of the circulant matrix, the Toeplitz eigenvalue problem is solved by applying the bisection method. The computational complexity of the parallel algorithm in this paper is O(r 2n 2/p) , where n is the dimension of the matrix, r is the semi bandwidth, p is the number of processors. The parallel speedup is O(p) . Numerical results are also presented in this paper.