Modification of the minimum-degree algorithm by multiple elimination

ABSTRACT

The most widely used ordering scheme to reduce fills and operations in sparse matrix computation is the minimum-degree algorithm. The notion of multiple elimination is introduced here as a modification to the conventional scheme. The motivation is discussed using the k-by-k grid model problem. Experimental results indicate that the modified version retains the fill-reducing property of (and is often better than) the original ordering algorithm and yet requires less computer time. The reduction in ordering time is problem dependent, and for some problems the modified algorithm can run a few times faster than existing implementations of the minimum-degree algorithm. The use of external degree in the algorithm is also introduced.

REFERENCES

• 1: DUFF, I.S. A sparse future. In Sparse Matrices and Their Uses, I.S. Duff, Ed. Academic Press, New York, 1982, pp. 1-29.
• 2: 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]
• 3: 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]
• 4: EISENSTAT, S.C., GURSKY, M.C., SCHULTZ, M.H., AND SHERMAN, A.H. The Yale Sparse Matrix Package, I. The symmetric code. Res. Rep. 112, Dept. of Computer Science, Yale Univ., New Haven, Conn., 1977.
• 5: EISENSTAT, S.C., SCHULTZ, M.H., AND SHERMAN, A.H. Applications of an element model for Gaussian elimination. In Sparse Matrix Computations, J.R. Bunch and D.J. Rose, Eds. Academic Press, New York, 1976 pp. 85-96.
• 6: Alan George , Joseph W. H. Liu, A Fast Implementation of the Minimum Degree Algorithm Using Quotient Graphs, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.337-358, Sept. 1980 [doi>10.1145/355900.355906]
• 7: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 8: GEORGE, J.A., L{u, J.W.H., AND NG, E. User guide for SPARSPAK, Waterloo Sparse Linear Equations Package. Res. Rep. CS 78-30 (revised 1980), Dept. of Computer Science, Univ. of Waterloo, Waterloo, Ont., Can., 1980.
• 9: PETERS, F.J. Parallel pivoting algorithms for sparse symmetric matrices. Tech. Rep., Dept. of Mathematics and Computer Science, Eindhoven Univ. of Technology, Eindhoven, Neth., 1982.
• 10: RosE, D.J. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In Graph Theory and Computing, R.C. Read, Ed. Academic Press, New York, 1973, pp. 183-217.
• 11: TINNEY, W.F., AND WALKER, J.W. Direct solution of sparse network equations by optimally ordered triangular factorization. Proc. IEEE 55 (1967), 1801-1809.
• 12: YANNAKAKIS, M. Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth. 1 (1981), 77-79.

INDEX TERMS

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)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
elimination, minimum degree, ordering, sparse ordering