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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 108627471
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: EFFICIENT SCALABLE ALGORITHMS FOR SOLVING DENSE LINEAR SYSTEMS WITH HIERARCHICALLY SEMISEPARABLE STRUCTURES.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22SHEN+WANG%22">SHEN WANG</searchLink><relatesTo>1</relatesTo><i> wang273@math.purdue.edu</i><br /><searchLink fieldCode="AR" term="%22LI%2C+XIAOYE+S%2E%22">LI, XIAOYE S.</searchLink><relatesTo>2</relatesTo><i> xsli@lbl.gov</i><br /><searchLink fieldCode="AR" term="%22JIANLIN+XIA%22">JIANLIN XIA</searchLink><relatesTo>1</relatesTo><i> xiaj@math.purdue.edu</i><br /><searchLink fieldCode="AR" term="%22YINGCHONG+SITU%22">YINGCHONG SITU</searchLink><relatesTo>3</relatesTo><i> ysitu@cs.purdue.edu</i><br /><searchLink fieldCode="AR" term="%22DE+HOOP%2C+MAARTEN+V%2E%22">DE HOOP, MAARTEN V.</searchLink><relatesTo>1</relatesTo><i> mdehoop@math.purdue.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Scientific+Computing%22">SIAM Journal on Scientific Computing</searchLink>. 2013, Vol. 35 Issue 6, pC519-C544. 26p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Semiseparable+matrices%22">Semiseparable matrices</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+algorithms%22">Parallel algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Imaging+systems+in+seismology%22">Imaging systems in seismology</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+computers%22">Parallel computers</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+systems%22">Linear systems</searchLink><br /><searchLink fieldCode="DE" term="%22Boundary+value+problems%22">Boundary value problems</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=108627471
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/110848062
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 26
        StartPage: C519
    Subjects:
      – SubjectFull: Semiseparable matrices
        Type: general
      – SubjectFull: Parallel algorithms
        Type: general
      – SubjectFull: Imaging systems in seismology
        Type: general
      – SubjectFull: Parallel computers
        Type: general
      – SubjectFull: Linear systems
        Type: general
      – SubjectFull: Boundary value problems
        Type: general
    Titles:
      – TitleFull: EFFICIENT SCALABLE ALGORITHMS FOR SOLVING DENSE LINEAR SYSTEMS WITH HIERARCHICALLY SEMISEPARABLE STRUCTURES.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: SHEN WANG
      – PersonEntity:
          Name:
            NameFull: LI, XIAOYE S.
      – PersonEntity:
          Name:
            NameFull: JIANLIN XIA
      – PersonEntity:
          Name:
            NameFull: YINGCHONG SITU
      – PersonEntity:
          Name:
            NameFull: DE HOOP, MAARTEN V.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: 2013
              Type: published
              Y: 2013
          Identifiers:
            – Type: issn-print
              Value: 10648275
          Numbering:
            – Type: volume
              Value: 35
            – Type: issue
              Value: 6
          Titles:
            – TitleFull: SIAM Journal on Scientific Computing
              Type: main
ResultId 1