Wednesday, October 29

MS5
Advances in Sparse Matrix Reorderings

3:00 PM-5:00 PM
Room: Ballroom 2

Sparse systems of linear equations arise in a large variety of scientific and engineering applications. Sparsity preservation is crucial in solving such linear systems using matrix factorizations as fill occurs during the computation. The speakers in this minisymposium will discuss recent work on developing robust and efficient ordering algorithms for sparse matrix factorizations. The effectiveness of direct methods for solving linear systems is affected by the initial ordering of the rows and/or columns of the coefficient matrix. For symmetric matrices, the most popular fill-reducing ordering algorithms are minimum degree and nested dissection. Minimum degree is a greedy heuristic. Although it is effective on most problems, there are instances for which minimum degree can perform poorly. Simple nested dissection heuristics are fast, but typically less effective for unstructured problems. For nonsymmetric matrices, little ordering work has been done.

Organizer: Esmond G. Ng
Oak Ridge National Laboratory

3:00 Practical Extensions of the Multisection Ordering for Sparse Matrices

Cleve Ashcraft, Boeing Information and Support Services; Stanley C. Eisenstat, Yale University; and Joseph W. H. Liu, York University, Canada

3:30 Multilevel Graph Partitioning and Nested Dissection

George Karypis, University of Minnesota, Minneapolis

4:00 Performance of Greedy Ordering Heuristics for Sparse Cholesky Factorization

Esmond G. Ng, Organizer; and Padma Raghavan, University of Tennessee, Knoxville

4:30 A Column Approximate Minimum Degree Ordering Algorithm

Timothy A. Davis, University of Florida; John R. Gilbert, Xerox Palo Alto Research Center; Esmond G. Ng, Organizer; and Barry W. Peyton, Oak Ridge National Laboratory

LA97 Homepage | Program Updates| Registration | Hotel Information | Transportation | Program-at-a-Glance |