zbMATH — the first resource for mathematics

New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem. (English) Zbl 1413.65099
Summary: In this paper, two accelerated divide-and-conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost $$O(N^2r)$$ flops in the worst case, where $$N$$ is the dimension of the matrix and $$r$$ is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy-like matrices and are off-diagonally low-rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low-rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off-diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations.

MSC:
 65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Software:
Algorithm 880; LAPACK; PAPI; VTune
Full Text:
References:
 [1] Golub, Matrix Computations (1996) [2] Parlett, The Symmetric Eigenvalue Problem (1998) · Zbl 0885.65039 · doi:10.1137/1.9781611971163 [3] Dhillon, Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices, Linear Algebra and its Applications 387 pp 1– (2004) · Zbl 1055.65048 · doi:10.1016/j.laa.2003.12.028 [4] Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numerische Mathematik 36 pp 177– (1981) · Zbl 0431.65022 · doi:10.1007/BF01396757 [5] Gu, A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM Journal on Matrix Analysis and Applications 16 pp 172– (1995) · Zbl 0815.65050 · doi:10.1137/S0895479892241287 [6] Demmel J Marques O Parlett B Vömel C Performance and accuracy of LAPACK’s symmetric tridiagonal eigensolvers Technical Report Knoxville 2007 · Zbl 1165.65014 [7] Demmel, Applied Numerical Linear Algebra (1997) · doi:10.1137/1.9781611971446 [8] Tisseur, A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures, SIAM Journal on Scientific Computing 20 pp 2223– (1999) · Zbl 0939.65058 · doi:10.1137/S1064827598336951 [9] Rutter J Computer Science Division 1994 [10] Chandrasekaran, A fast ULV decomposition solver for hierarchical semiseparable representations, SIAM Journal on Matrix Analysis and Applications 28 pp 603– (2006) · Zbl 1120.65031 · doi:10.1137/S0895479803436652 [11] Xia, Fast algorithm for hierarchically semiseparable matrices, Numerical Linear Algebra with Applications 17 pp 953– (2010) · Zbl 1240.65087 · doi:10.1002/nla.691 [12] Bunch, Rank one modification of the symmetric eigenproblem, Numerische Mathematik 31 pp 31– (1978) · Zbl 0369.65007 · doi:10.1007/BF01396012 [13] Li, An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem, SIAM Journal on Matrix Analysis and Applications 35 pp 1038– (2014) · Zbl 1305.65127 · doi:10.1137/130945995 [14] Gu M Xia J A multi-structured superfast Toeplitz solver 2009 [15] Martinsson, A fast randomized algorithm for computing a hierarchically semi-separable representation of a matrix, SIAM Journal on Matrix Analysis and Applications 32 (4) pp 1251– (2011) · Zbl 1237.65028 · doi:10.1137/100786617 [16] Halko, Finding structure with randomness probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review 53 pp 217– (2011) · Zbl 1269.65043 · doi:10.1137/090771806 [17] Liberty, Randomized algorithms for the low-rank approximation of matrices, PNAS 104 pp 20167– (2007) · Zbl 1215.65080 · doi:10.1073/pnas.0709640104 [18] Carrier, A fast adaptive multipole algorithm for particle simulations, SIAM Journal on Scientific and Statistical Computing 9 pp 669– (1988) · Zbl 0656.65004 · doi:10.1137/0909044 [19] Greengard, A fast algorithm for particle simulations, Journal of Computational Physics 73 pp 325– (1987) · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9 [20] Braess, Approximation of 1/x by exponential sums in [1,), IMA Journal of Numerical Analysis 25 pp 685– (2005) · Zbl 1082.65025 · doi:10.1093/imanum/dri015 [21] Wang, Efficient scalable algorithms for hierarchically semiseparable matrices, SIAM Journal on Scientific Computing 35 pp C519– (2013) · Zbl 1285.65017 · doi:10.1137/110848062 [22] Lyons W Fast algorithms with applications to PDEs Ph.D. Thesis Santa Barbara 2005 [23] Gu, A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM Journal on Matrix Analysis and Applications 15 pp 1266– (1994) · Zbl 0807.65029 · doi:10.1137/S089547989223924X [24] Löwner, Über monotone matrixfunktionen, Mathematische Zeitschrift 38 pp 177– (1934) · JFM 60.0055.01 · doi:10.1007/BF01170633 [25] Hackbusch, A sparse matrix arithmetic based on -matrices. Part I: introduction to -matrices, Computing 62 pp 89– (1999) · Zbl 0927.65063 · doi:10.1007/s006070050015 [26] Hackbusch, A sparse matrix arithmetic based on -matrices. Part II: application to multi-dimensional problems, Computing 64 pp 21– (2000) [27] Hackbusch, Data-sparse approximation by adaptive 2-matrices, Computing 69 pp 1– (2002) · Zbl 1012.65023 · doi:10.1007/s00607-002-1450-4 [28] Hackbusch, Lecture on Applied Mathematics pp 9– (2000) · doi:10.1007/978-3-642-59709-1_2 [29] Eidelman, On a new class of structured matrices, Integral Equations and Operator Theory 34 pp 293– (1999) · Zbl 0934.15002 · doi:10.1007/BF01300581 [30] Vandebril, Matrix Computations and Semiseparable Matrices, Volume I: Linear Systems (2008) · Zbl 1141.65019 [31] Chandrasekaran S Dewilde P Gu M Pals T Sun X van der Veen AJ White D Fast stable solvers for sequentially semi-separable linear systems of equations and least squares problems Berkeley, CA 2003 · doi:10.2172/15003389 [32] Chandrasekaran, Some fast algorithms for sequentially semiseparable representation, SIAM Journal on Matrix Analysis and Applications 27 pp 341– (2005) · Zbl 1091.65063 · doi:10.1137/S0895479802405884 [33] Chandrasekaran S Gu M Pals T Fast and stable algorithms for hierarchically semi-separable representations Berkeley, CA 2004 [34] Starr P On the numerical solution of one-dimensional integral and differential equations Ph.D. Thesis New Haven, CT 1991 [35] Xia, Robust approximate Choleksy factorization of rank-structured symmetric positive definite matrices, SIAM Journal on Matrix Analysis and Applications 31 pp 2899– (2010) · Zbl 1217.65061 · doi:10.1137/090750500 [36] Cheng, On the compression of low rank matrices, SIAM Journal on Scientific Computing 26 pp 1389– (2005) · Zbl 1083.65042 · doi:10.1137/030602678 [37] Martinsson, A randomized algorithm for the approximation of matrices, Applied and Computational Harmonic Analysis 30 pp 47– (2011) · Zbl 1210.65095 · doi:10.1016/j.acha.2010.02.003 [38] Gu, Efficient algorithms for computing a strong-rank revealing QR factorization, SIAM Journal on Scientific Computing 17 pp 848– (1996) · Zbl 0858.65044 · doi:10.1137/0917055 [39] Pan, On the existence and computation of rank revealing LU factorizations, Linear Algebra and its Applications 316 pp 199– (2000) · Zbl 0962.65023 · doi:10.1016/S0024-3795(00)00120-8 [40] Goreinov, Theory of pesudo-skeleton matrix approximations, Linear Algebra and its Applications 261 pp 1– (1997) · Zbl 0877.65021 · doi:10.1016/S0024-3795(96)00301-1 [41] Stewart, Four algorithms for the efficient computation of truncated pivoted QR approximations to a sparse matrix, Numerische Mathematik 83 pp 313– (1999) · Zbl 0957.65031 · doi:10.1007/s002110050451 [42] Chan, Some applications of the rank-revealing QR factorization, SIAM Journal on Scientific and Statistical Computing 13 pp 727– (1992) · Zbl 0756.65032 · doi:10.1137/0913043 [43] Chandrasekaran, A fast solver for HSS representations via sparse matrices, SIAM Journal on Matrix Analysis and Applications 29 pp 67– (2006) · Zbl 1135.65317 · doi:10.1137/050639028 [44] Pichon G Haidar A Faverge M Kurzak J Divide and conquer symmetric tridiagonal eigensolver for multicore architectures In the 29th IEEE International Parallel and Distributed Processing Symposium Hyderabad, India 2015 51 60 [45] Marques, Algorithm 880: A testing infrastructure for symmetric tridiagonal eigensolvers, ACM Transactions on Mathematical Software 35 pp 8:1– (2008) · Zbl 05458493 · doi:10.1145/1377603.1377611 [46] Abramowitz, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (1965) [47] Browne, A portable programming interface for performance evaluation on modern processors, The International Journal of High Performance Computing Applications 14 pp 189– (2000) · doi:10.1177/109434200001400303 [48] Intel VTune Amplifier https://software.intel.com/en-us/intel-vtune-amplifier-xe
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.