Matrix inversion with limited memory usage

Abstract

Nowadays, due to emerging big data applications, it is necessary to develop algorithms capable of performing operations on extremely large-order matrices that must deal with memory constraints. In this work, we revisit the BRI (Block Recursive Inversion) algorithm that inverts matrices with limited memory usage. BRI manipulates only matrix blocks instead of the entire matrix and therefore requires less memory. In this work, we provide a mathematical foundation for the BRI algorithm. In addition, we generalize the underlying idea of ​​the BRI algorithm and propose variants of it called NW-BRI and Pruned NW-BRI. They partition the matrix in a more appropriate way to reduce numerical problems with nonsingular blocks and reduce the number of block inversions. The work measured the memory consumption of all these algorithms. The results showed that only 10\% to 20\% of the memory was used compared to conventional inversion by LU decomposition. However, the algorithms took significantly longer to run than inversion by LU decomposition. Naturally, this time can be reduced by using a parallel version of then.