Computer Science NASC Seminar
A Fast Algorithm for Sparse Matrix Computations Related to Inversion
Song Li, Stanford
February 11, 2011
10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 100121110
(Directions)
Spring 2011 NASC Seminars Calendar
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 bigO sense for 2D and 3D problems. However, in practice, FIND suffers from two problems due to the wideseparators used by its partitioning scheme. One problem caused by the wideseparators is that they introduce large constant factors into the computational cost of FIND. The other problem is that wideseparators 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, FINDSS (Singlelayer Separator), resolves these problems. By thoroughly decomposing the computation process, we are able to efficiently compute entries of the inverse while using the same narrowseparators employed by nested dissection algorithms. The framework that our method is based on is the first attempt to apply the widelyused 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 FINDSS with other methods related to elimination trees.
