Fast structured direct solutions of sparse linear systems.
Jianlin Xia (Math, Purdue)

In this talk, we consider the fast solution of sparse linear systems arising from practical problems such as the discretization of some PDEs. We show that, during the direct factorization of the sparse matrices, certain structures exist. These structures enalbe us to solve the systems quickly. Furthermore, for certain problems, the structures are relatively insensitivity to parameters such as frequencies. These properties help us develop fast direct solvers which break classical lower complexity bounds.

We then present some practical ways of solving or preconditioning the systems with the aid of this property. Semiseparable matrix methods and other structured matrix techniques are built into Sparse eliminations so as to develop approximate strucured solvers. The solvers have roughly O(n) cost for 2D PDEs and at most O(n^1.3) cost for 3D ones, in contrast with classical optimal solution costs of O(n^1.5) and O(n²), respectively. Effective preconditioning techniques are also given for problems where the structures are not strong. For SPD problems, the preconditioner preserves the positive definiteness. Various examples are used to demonstrate the performance.