View in EDS

AN EFFICIENT MULTICORE IMPLEMENTATION OF A NOVEL HSS-STRUCTURED MULTIFRONTAL SOLVER USING RANDOMIZED SAMPLING.

Saved in:
Bibliographic Details
Title: AN EFFICIENT MULTICORE IMPLEMENTATION OF A NOVEL HSS-STRUCTURED MULTIFRONTAL SOLVER USING RANDOMIZED SAMPLING.
Authors: GHYSELS, PIETER1 pghysels@lbl.gov, LI, XIAOYE S.1 xsli@lbl.gov, ROUET, FRANÇOIS-HENRY1 fhrouet@lbl.gov, WILLIAMS, SAMUEL1 swwilliams@lbl.gov, NAPOV, ARTEM2 anapov@ulb.ac.be
Source: SIAM Journal on Scientific Computing. 2016, Vol. 38 Issue 5, pS358-S384. 27p.
Subjects: Linear systems, Semiseparable matrices, Algorithms, Partial differential equations, Finite element method
Abstract: We present a sparse linear system solver that is based on a multifrontal variant of Gaussian elimination and exploits low-rank approximation of the resulting dense frontal matrices. We use hierarchically semiseparable (HSS) matrices, which have low-rank off-diagonal blocks, to approximate the frontal matrices. For HSS matrix construction, a randomized sampling algorithm is used together with interpolative decompositions. The combination of the randomized compression with a fast ULV HSS factorization leads to a solver with lower computational complexity than the standard multifrontal method for many applications, resulting in speedups up to sevenfold for problems in our test suite. The implementation targets many-core systems by using task parallelism with dynamic runtime scheduling. Numerical experiments show performance improvements over state-ofthe-art sparse direct solvers. The implementation achieves high performance and good scalability on a range of modern shared memory parallel systems, including the Intel Xeon Phi (MIC). The code is part of a software package called STRUMPACK (STRUctured Matrices PACKage), which also has a distributed memory component for dense rank-structured matrices. [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: 119256293
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: AN EFFICIENT MULTICORE IMPLEMENTATION OF A NOVEL HSS-STRUCTURED MULTIFRONTAL SOLVER USING RANDOMIZED SAMPLING.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22GHYSELS%2C+PIETER%22">GHYSELS, PIETER</searchLink><relatesTo>1</relatesTo><i> pghysels@lbl.gov</i><br /><searchLink fieldCode="AR" term="%22LI%2C+XIAOYE+S%2E%22">LI, XIAOYE S.</searchLink><relatesTo>1</relatesTo><i> xsli@lbl.gov</i><br /><searchLink fieldCode="AR" term="%22ROUET%2C+FRANÇOIS-HENRY%22">ROUET, FRANÇOIS-HENRY</searchLink><relatesTo>1</relatesTo><i> fhrouet@lbl.gov</i><br /><searchLink fieldCode="AR" term="%22WILLIAMS%2C+SAMUEL%22">WILLIAMS, SAMUEL</searchLink><relatesTo>1</relatesTo><i> swwilliams@lbl.gov</i><br /><searchLink fieldCode="AR" term="%22NAPOV%2C+ARTEM%22">NAPOV, ARTEM</searchLink><relatesTo>2</relatesTo><i> anapov@ulb.ac.be</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Scientific+Computing%22">SIAM Journal on Scientific Computing</searchLink>. 2016, Vol. 38 Issue 5, pS358-S384. 27p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Linear+systems%22">Linear systems</searchLink><br /><searchLink fieldCode="DE" term="%22Semiseparable+matrices%22">Semiseparable matrices</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Partial+differential+equations%22">Partial differential equations</searchLink><br /><searchLink fieldCode="DE" term="%22Finite+element+method%22">Finite element method</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We present a sparse linear system solver that is based on a multifrontal variant of Gaussian elimination and exploits low-rank approximation of the resulting dense frontal matrices. We use hierarchically semiseparable (HSS) matrices, which have low-rank off-diagonal blocks, to approximate the frontal matrices. For HSS matrix construction, a randomized sampling algorithm is used together with interpolative decompositions. The combination of the randomized compression with a fast ULV HSS factorization leads to a solver with lower computational complexity than the standard multifrontal method for many applications, resulting in speedups up to sevenfold for problems in our test suite. The implementation targets many-core systems by using task parallelism with dynamic runtime scheduling. Numerical experiments show performance improvements over state-ofthe-art sparse direct solvers. The implementation achieves high performance and good scalability on a range of modern shared memory parallel systems, including the Intel Xeon Phi (MIC). The code is part of a software package called STRUMPACK (STRUctured Matrices PACKage), which also has a distributed memory component for dense rank-structured matrices. [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=119256293
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/15M1010117
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 27
        StartPage: S358
    Subjects:
      – SubjectFull: Linear systems
        Type: general
      – SubjectFull: Semiseparable matrices
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Partial differential equations
        Type: general
      – SubjectFull: Finite element method
        Type: general
    Titles:
      – TitleFull: AN EFFICIENT MULTICORE IMPLEMENTATION OF A NOVEL HSS-STRUCTURED MULTIFRONTAL SOLVER USING RANDOMIZED SAMPLING.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: GHYSELS, PIETER
      – PersonEntity:
          Name:
            NameFull: LI, XIAOYE S.
      – PersonEntity:
          Name:
            NameFull: ROUET, FRANÇOIS-HENRY
      – PersonEntity:
          Name:
            NameFull: WILLIAMS, SAMUEL
      – PersonEntity:
          Name:
            NameFull: NAPOV, ARTEM
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: 2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 10648275
          Numbering:
            – Type: volume
              Value: 38
            – Type: issue
              Value: 5
          Titles:
            – TitleFull: SIAM Journal on Scientific Computing
              Type: main
ResultId 1