Mixed precision low-rank approximations and their application to block low-rank LU factorization
Authors:
- 3 August 2022
- journal article
- research article
- Published by Oxford University Press (OUP) in IMA Journal of Numerical Analysis
- Vol. 43 (4) , 2198-2227
Abstract
We introduce a novel approach to exploit mixed precision arithmetic for low-rank approximations. Our approach is based on the observation that singular vectors associated with small singular values can be stored in lower precisions while preserving high accuracy overall. We provide an explicit criterion to determine which level of precision is needed for each singular vector. We apply this approach to block low-rank (BLR) matrices, most of whose off-diagonal blocks have low rank. We propose a new BLR LU factorization algorithm that exploits the mixed precision representation of the blocks. We carry out the rounding error analysis of this algorithm and prove that the use of mixed precision arithmetic does not compromise the numerical stability of the BLR LU factorization. Moreover, our analysis determines which level of precision is needed for each floating-point operation (flop), and therefore guides us toward an implementation that is both robust and efficient. We evaluate the potential of this new algorithm on a range of matrices coming from real-life problems in industrial and academic applications. We show that a large fraction of the entries in the LU factors and flops to perform the BLR LU factorization can be safely switched to lower precisions, leading to significant reductions of the storage and expected time costs, of up to a factor three using fp64, fp32, and bfloat16 arithmetics.Keywords
This publication has 28 references indexed in Scilit:
- On the Complexity of the Block Low-Rank Multifrontal FactorizationSIAM Journal on Scientific Computing, 2017
- A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear SystemsSIAM Journal on Scientific Computing, 2017
- Hierarchical Matrices: Algorithms and Analysis2015
- Improving Multifrontal Methods by Means of Block Low-Rank RepresentationsSIAM Journal on Scientific Computing, 2015
- Mixed-Precision Cholesky QR Factorization and Its Case Studies on Multicore CPU with Multiple GPUsSIAM Journal on Scientific Computing, 2015
- The university of Florida sparse matrix collectionACM Transactions on Mathematical Software, 2011
- Accuracy and Stability of Numerical Algorithms2002
- Optimization by Direct Search in Matrix ComputationsSIAM Journal on Matrix Analysis and Applications, 1993
- Scaling for Numerical Stability in Gaussian EliminationJournal of the ACM, 1979
- On the Compatibility of a Given Solution With the Data of a Linear SystemJournal of the ACM, 1967