A new scheduling algorithm for parallel sparse LU factorization with static pivoting

ABSTRACT

In this paper we present a static scheduling algorithm for parallel sparse LU factorization with static pivoting. The algorithm is divided into mapping and scheduling phases, using the symmetric pruned graphs of L^T and U to represent dependencies. The scheduling algorithm is designed for driving the parallel execution of the factorization on a distributed-memory architecture. Experimental results and comparisons with SuperLU_DIST are reported after applying this algorithm on real world application matrices on an IBM SP RS/6000 distributed memory machine.

REFERENCES

• 1: Patrick R. Amestoy , Iain S. Duff , Jean-Yves L'excellent , Xiaoye S. Li, Analysis and comparison of two general sparse solvers for distributed memory computers, ACM Transactions on Mathematical Software (TOMS), v.27 n.4, p.388-421, December 2001 [doi>10.1145/504210.504212]
• 2: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 3: I. S. Duff , J. Koster, On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix, SIAM Journal on Matrix Analysis and Applications, v.22 n.4, p.973-996, 2000 [doi>10.1137/S0895479899358443]
• 4: Stanley C. Eisenstat , Joseph W. H. Liu, Exploiting structural symmetry in unsymmetric sparse symbolic factorization, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.202-211, Jan. 1992 [doi>10.1137/0613017]
• 5: Stanley C. Eisenstat , Joseph W. H. Liu, Exploiting structural symmetry in a sparse partial pivoting code, SIAM Journal on Scientific Computing, v.14 n.1, p.253-257, Jan. 1993 [doi>10.1137/0914016]
• 6: Hesham El-Rewini , Hesham H. Ali , Ted Lewis, Task Scheduling in Multiprocessing Systems, Computer, v.28 n.12, p.27-37, December 1995 [doi>10.1109/2.476197]
• 7: J. A. George, J. W. H. Liu, and E. G. Ng. Communication results for parallel sparse Cholesky factorization on a hypercube. Parallel Computing, 10:287--298, 1989.
• 8: John R. Gilbert , Joseph W. H. Liu, Elimination structures for unsymmetric sparse LU factors, SIAM Journal on Matrix Analysis and Applications, v.14 n.2, p.334-352, April 1993 [doi>10.1137/0614024]
• 9: P. Henon, P. Ramet, and J. Roman. Pastix: A parallel direct solver for sparse spd matrices based on efficient static scheduling and memory managment. In SIAM Conference PPSC'2001, Portsmouth, Virginie, USA, 2001.
• 10: M. Joshi, G. Karypis, V. Kumar, A. Gupta, and F. Gustavson. PSPASES: Scalable Parallel Direct Solver Library for Sparse Symmetric Positive Definite Linear Systems. Technical report, University of Minnesota and IBM Thomas J. Watson Research Center, May 1999.
• 11: Xiaoye S. Li , James W. Demmel, Making sparse Gaussian elimination scalable by static pivoting, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-17, November 07-13, 1998, San Jose, CA
• 12: X. S. Li and J. W. Demmel. A Scalable Sparse Direct Solver Using Static Pivoting. 9th SIAM Conference on Parallel Processing and Scientific Computing, 1999.
• 13: Joseph W. H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.141-153, June 1985 [doi>10.1145/214392.214398]
• 14: Joseph W. H. Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications, v.11 n.1, p.134-172, January 1990 [doi>10.1137/0611010]
• 15: Alex Pothen , Chunguang Sun, A mapping algorithm for parallel sparse Cholesky factorization, SIAM Journal on Scientific Computing, v.14 n.5, p.1253-1257, Sept. 1993 [doi>10.1137/0914074]
• 16: M. Wu and D. D. Gajski. Hypertool: A programming aid for message-passing systems. IEEE Trans. on Parallel and Distributed Systems, 5(9):951--967, 1994.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Experimentation, Measurement, Performance