The influence of relaxed supernode partitions on the multifrontal method

ABSTRACT

In this paper we present an algorithm for partitioning the nodes of a graph into supernodes, which improves the performance of the multifrontal method for the factorization of large, sparse matrices on vector computers. This new algorithm first partitions the graph into fundamental supernodes. Next, using a specified relaxation parameter, the supernodes are coalesced in a careful manner to create a coarser supernode partition. Using this coarser partition in the factorization generally introduces logically zero entries into the factor. This is accompanied by a decrease in the amount of sparse vector computations and data movement and an increase in the number of dense vector operations. The amount of storage required for the factor is generally increased by a small amount. On a collection of moderately sized 3-D structures, matrices speedups of 3 to 20 percent on the Cray X-MP are observed over the fundamental supernode partition which allows no logically zero entries in the factor. Using this relaxed supernode partition, the multifrontal method now factorizes the extremely sparse electric power matrices faster than the general sparse algorithm. In addition, there is potential for considerably reducing the communication requirements for an implementation of the multifrontal method on a local memory multiprocessor.

REFERENCES

• 1: ASHCRAFT, C.C. A vector implementation of the multifrontal method for large sparse symmetric positive definite linear systems. Boeing Computer Services, Tech. Rep. ETA-TR-51, Seattle, Wash., 1987.
• 2: ASHCRAFT, C. C., LEWIS, J. G., AND PEYTON, B.W. A supernodal implementation of general sparse factorizations for vector computers. Boeing Computer Services, Tech. Rep. ETA-TR-52, Seattle, Wash., 1987.
• 3: ASHCRAFT, C. C., GRIMES, R. G., LEWIS, J. G., PEYTON, B. W., AND SIMON, H.D. Progress in sparse matrix methods for large linear systems on vector supercomputers. Int. J. Supercomput. Appl. 1 (1987), 10-20.
• 4: David S. Dodson , John G. Lewis, Proposed sparse extensions to the Basic Linear Algebra Subprograms, ACM SIGNUM Newsletter, v.20 n.1, p.22-25, January 1985 [doi>10.1145/1057935.1057938]
• 5: DODSON, D. S., GRIMES, R. G., AND LEWIS, J.G. Sparse extensions to the FORTRAN basic linear algebra subprograms. Boeing Computer Services, Tech. Rep. ETA-TR-63, Seattle, Wash., accepted for publication in ACM TOMS (1988).
• 6: Jack J. Dongarra , Stanley C. Eisenstat, Squeezing the most out of an algorithm in CRAY FORTRAN, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.219-230, Sept. 1984 [doi>10.1145/1271.319413]
• 7: DONGARRA, J. J., DU CROZ, J., HAMMARLING, S. Z., AND HANSON, R.J. An extended set of Fortran basic linear algebra subprograms. Argonne National Laboratory, Tech. Memo. 41, Argonne, Ill., 1986.
• 8: DUFF, I.S. Full matrix techniques in sparse Gaussian elimination. In Lecture Notes in Math., 912, G. A. Watson, Ed. Springer-Verlag, New York, 1982, pp. 71-84.
• 9: I S Duff, Parallel implementation of multifrontal schemes, Parallel Computing, v.3 n.3, p.193-204, July 1986 [doi>10.1016/0167-8191(86)90019-0]
• 10: I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
• 11: DUFF, I. S., AND REID, J.K. The multifrontal solution of unsymmetric sets of linear equations. SIAM J. Sci. Star. Comput. 5 (1984), 633-641.
• 12: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 13: Iain Duff , Roger Grimes , John Lewis , Bill Poole, Sparse matrix test problems, ACM SIGNUM Newsletter, v.17 n.2, p.22-22, June 1982 [doi>10.1145/1057588.1057590]
• 14: EISENSTAT, S. C., SCHULTZ, M. H., AND SHERMAN, A. A. Software for sparse gaussian elimination with limited core storage. In Sparse Matrix Proceedings. I. S. Duff and G. W. Stewart, Eds., SIAM, Philadelphia, Pa., 1978, pp. 135-153.
• 15: EISENSTAT, S. C., SCHULTZ, M. H., AND SHERMAN, A.A. Algorithms and data structures for sparse symmetric Gaussian elimination. SIAM J. Sci. Star. Comput. 2 (1981), 225-237.
• 16: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 17: John G. Lewis , Horst D. Simon, The impact of hardware gather/scatter on sparse Gaussian elimination, SIAM Journal on Scientific and Statistical Computing, v.9 n.2, p.304-311, March 1988 [doi>10.1137/0909019]
• 18: 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]
• 19: Joseph W. Liu, A compact row storage scheme for Cholesky factors using elimination trees, ACM Transactions on Mathematical Software (TOMS), v.12 n.2, p.127-148, June 1986 [doi>10.1145/6497.6499]
• 20: Joseph W. H. Liu, On the storage requirement in the out-of-core multifrontal method for sparse factorization, ACM Transactions on Mathematical Software (TOMS), v.12 n.3, p.249-264, Sept. 1986 [doi>10.1145/7921.11325]
• 21: Robert Schreiber, A New Implementation of Sparse Gaussian Elimination, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.256-276, Sept. 1982 [doi>10.1145/356004.356006]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance