In many computational and engineering problems, it is critical to solve large sparse linear systems of equations rapidly and reliably. Nevertheless, many practical but difficult large linear systems of equations remain out of reach computationally. In this project, the PI develops structured fast direct methods and pre-conditioners for solving such large sparse linear systems. These methods systematically exploit potentially rich numerical low-rank patterns within the fill-ins for large reductions in computational time and memory. The efficiency of these methods comes from three innovative design strategies: the PI develops randomized algorithms that can rapidly compute high quality low-rank approximations with low numerical compression overhead; the PI adapts these methods to preserve desirable properties of the original matrix for enhanced numerical reliability; and the PI re-organizes the computations so that no numerical compression and data communication is performed unless necessary.
The outcome of this research has the potential to create a novel class of direct solvers and pre-conditioners that in conjunction with iterative solvers can become powerful weapons for solving difficult large sparse linear systems, and the low-rank approximation schemes would become a valuable tool for the general scientific community, as effective data compression is essential in many areas of science and engineering. Mathematical software for rapidly solving large sparse linear systems of equations and for effective compression of large data sets will be made available to the scientific computing public.
