Skip to Main content Skip to Navigation
Journal articles

Solving Block Low-Rank Linear Systems by LU Factorization is Numerically Stable

Abstract : Block low-rank (BLR) matrices possess a blockwise low-rank property that can be exploited to reduce the complexity of numerical linear algebra algorithms. The impact of these low-rank approximations on the numerical stability of the algorithms in floating-point arithmetic has not previously been analyzed. We present rounding error analysis for the solution of a linear system by LU factorization of BLR matrices. Assuming that a stable pivoting scheme is used, we prove backward stability: the relative backward error is bounded by a modest constant times ε, where the low-rank threshold ε is the parameter controlling the accuracy of the blockwise low-rank approximations. In addition to this key result, our analysis offers three new insights into the numerical behavior of BLR algorithms. First, we compare the use of a global or local low-rank threshold and find that a global one should be preferred. Second, we show that performing intermediate recompressions during the factorization can significantly reduce its cost without compromising numerical stability. Third, we consider different BLR factorization variants and determine the update-compress-factor (UCF) variant to be the best. Tests on a wide range of matrices from various real-life applications show that the predictions from the analysis are realized in practice.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-02496325
Contributor : Theo Mary <>
Submitted on : Monday, June 7, 2021 - 12:01:57 PM
Last modification on : Tuesday, July 13, 2021 - 3:27:39 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Citation

Nicholas Higham, Théo Mary. Solving Block Low-Rank Linear Systems by LU Factorization is Numerically Stable. IMA Journal of Numerical Analysis, Oxford University Press (OUP), 2021, ⟨10.1093/imanum/drab020⟩. ⟨hal-02496325v3⟩

Share

Metrics

Record views

12

Files downloads

12