INS seminars 61: Matrix-free direct solvers (Jianlin Xia, May.13, 2013)

INS seminars 61

Abstract:

Large sparse linear systems arise frequently in scientific computing and engineering simulations. Both direct solvers and iterative ones have their advantages and disadvantages. Direct solvers are robust and are suitable for multiple right-hand sides. However, they are often expensive for sparse problems due to fill-in. Moreover, direct solvers usually require the matrix to be explicitly available. We propose a series of matrix-free direct solvers, which have two significant advantages: 1. For many types of dense and sparse problems, we only need matrix-vector products (just like in iterative solvers) to construct a direct factorization. The ideas include adaptive randomization, new multi-layer nested dissection, etc. For many problems, it typically require only about O(log^d n) matrix-vector products to reconstruct the matrix, where d is a small integer (e.g., d = 2 for 2D and 3 for 3D discretized problems); 2. We compress dense fill-in into data-sparse approximations so as to achieve nearly O(n) complexity for various types of problems, especially those arising from the discretization of certain types PDEs and integral equations. Various tree structured algorithms are designed or used.