Liao, X.; Li, S.; Lu, Y.; Román Moltó, JE. (2021). A Parallel Structured Divide-and-Conquer Algorithm for Symmetric Tridiagonal Eigenvalue Problems. IEEE Transactions on Parallel and Distributed Systems. 32(2):367-378. https://doi.org/10.1109/TPDS.2020.3019471
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/176234
Title:
|
A Parallel Structured Divide-and-Conquer Algorithm for Symmetric Tridiagonal Eigenvalue Problems
|
Author:
|
Liao, Xia
Li, Shengguo
Lu, Yutong
Román Moltó, José Enrique
|
UPV Unit:
|
Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació
|
Issued date:
|
|
Abstract:
|
[EN] In this article, a parallel structured divide-and-conquer (PSDC) eigensolver is proposed for symmetric tridiagonal matrices based on ScaLAPACK and a parallel structured matrix multiplication algorithm, called PSMMA. ...[+]
[EN] In this article, a parallel structured divide-and-conquer (PSDC) eigensolver is proposed for symmetric tridiagonal matrices based on ScaLAPACK and a parallel structured matrix multiplication algorithm, called PSMMA. Computing the eigenvectors via matrix-matrix multiplications is the most computationally expensive part of the divide-and-conquer algorithm, and one of the matrices involved in such multiplications is a rank-structured Cauchy-like matrix. By exploiting this particular property, PSMMA constructs the local matrices by using generators of Cauchy-like matrices without any communication, and further reduces the computation costs by using a structured low-rank approximation algorithm. Thus, both the communication and computation costs are reduced. Experimental results show that both PSMMA and PSDC are highly scalable and scale to 4096 processes at least. PSDC has better scalability than PHDC that was proposed in [16] and only scaled to 300 processes for the same matrices. Comparing with PDSTEDC in ScaLAPACK, PSDC is always faster and achieves 1.4x-1.6x speedup for some matrices with few deflations. PSDC is also comparable with ELPA, with PSDC being faster than ELPA when using few processes and a little slower when using many processes.
[-]
|
Subjects:
|
Approximation algorithms
,
Symmetric matrices
,
Generators
,
Eigenvalues and eigenfunctions
,
Matrix decomposition
,
Complexity theory
,
Scalability
,
PSMMA
,
PUMMA algorithm
,
ScaLAPACK
,
Divide-and-conquer
,
Rank-structured matrix
,
Cauchy-like matrix
|
Copyrigths:
|
Reserva de todos los derechos
|
Source:
|
IEEE Transactions on Parallel and Distributed Systems. (issn:
1045-9219
)
|
DOI:
|
10.1109/TPDS.2020.3019471
|
Publisher:
|
Institute of Electrical and Electronics Engineers
|
Publisher version:
|
https://doi.org/10.1109/TPDS.2020.3019471
|
Project ID:
|
info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-107379RB-I00/ES/ALGORITMOS PARALELOS Y SOFTWARE PARA METODOS ALGEBRAICOS EN ANALISIS DE DATOS/
...[+]
info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-107379RB-I00/ES/ALGORITMOS PARALELOS Y SOFTWARE PARA METODOS ALGEBRAICOS EN ANALISIS DE DATOS/
info:eu-repo/grantAgreement/NSFC//NNW2019ZT6-B20/
info:eu-repo/grantAgreement/NSFC//NNW2019ZT6B21/
info:eu-repo/grantAgreement/NSFC//NNW2019ZT5-A10/
info:eu-repo/grantAgreement/NSFC//U1611261/
info:eu-repo/grantAgreement/NSFC//61872392/
info:eu-repo/grantAgreement/NSFC//U1811461/
info:eu-repo/grantAgreement/National Key Research and Development Program, China//2018YFB0204303/
info:eu-repo/grantAgreement/Natural Science Foundation of Guangdong Province//2018B030312002/
info:eu-repo/grantAgreement/Natural Science Foundation of Guangdong Province//2016ZT06D211/
info:eu-repo/grantAgreement/Natural Science Foundation of Hunan Province//2019JJ40339/
info:eu-repo/grantAgreement/NUDT//ZK18-03-01/
[-]
|
Description:
|
© 2021 IEEE. Personal use of this material is permitted. Permissíon from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertisíng or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
|
Thanks:
|
The authors would like to thank the referees for their valuable comments which greatly improve the presentation of this article. This work was supported by National Natural Science Foundation of China (No. NNW2019ZT6-B20, ...[+]
The authors would like to thank the referees for their valuable comments which greatly improve the presentation of this article. This work was supported by National Natural Science Foundation of China (No. NNW2019ZT6-B20, NNW2019ZT6B21, NNW2019ZT5-A10, U1611261, 61872392, and U1811461), National Key RD Program of China (2018YFB0204303), NSF of Hunan (No. 2019JJ40339), NSF of NUDT (No. ZK18-03-01), Guangdong Natural Science Foundation (2018B030312002), and the Program for Guangdong Introducing Innovative and Entrepreneurial Teams under Grant 2016ZT06D211. The work of Jose E. Roman was supported by the Spanish Agencia Estatal de Investigacion (AEI) under project SLEPc-DA (PID2019-107379RB-I00).
[-]
|
Type:
|
Artículo
|