An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures
From MaRDI portal
Publication:724535
DOI10.1016/J.CAM.2018.05.051zbMATH Open1391.65086arXiv1612.07526OpenAlexW2561673710WikidataQ129729285 ScholiaQ129729285MaRDI QIDQ724535FDOQ724535
Authors: François-Henry Rouet, Jie Liu, Chun Huang, Xingyu Gao, Xuebin Chi, Shengguo Li 
Publication date: 26 July 2018
Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1612.07526
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
Parallel numerical computation (65Y05) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Parallel algorithms in computer science (68W10)
Cites Work
- LAPACK Users' Guide
- ScaLAPACK: A portable linear algebra library for distributed memory computers -- design issues and performance
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- Fast algorithms for hierarchically semiseparable matrices
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem
- Fast algorithms for spherical harmonic expansions. II.
- Rank-one modification of the symmetric eigenproblem
- Title not available (Why is that?)
- Some Fast Algorithms for Sequentially Semiseparable Representations
- Randomized algorithms for the low-rank approximation of matrices
- On the Compression of Low Rank Matrices
- On a new class of structured matrices
- A fast algorithm for computing the smallest eigenvalue of a symmetric positive-definite Toeplitz matrix
- A Divide and Conquer method for the symmetric tridiagonal eigenproblem
- On the Orthogonality of Eigenvectors Computed by Divide-and-Conquer Techniques
- A fast QR algorithm for companion matrices
- Title not available (Why is that?)
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization
- Solving the Symmetric Tridiagonal Eigenvalue Problem on the Hypercube
- A Parallel Divide and Conquer Algorithm for the Symmetric Eigenvalue Problem on Distributed Memory Architectures
- An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
- New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem.
- Direction-Preserving and Schur-Monotonic Semiseparable Approximations of Symmetric Positive Definite Matrices
- Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
- Minisymposium 4 : Parallele Algorithmen in Der Numerischen Algebra
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.
- A hybrid parallel algorithm based on divided and conquer method using MPI/Cilk for the symmetric tridiagonal eigenproblem
- Synchronization properties of interconnected network based on the vital node
- Comprehensive decomposition optimization method for locating key sets of commenters spreading conspiracy theory in complex social networks
Uses Software
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)
