Computational Mathematics and Scientific Computing Seminar

---

A Fast Algorithm for Sparse Matrix Computations Related to Inversion

Speaker: Song Li, Stanford

Location: Warren Weaver Hall 1302

Date: Feb. 11, 2011, 10 a.m.

Synopsis:

Many problems require computing a subset of the inverse of sparse matrix. Most existing methods for this problem are based on both Gaussian elimination and back substitution, except for the FIND (Fast Inverse using Nested Dissection) algorithm, which is solely based on repeated Gaussian elimination. The FIND algorithm is optimal in the big-O sense for 2D and 3D problems. However, in practice, FIND suffers from two problems due to the wide-separators used by its partitioning scheme. One problem caused by the wide-separators is that they introduce large constant factors into the computational cost of FIND. The other problem is that wide-separators result in a partitioning scheme different from those used by algorithms based on nested dissection; this makes it difficult for FIND to take advantage of existing partitioning methods and libraries for nested dissection. Our new method, FIND-SS (Single-layer Separator), resolves these problems. By thoroughly decomposing the computation process, we are able to efficiently compute entries of the inverse while using the same narrow-separators employed by nested dissection algorithms. The framework that our method is based on is the first attempt to apply the widely-used relationship between mesh nodes and matrix computations to the problem of multiple eliminations with reuse of partial results. This framework also makes it easier to compare FIND-SS with other methods related to elimination trees.