A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices

作者：Coakley Ed S^*; Rokhlin Vladimir

来源：Applied and Computational Harmonic Analysis, 2013, 34(3): 379-414.

DOI：10.1016/j.acha.2012.06.003

• Tridiagonal
• Symmetric eigenproblem
• Fast multipole method

We propose a new fast algorithm for computing the spectrum of an N x N symmetric tridiagonal matrix in 0 (N ln N) operations. Such an algorithm may be combined with any of the existing methods for the determination of eigenvectors of a symmetric tridiagonal matrix with known eigenvalues. The underlying technique is a divide-and-conquer approach which determines eigenvalues of a larger tridiagonal matrix from those of constituent matrices by the use of relations of their characteristic polynomials. The evaluation of characteristic polynomials is accelerated by the use of a technique known as the fast multipole method. An implementation of the algorithm has been developed in FORTRAN, providing for a comparison with existing techniques in terms of running time and accuracy. We present numerical results which demonstrate the effectiveness of the method.

• 出版日期2013-5