Improving Multifrontal Methods by Means of Block Low-Rank Representations
| Autor: | Patrick R. Amestoy, Olivier Boiteau, Cleve Ashcraft, Jean-Yves L'Excellent, Clement Weisbecker, Alfredo Buttari |
|---|---|
| Přispěvatelé: | Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Livermore Software Technology Corporation [Livermore] (LSTC), EDF R&D (EDF R&D), EDF (EDF), Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut National Polytechnique (Toulouse) (Toulouse INP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
multifrontal method
sparse direct methods Rank (linear algebra) Applied Mathematics MathematicsofComputing_NUMERICALANALYSIS Solver [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation QR decomposition Algebra Computational Mathematics Matrix (mathematics) Algebraic operation low-rank approximations Singular value decomposition [INFO]Computer Science [cs] elliptic PDEs Algorithm [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS] Block (data storage) Sparse matrix Mathematics |
| Zdroj: | SIAM Journal on Scientific Computing SIAM Journal on Scientific Computing, Society for Industrial and Applied Mathematics, 2015, 37 (3), pp.A1451-A1474. ⟨10.1137/120903476⟩ SIAM Journal on Scientific Computing, 2015, 37 (3), pp.A1451-A1474. ⟨10.1137/120903476⟩ |
| ISSN: | 1064-8275 |
| DOI: | 10.1137/120903476⟩ |
| Popis: | International audience; Matrices coming from elliptic partial differential equations have been shown to have alow-rank property: well-defined off-diagonal blocks of their Schur complements can be approximatedby low-rank products. Given a suitable ordering of the matrix which gives the blocks a geometricalmeaning, such approximations can be computed using an SVD or a rank-revealing QR factorization.The resulting representation offers a substantial reduction of the memory requirement and givesefficient ways to perform many of the basic dense linear algebra operations. Several strategies,mostly based on hierarchical formats, have been proposed to exploit this property. We study asimple, nonhierarchical, low-rank format called block low-rank (BLR) and explain how it can be usedto reduce the memory footprint and the complexity of sparse direct solvers based on the multifrontalmethod. We present experimental results on matrices coming from elliptic PDEs and from variousother applications. We show that even if BLR-based factorizations are asymptotically less efficientthan hierarchical approaches, they still deliver considerable gains. The BLR format is compatiblewith numerical pivoting, and its simplicity and flexibility make it easy to use in the context of ageneral purpose, algebraic solver. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|