Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Scalable and Dependable Sparse Matrix Factorization

View Current Project Information

Edward Jason Riedy and James Demmel

National Science Foundation CCF-00444486

Direct factorization for solving sparse systems of linear equations Ax = b often is not used for massive systems (over 1 million unknowns). Current implementations do not scale to the necessary large parallel systems.

To provide scalability, we decouple the symbolic computations from the scalable numerical work by selecting pivots before factorization. This static pivoting allows efficient factorization of massive matrices on distributed-memory parallel platforms. Static pivoting currently has two drawbacks: the implementation to compute the pivoting is sequential, and the numerical error and stability properties are not well understood. We are removing both of those drawbacks. Computing the pivoting requires finding a maximum-weight matching on a bipartite graph. This problem appears not only in sparse factorization but also in computational biology, social network analysis, and data mining. We compute a matching with a parallel, scalable auction algorithm. This algorithm also provides a framework for parallel analysis of a sparse matrix's graph structure. We address static pivoting's numerical robustness through improved heuristics, extra-precise iterative refinement, and extensive testing. Improved perturbation heuristics greatly reduce factorization error if tiny pivots occur. Extra-precise iterative refinement for dense systems provides low-error solutions and dependable error estimates [1,2]; we are extending these results to the sparse case. We also have proven that the perturbed factorization serves as a preconditioner for suitable iterative methods that reduce the number of necessary steps to the number of perturbations.

J. Demmel, Y. Hida, W. Kahan, X. Li, S. Mukherjee, and J. Riedy, "Error Bounds from Extra Precise Iterative Refinement," ACM Trans. Mathematical Software, June 2006. DOI: 10.1145/1141885.1141894
J. Demmel, Y. Hida, X. Li, and J. Riedy, "Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems," LAPACK Working Note 188, May 2007.