A combined unifrontal/multifrontal method for unsymmetric sparse matrices

ABSTRACT

We discuss the organization of frontal matrices in multifrontal methods for the solution of large sparse sets of unsymmetric linear equations. In the multifrontal method, work on a frontal matrix can be suspended, the frontal matrix can be stored for later reuse, and a new frontal matrix can be generated. There are thus several frontal matrices stored during the factorization, and one or more of these are assembled (summed) when creating a new frontal matrix. Although this means that arbitrary sparsity patterns can be handled efficiently, extra work is required to sum the frontal matrices together and can be costly because indirect addressing is requred. The (uni)frontal method avoids this extra work by factorizing the matrix with a single frontal matrix. Rows and columns are added to the frontal matrix, and pivot rows and columns are removed. Data movement is simpler, but higher fill-in can result if the matrix cannot be permuted into a variable-band form with small profile. We consider a combined unifrontal/multifrontal algorithm to enable general fill-in reduction orderings to be applied without the data movement of previous multifrontal approaches. We discuss this technique in the context of a code designed for the solution of sparse systems with unsymmetric pattern.

REFERENCES

• 1: AMESTOY, P. R. AND DUFF, I. S. 1989. Vectorization of a multiprocessor multifrontal code. Int. J. Supercomput. Appl. High Perform. Eng. 3, 3, 41-59.
• 2: Patrick R. Amestoy , Timothy A. Davis , Iain S. Duff, An Approximate Minimum Degree Ordering Algorithm, SIAM Journal on Matrix Analysis and Applications, v.17 n.4, p.886-905, Oct. 1996 [doi>10.1137/S0895479894278952]
• 3: AMESTOY, P. R., DAYD , M., AND DUFF, I. S. 1989. Use of computational kernels in the solution of full and sparse linear equations. In Proceedings of the International Workshop on Parallel and Distributed Algorithms (Gers, France, Oct. 3-6), M. Cosnard, Y. Robert, P. Quinton, and M. Raynal, Eds. North-Holland Publishing Co., Amsterdam, The Netherlands, 13-19.
• 4: ARIOLI, M., DEMMEL, J. W., AND DUFF, I. S. 1989. Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Appl. 10, 165-190.
• 5: BAI, Z., DAY, D., DEMMEL, J., AND DONGARRA, J. 1996. Test matrix collection (non-Hermitian eigenvalue problems), Release 1. Tech. Rep. (Sept.). University of Kentucky, Lexington, KY. Available at ftp://ftp.ms.uky.edu/pub/misc/bai/Collection.
• 6: CHAN, W. M. AND GEORGE, A. 1980. A linear time implementation of the reverse Cuthill- Mckee algorithm. BIT 20, 8-14.
• 7: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 8: DAVIS, T.A. 1995. Users' guide to the unsymmetric-pattern multifrontal package (UMF- PACK, version 1.1). Tech. Rep. TR-95-004. CISE Department, University of Florida, Gainesville, FL.
• 9: DAVIS, T.A. 1997. University of Florida sparse matrix collection. CISE Department, University of Florida, Gainesville, FL. http://www.cise.ufl.edu/-davis and ftp://ftp.cise. ufl. edu/pub/faculty/davis.
• 10: DAVIS, T. A. AND DUFF, I. S. 1991. Unsymmetric-pattern multifrontal methods for parallel sparse LU factorization. Tech. Rep. TR-91-023. CISE Department, University of Florida, Gainesville, FL.
• 11: Timothy A. Davis , Iain S. Duff, An Unsymmetric-Pattern Multifrontal Method for Sparse LU Factorization, SIAM Journal on Matrix Analysis and Applications, v.18 n.1, p.140-158, Jan. 1997 [doi>10.1137/S0895479894246905]
• 12: DAYD , M. J. AND DUFF, I. S. 1996. A blocked implementation of Level 3 BLAS for RISC processors. Tech. Rep. RAL-TR-96-014. Rutherford Appleton Lab., Didcot, Oxon, United Kingdom. Also ENSEEIHT-IRIT Tech. Rep. RT/APO/96/1 and CERFACS Rep. TR/PA/96/06.
• 13: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W.H. Liu, A Supernodal Approach to Sparse Partial Pivoting, University of California at Berkeley, Berkeley, CA, 1995
• 14: James W. Demmel , John Gilbert , Xiaoye S. Li, SuperLU Users'' Guide, University of California at Berkeley, Berkeley, CA, 1997
• 15: Jack J Dongarra , Eric Grosse, Distribution of mathematical software via electronic mail, Communications of the ACM, v.30 n.5, p.403-407, May 1987 [doi>10.1145/22899.22904]
• 16: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 17: DUFF, I. S. 1984a. Design features of a frontal code for solving sparse unsymmetric linear systems out-of-core. SIAM J. Sci. Comput. 5, 270-280.
• 18: DUFF, I. S. 1984b. The solution of nearly symmetric sparse linear systems. In Computing Methods in Applied Sciences and Engineering, R. Glowinski and J. Lions, Eds. North-Holland Publishing Co., Amsterdam, The Netherlands, 57-74.
• 19: 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]
• 20: DUFF, I. S. AND REID, J. K. 1984. The multifrontal solution of unsymmetric sets of linear equations. SIAM J. Sci. Comput. 5, 3, 633-641.
• 21: DUFF, I. S. AND REID, J. K. 1993. MA48, a Fortran code for direct solution of sparse unsymmetric linear systems of equations. Tech. Rep. RAL-93-072. Rutherford Appleton Lab., Didcot, Oxon, United Kingdom.
• 22: I. S. Duff , J. K. Reid, The design of MA48: a code for the direct solution of sparse unsymmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.187-226, June 1996 [doi>10.1145/229473.229476]
• 23: DUFF, I. S. AND SCOTT, J.A. 1993. MA42--A new frontal code for solving sparse unsymmetric systems. Tech. Rep. RAL 93-064. Rutherford Appleton Lab., Didcot, Oxon, United Kingdom.
• 24: DUFF, I. S. AND SCOTT, J.A. 1994. The use of multiple fronts in Gaussian elimination. In Proceedings of the 5th SIAM Conference on Applied Linear Algebra (Philadelphia, PA), J. Lewis, Ed. SIAM, Philadelphia, PA, 567-571.
• 25: DUFF, I. S. AND SCOTT, g.A. 1996a. A comparison of frontal software with other sparse direct solvers. Tech. Rep. RAL-TR-96-102. Rutherford Appleton Lab., Didcot, Oxon, United Kingdom.
• 26: I. S. Duff , J. A. Scott, The design of a new frontal code for solving sparse, unsymmetric systems, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.30-45, March 1996 [doi>10.1145/225545.225550]
• 27: 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]
• 28: FELDMAN, P., MELVILLE, R., AND LONG, D. 1996. Efficient frequency domain analysis of large nonlinear analog circuits. In Proceedings of the IEEE Conference on Custom Integrated Circuits (Santa Clara, CA). IEEE Press, Piscataway, NJ.
• 29: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 30: A. George , W. H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review, v.31 n.1, p.1-19, Mar. 1989 [doi>10.1137/1031001]
• 31: HSL. 1996. Harwell Subroutine Library: A Catalogue of Subroutines (Release 12). AEA Technology, Didcot, Oxon, United Kingdom.
• 32: IRONS, B. M. 1970. A frontal solution program for finite element analysis. Int. J. Numer. Method. Eng. 2, 5-32.
• 33: Joseph W. H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review, v.34 n.1, p.82-109, March 1992 [doi>10.1137/1034004]
• 34: LIU, J. W. H. AND SHERMAN, A. H. 1976. Comparative analysis of the Cuthill-Mckee and the reverse Cuthill-Mckee ordering algorithms for sparse matrices. SIAM J. Numer. Anal. 13, 2, 198-213.
• 35: SAAD, Y. 1994. Sparskit: A basic tool kit for sparse matrix computation, version 2. Tech. Rep. Computer Science Department, Univ. of Minnesota, Minneapolis, MN.
• 36: Stephen A. Vavasis, Stable finite elements for problems with wild coefficients, SIAM Journal on Numerical Analysis, v.33 n.3, p.890-916, June 1996 [doi>10.1137/0733045]
• 37: S. E. Zitney, Sparse matrix methods for chemical process separation calculations on supercomputers, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.414-423, November 16-20, 1992, Minneapolis, Minnesota, United States
• 38: ZITNEY, S. E. AND STADTHERR, M.A. 1993. Supercomputing strategies for the design and analysis of complex separation systems. Ind. Eng. Chem. Res. 32, 604-612.
• 39: ZITNEY, S. E., MALLYA, J., DAVIS, T. A., AND STADTHERR, M.A. 1996. Multifrontal vs. frontal techniques for chemical process simulation on supercomputers. Comput. Chem. Eng. 20, 6-7, 641-646.

INDEX TERMS

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

Additional 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, Experimentation, Performance

Keywords:
frontal methods, linear equations, multifrontal methods, sparse unsymmetric matrices