View in EDS

EFFICIENT SCALABLE ALGORITHMS FOR SOLVING DENSE LINEAR SYSTEMS WITH HIERARCHICALLY SEMISEPARABLE STRUCTURES.

Saved in:
Bibliographic Details
Title: EFFICIENT SCALABLE ALGORITHMS FOR SOLVING DENSE LINEAR SYSTEMS WITH HIERARCHICALLY SEMISEPARABLE STRUCTURES.
Authors: SHEN WANG1 wang273@math.purdue.edu, LI, XIAOYE S.2 xsli@lbl.gov, JIANLIN XIA1 xiaj@math.purdue.edu, YINGCHONG SITU3 ysitu@cs.purdue.edu, DE HOOP, MAARTEN V.1 mdehoop@math.purdue.edu
Source: SIAM Journal on Scientific Computing. 2013, Vol. 35 Issue 6, pC519-C544. 26p.
Subjects: Semiseparable matrices, Parallel algorithms, Imaging systems in seismology, Parallel computers, Linear systems, Boundary value problems
Abstract: Hierarchically semiseparable (HSS) matrix techniques are emerging in constructing superfast direct solvers for both dense and sparse linear systems. Here, we develop a set of novel parallel algorithms for key HSS operations that are used for solving large linear systems. These are parallel rank-revealing QR factorization, HSS constructions with hierarchical compression, ULV HSS factorization, and HSS solutions. The HSS tree-based parallelism is fully exploited at the coarse level. The BLACS and ScaLAPACK libraries are used to facilitate the parallel dense kernel operations at the fine-grained level. We appply our new solvers for discretized Helmholtz equations for multifrequency seismic imaging and iteratively solve time-harmonic seismic inverse boundary value problems. In particular, we use the HSS algorithms to solve the dense Schur complement systems associated with the root separator of the separator tree obtained from nested dissection of the graph of discretized Helmholtz equations. We demonstrate that the new approach is much faster and uses much less memory than the LU factorization algorithm for both two-dimensional and three-dimensional problems, using up to 8912 processing cores. This is the first work in parallelizing HSS algorithms and conducting detailed performance analysis on a large parallel machine. This also lays a good foundation for developing scalable sparse structured factorization algorithms for general sparse linear systems. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Scientific Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Hierarchically semiseparable (HSS) matrix techniques are emerging in constructing superfast direct solvers for both dense and sparse linear systems. Here, we develop a set of novel parallel algorithms for key HSS operations that are used for solving large linear systems. These are parallel rank-revealing QR factorization, HSS constructions with hierarchical compression, ULV HSS factorization, and HSS solutions. The HSS tree-based parallelism is fully exploited at the coarse level. The BLACS and ScaLAPACK libraries are used to facilitate the parallel dense kernel operations at the fine-grained level. We appply our new solvers for discretized Helmholtz equations for multifrequency seismic imaging and iteratively solve time-harmonic seismic inverse boundary value problems. In particular, we use the HSS algorithms to solve the dense Schur complement systems associated with the root separator of the separator tree obtained from nested dissection of the graph of discretized Helmholtz equations. We demonstrate that the new approach is much faster and uses much less memory than the LU factorization algorithm for both two-dimensional and three-dimensional problems, using up to 8912 processing cores. This is the first work in parallelizing HSS algorithms and conducting detailed performance analysis on a large parallel machine. This also lays a good foundation for developing scalable sparse structured factorization algorithms for general sparse linear systems. [ABSTRACT FROM AUTHOR]
ISSN:10648275
DOI:10.1137/110848062