An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures
From MaRDI portal
(Redirected from Publication:724535)
Abstract: In this paper, an efficient divide-and-conquer (DC) algorithm is proposed for the symmetric tridiagonal matrices based on ScaLAPACK and the hierarchically semiseparable (HSS) matrices. HSS is an important type of rank-structured matrices.Most time of the DC algorithm is cost by computing the eigenvectors via the matrix-matrix multiplications (MMM). In our parallel hybrid DC (PHDC) algorithm, MMM is accelerated by using the HSS matrix techniques when the intermediate matrix is large. All the HSS algorithms are done via the package STRUMPACK. PHDC has been tested by using many different matrices. Compared with the DC implementation in MKL, PHDC can be faster for some matrices with few deflations when using hundreds of processes. However, the gains decrease as the number of processes increases. The comparisons of PHDC with ELPA (the Eigenvalue soLvers for Petascale Applications library) are similar. PHDC is usually slower than MKL and ELPA when using 300 or more processes on Tianhe-2 supercomputer.
Recommendations
- New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
- A hybrid parallel algorithm based on divided and conquer method using MPI/Cilk for the symmetric tridiagonal eigenproblem
- scientific article; zbMATH DE number 1330403
- A Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures
- Parallel block tridiagonalization of real symmetric matrices
Cites work
- scientific article; zbMATH DE number 1955860 (Why is no real title available?)
- scientific article; zbMATH DE number 1531793 (Why is no real title available?)
- 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 Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures
- A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization
- A fast QR algorithm for companion matrices
- A fast algorithm for computing the smallest eigenvalue of a symmetric positive-definite Toeplitz matrix
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Direction-Preserving and Schur-Monotonic Semiseparable Approximations of Symmetric Positive Definite Matrices
- Fast algorithms for hierarchically semiseparable matrices
- Fast algorithms for spherical harmonic expansions. II.
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- LAPACK Users' Guide
- Minisymposium 4 : Parallele Algorithmen in Der Numerischen Algebra
- New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
- On a new class of structured matrices
- On the Compression of Low Rank Matrices
- On the Orthogonality of Eigenvectors Computed by Divide-and-Conquer Techniques
- 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
- ScaLAPACK: A portable linear algebra library for distributed memory computers -- design issues and performance
- Solving the Symmetric Tridiagonal Eigenvalue Problem on the Hypercube
- Some Fast Algorithms for Sequentially Semiseparable Representations
Cited in
(5)- SuperDC: superfast divide-and-conquer eigenvalue decomposition with improved stability for rank-structured matrices
- New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
- Comprehensive decomposition optimization method for locating key sets of commenters spreading conspiracy theory in complex social networks
- Synchronization properties of interconnected network based on the vital node
- A hybrid parallel algorithm based on divided and conquer method using MPI/Cilk for the symmetric tridiagonal eigenproblem
This page was built for publication: An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724535)
