- -

A Parallel Structured Divide-and-Conquer Algorithm for Symmetric Tridiagonal Eigenvalue Problems

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A Parallel Structured Divide-and-Conquer Algorithm for Symmetric Tridiagonal Eigenvalue Problems

Show simple item record

Files in this item

dc.contributor.author Liao, Xia es_ES
dc.contributor.author Li, Shengguo es_ES
dc.contributor.author Lu, Yutong es_ES
dc.contributor.author Román Moltó, José Enrique es_ES
dc.date.accessioned 2021-11-05T14:06:21Z
dc.date.available 2021-11-05T14:06:21Z
dc.date.issued 2021-02-01 es_ES
dc.identifier.issn 1045-9219 es_ES
dc.identifier.uri http://hdl.handle.net/10251/176234
dc.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. es_ES
dc.description.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. 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. es_ES
dc.description.sponsorship 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). es_ES
dc.language Inglés es_ES
dc.publisher Institute of Electrical and Electronics Engineers es_ES
dc.relation.ispartof IEEE Transactions on Parallel and Distributed Systems es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Approximation algorithms es_ES
dc.subject Symmetric matrices es_ES
dc.subject Generators es_ES
dc.subject Eigenvalues and eigenfunctions es_ES
dc.subject Matrix decomposition es_ES
dc.subject Complexity theory es_ES
dc.subject Scalability es_ES
dc.subject PSMMA es_ES
dc.subject PUMMA algorithm es_ES
dc.subject ScaLAPACK es_ES
dc.subject Divide-and-conquer es_ES
dc.subject Rank-structured matrix es_ES
dc.subject Cauchy-like matrix es_ES
dc.subject.classification CIENCIAS DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL es_ES
dc.title A Parallel Structured Divide-and-Conquer Algorithm for Symmetric Tridiagonal Eigenvalue Problems es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1109/TPDS.2020.3019471 es_ES
dc.relation.projectID 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/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/NSFC//NNW2019ZT6-B20/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/NSFC//NNW2019ZT6B21/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/NSFC//NNW2019ZT5-A10/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/NSFC//U1611261/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/NSFC//61872392/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/NSFC//U1811461/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/National Key Research and Development Program, China//2018YFB0204303/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/Natural Science Foundation of Guangdong Province//2018B030312002/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/Natural Science Foundation of Guangdong Province//2016ZT06D211/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/Natural Science Foundation of Hunan Province//2019JJ40339/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/NUDT//ZK18-03-01/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation 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 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1109/TPDS.2020.3019471 es_ES
dc.description.upvformatpinicio 367 es_ES
dc.description.upvformatpfin 378 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 32 es_ES
dc.description.issue 2 es_ES
dc.relation.pasarela S\442891 es_ES
dc.contributor.funder AGENCIA ESTATAL DE INVESTIGACION es_ES
dc.contributor.funder National Natural Science Foundation of China es_ES
dc.contributor.funder Natural Science Foundation of Hunan Province es_ES
dc.contributor.funder National University of Defense Technology, China es_ES
dc.contributor.funder Natural Science Foundation of Guangdong Province es_ES
dc.contributor.funder National Key Research and Development Program, China es_ES


This item appears in the following Collection(s)

Show simple item record