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

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

作　　者：罗晓广[1,2] 李晓梅[1,2] 

机构地区：[1]国防科技大学计算机系 [2]总装部指挥技术学院

出　　处：《工程数学学报》1999年第1期105-110,共6页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金;国防预研基金

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

关 键 词：并行算法 TOEPLITZ矩阵 矩阵 特征值问题 

分 类 号：O241.6[理学—计算数学]