A review of frontal methods for solving linear systems. (English) Zbl 0926.65030

Summary: We review some recent developments in frontal and multifrontal schemes for solving sparse linear systems, including variants that exploit parallelism and matrix structure. An important aspect of these methods is the extensive use of full linear algebra kernels that are both portable and efficient over a wide range of machines.


65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
Full Text: DOI


[1] Amestoy, P.R.; Duff, I.S., Vectorization of a multiprocessor multifrontal code, Int. J. supercomputer applic., 3, 41, (1989)
[2] Amestoy, P.R.; Duff, I.S., MUPS: a parallel package for solving sparse unsymmetric sets of linear equations, (), to appear · Zbl 0956.65017
[3] Amestoy, P.R.; Daydé, M.J.; Duff, I.S.; Morère, P., Linear algebra calculations on a virtual shared memory computer, Int. J. high speed computing, (1994)
[4] Anderson, E.; Bai, Z.; Bischof, C.; Demmel, J.; Dongarra, J.; DuCroz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Ostrouchov, S.; Sorensen, D., LAPACK users guide, (1992), SIAM Philadelphia, PA · Zbl 0843.65018
[5] Harwell Subroutine Library, A catalogue of subroutines (release 11), (1993), Theoretical Studies Department, AEA Industrial Technology, Anon
[6] Benner, R.E.; Montry, G.R.; Weigand, G.G., Concurrent multifrontal methods: shared memory, cache, and frontwidth issues, Int. J. supercomputer applications, 1, 26, (1987)
[7] Conroy, J.M.; Kratzer, S.G.; Lucas, R.F., Data-parallel sparse matrix factorization, (), 377 · Zbl 0819.65026
[8] Davis, T.A.; Duff, I.S., A combined unifrontal/multifrontal method for unsymmetric sparse matrices, () · Zbl 0962.65027
[9] Davis, T.A.; Duff, I.S., An unsymmetric-pattern multifrontal method for sparse LU factorization, () · Zbl 0884.65021
[10] Dongarra, J.J.; Croz, Du J.; Duff, I.S.; Hammarling, S., A set of level 3 basic linear algebra subprograms, ACM trans. on math. software, 16, 1, (1990) · Zbl 0900.65115
[11] Duff, I.S., MA32 —; A package for solving sparse unsymmetric systems using the frontal method, () · Zbl 0541.65017
[12] Duff, I.S.; Reid, J.K., The multifrontal solution of indefinite sparse symmetric linear systems, ACM trans. on math. software, 9, 302, (1983) · Zbl 0515.65022
[13] Duff, I.S.; Reid, J.K., MA48, a Fortran code for direct solution of sparse unsymmetric linear systems of equations, () · Zbl 0884.65019
[14] Duff, I.S.; Reid, J.K., MA47, a Fortran code for direct solution of indefinite sparse symmetric linear systems, () · Zbl 0884.65020
[15] Duff, I.S.; Scott, J.A., MA42 —; a new frontal code for solving sparse unsymmetric systems, (), shortened version to appear in ACM Trans. Math. Software · Zbl 0884.65018
[16] Duff, I.S.; Scott, J.A., The use of multiple fronts in Gaussian elimination, (), 567 · Zbl 0819.65023
[17] Duff, I.S., The solution of augmented systems, (), 40-55 · Zbl 0796.65023
[18] Duff, I.S.; Grimes, R.G.; Lewis, J.G., Users guide for the harwell-boeing sparse matrix collection, release I, ()
[19] Duff, I.S.; Reid, J.K.; Scott, J.A., The use of profile reduction algorithms with a frontal code, Int. J. numerical methods in eng., 28, 2555, (1989) · Zbl 0725.65045
[20] Eisenstat, S.C.; Liu, J.W.H., Exploiting structural symmetry in unsymmetric sparse symbolic factorization, SIAM J. matrix analysis and appl., 13, 202, (1992) · Zbl 0746.65023
[21] Gay, D.M., Electronic mail distribution of linear programming test problems, Mathematical programming society, COAL newsletter, (1985)
[22] Gupta, A.; Kumar, V., A scalable parallel algorithm for sparse matrix factorization, ()
[23] Irons, B.M., A frontal solution program for finite-element analysis, Int. J. num. methods in eng., 2, 5, (1970) · Zbl 0252.73050
[24] Liu, J.W.H., On the storage requirement in the out-of-core multifrontal method for sparse factorization, ACM trans. on math. software, 12, 249, (1987)
[25] Liu, J.W.H., The multifrontal method for sparse matrix solution: theory and practice, SIAM rev., 34, 82, (1992) · Zbl 0919.65019
[26] Lucas, R.F., A hybrid multifrontal algorithm for factoring extremely sparse matrices, ()
[27] Rothberg, E., Efficient sparse Cholesky factorization on distributed-memory multiprocessors, (), 141
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.