Solving block low-rank linear systems by LU factorization is numerically stable

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 analysed. 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 epsilon, where the low-rank threshold e 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 behaviour 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 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.

Automated summary

This paper investigates the application of block low-rank matrices in numerical linear algebra algorithms and analyzes the numerical stability in floating-point arithmetic. The paper presents a rounding error analysis method for solving linear systems using LU factorization of BLR matrices. It offers new insights into the numerical behavior of BLR algorithms by comparing the use of different low-rank thresholds, performing intermediate recompressions, and considering different factorization variants.