.png){kind=icon}
.png){kind=icon}
Return
SUPERFAST DIVIDE-AND-CONQUER METHOD AND PERTURBATION ANALYSIS FOR STRUCTURED EIGENVALUE SOLUTIONS
.png){kind=icon}
PRE
AI
DOI：10.1137/15M1018812.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present a sup er fast divide-and-conquer method for finding all the eigenvalues as well as all the eigenvectors (in a structured form) of a class of symmetric matrices with off-diagonal ranks or numerical ranks bounded by r, as well as the approximation accuracy of the eigenvalues due to off-diagonal compression. More specifically, the complexity is O (r(2)n log n) + O (r n log(2)n), where n is the order of the matrix. Such matrices are often encountered in practical computations with banded matrices, Toeplitz matrices (in Fourier space), and certain discretized problems. They can be represented or approximated by hierarchically semiseparable (HSS) matrices. We show how to preserve the HSS structure throughout the dividing process that involves recursive updates and how to quickly perform stable eigendecompositions of the structured forms. Various other numerical issues are discussed, such as computation reuse and deflation. The structure of the eigenvector matrix is also shown. We further analyze the structured perturbation, i.e., how compression of the off-diagonal blocks impacts the accuracy of the eigenvalues. They show that rank structured methods can serve as an effective and efficient tool for approximate eigenvalue solutions with controllable accuracy. The algorithm and analysis are very useful for finding the eigendecomposition of matrices arising from some important applications and can be modified to find SVDs of nonsymmetric matrices. The efficiency and accuracy are illustrated in terms of Toeplitz and discretized matrices. Our method requires significantly fewer operations than a recent structured eigensolver, by nearly an order of magnitude.
Keywords:
superfast divide-and-conquer
eigenvalue decomposition
structured perturbation analysis
linear complexity
rank structure
compression
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W
View more organizations