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^{2}), 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.