New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
From MaRDI portal
Abstract: In this paper, two accelerated divide-and-conquer algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost {flops} in the worst case, where is the dimension of the matrix and 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 done 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 6x times faster for some large matrices with few deflations.
Recommendations
- An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures
- A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices
- An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
- scientific article; zbMATH DE number 1330403
- scientific article; zbMATH DE number 741157
Cites work
- A Divide and Conquer method for the symmetric tridiagonal eigenproblem
- A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- A fast algorithm for particle simulations
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A Fast Solver for HSS Representations via Sparse Matrices
- A Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures
- A randomized algorithm for the decomposition of matrices
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A Stable and Efficient Algorithm for the Rank-One Modification of the Symmetric Eigenproblem
- A theory of pseudoskeleton approximations
- An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
- Approximation of 1/x by exponential sums in [1, ∞)
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures
- Fast algorithms for hierarchically semiseparable matrices
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
- scientific article; zbMATH DE number 1049353 (Why is no real title available?)
- Matrix computations and semiseparable matrices. Vol. 1: Linear systems.
- Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
- On a new class of structured matrices
- On the Compression of Low Rank Matrices
- On the existence and computation of rank-revealing LU factorizations
- Performance and Accuracy of LAPACK's Symmetric Tridiagonal Eigensolvers
- Randomized algorithms for the low-rank approximation of matrices
- Rank-one modification of the symmetric eigenproblem
- Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
- Some Applications of the Rank Revealing QR Factorization
- Some Fast Algorithms for Sequentially Semiseparable Representations
Cited in
(8)- A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices
- An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths
- Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions
- Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD
- A fast randomized eigensolver with structured LDL factorization update
- An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
- SuperDC: superfast divide-and-conquer eigenvalue decomposition with improved stability for rank-structured matrices
- An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures
This page was built for publication: New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955975)
