OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

On the Complexity of the Block Low-Rank Multifrontal Factorization

Amestoy, Patrick and Buttari, Alfredo and L'Excellent, Jean-Yves and Mary, Théo On the Complexity of the Block Low-Rank Multifrontal Factorization. (2017) SIAM Journal on Scientific Computing, 39 (4). 1710-1740. ISSN 1064-8275

[img] (Document in English)

PDF (Publisher's version) - Depositor and staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
494kB

Official URL: https://epubs.siam.org/doi/abs/10.1137/16M1077192

Abstract

Matrices coming from elliptic partial differential equations have been shown to have a low-rank property: well-defined off-diagonal blocks of their Schur complements can be approximated by low-rank products, and this property can be efficiently exploited in multifrontal solvers to provide a substantial reduction of their complexity. Among the possible low-rank formats, the block low- rank (BLR) format is easy to use in a general purpose multifrontal solver and has been shown to provide significant gains compared to full-rank on practical applications. However, unlike hierarchical formats, such as H and HSS, its theoretical complexity was unknown. In this paper, we extend the theoretical work done on hierarchical matrices in order to compute the theoretical complexity of the BLR multifrontal factorization. We then present several variants of the BLR multifrontal factorization, depending on the strategies used to perform the updates in the frontal matrices and on the constraints on how numerical pivoting is handled. We show how these variants can further reduce the complexity of the factorization. In the best case (3D, constant ranks), we obtain a complexity of the order of O(n 4/3 ). We provide an experimental study with numerical results to support our complexity bounds.

Item Type:Article
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Ecole Normale Supérieure de Lyon - ENS de Lyon (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - INPT (FRANCE)
French research institutions > Institut National de la Recherche en Informatique et en Automatique - INRIA (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UPS (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université Claude Bernard-Lyon I - UCBL (FRANCE)
Laboratory name:
Statistics:download
Deposited By: IRIT IRIT
Deposited On:10 Sep 2018 15:10

Repository Staff Only: item control page