Fast, Stable, and Matrix-Free Direct Solvers for Large Dense Linear Systems

Host

Applied Mathematics

Speaker

Jianlin Xia
Purdue University
www.math.purdue.edu/~xiaj/

Description

Abstract: In numerical computations and engineering simulations, solving large dense linear systems is usually the major cost. Examples include discretized integral equations, Schur complements in direct factorizations of sparse matrices, radial basis function interpolations, spectral approximations, etc. For large matrix sizes n, standard direct solvers cost $O(n^3)$ flops with $O(n^2)$ storage and are impractical. On the other hand, many problems are severely ill conditioned, which makes iterative methods hard to converge. Additional difficulties may arise, such as multiple right-hand sides and the lack of explicit matrices.

We discuss a class of structured direct solvers, which approximate the dense matrices by data-sparse or compressed forms. The approximations can be based on certain kernel information as in the fast multipole method or treecodes (which have been previously used to accelerated matrix-vector products). The approximations can also be algebraic or matrix-free (based on matrix-vector products as in iterative methods). The approximation accuracy are user controllable. The data-sparse forms are then quickly factorized and solved. For various problems, the solution cost and the storage are nearly $O(n)$. Moreover, we show that the factorization provides significantly better stability than standard LU factorizations with partial pivoting. Numerical tests in terms of some integral equations and RBF interpolations will be given. This is joint work with Yuanzhe Xi.