Premium
New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem
Author(s) -
Li Shengguo,
Liao Xiangke,
Liu Jie,
Jiang Hao
Publication year - 2016
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2046
Subject(s) - tridiagonal matrix , divide and conquer algorithms , eigenvalues and eigenvectors , mathematics , algorithm , dimension (graph theory) , rank (graph theory) , matrix (chemical analysis) , flops , diagonal , divide and conquer eigenvalue algorithm , cauchy distribution , diagonal matrix , parallel computing , combinatorics , computer science , mathematical analysis , physics , materials science , geometry , quantum mechanics , composite material
Summary In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O ( N 2 r ) 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. Copyright © 2016 John Wiley & Sons, Ltd.