×

zbMATH — the first resource for mathematics

An efficient analyse phase for element problems. (English) Zbl 1313.65044
Summary: The analyse phase of a sparse direct solver for symmetrically structured systems of linear equations is used to determine the sparsity pattern of the matrix factor. This allows the subsequent numerical factorisation and solve phases to be executed efficiently. Many direct solvers require the system matrix to be in assembled form. For problems arising from finite element applications, assembling and then using the system matrix can be costly in terms of both time and memory. This paper describes and implements a variant of the work of Gilbert, Ng and Peyton for matrices in elemental form. The proposed variant works with an equivalent matrix that avoids explicitly assembling the system matrix and exploits supervariables. Numerical experiments using problems from practical applications are used to demonstrate the significant advantages of working directly with the elemental form.

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gilbert, An efficient algorithm to compute row and column counts for sparse Cholesky factorization, SIAM Journal on Matrix Analysis and Applications 15 (4) pp 1075– (1994) · Zbl 0810.65023
[2] HSL A collection of Fortran codes for large-scale scientific computation 2011 http://www.hsl.rl.ac.uk
[3] George, Computer Solution of Large Sparse Positive Definite Systems (1981) · Zbl 0516.65010
[4] Duff, Direct Methods for Sparse Matrices (1986)
[5] Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications 11 (1) pp 134– (1990) · Zbl 0697.65013
[6] Duff, The multifrontal solution of indefinite sparse symmetric linear systems, ACM Transactions on Mathematical Software 9 pp 302– (1983) · Zbl 0515.65022
[7] Ashcraft, The influence of relaxed supernode partitions on the multifrontal method, ACM Transactions on Mathematical Software 15 pp 291– (1999) · Zbl 0900.65061
[8] Davis, Dynamic supernodes in sparse Cholesky update/downdate and triangular solves, ACM Transactions Mathematical Software 35 (2009) · Zbl 05517420
[9] Davis, The University of Florida sparse matrix collection, ACM Transactions on Mathematical Software 28 (2011) · Zbl 1365.65123
[10] Ng, Block sparse Cholesky algorithms on advanced uniprocessor computers, SIAM Journal on Scientific Computing 14 (5) pp 1034– (1993) · Zbl 0785.65015
[11] Ng, Proceedings of the Fourth IMACS International Symposium on Iterative Methods in Scientific Computation pp 211– (1999)
[12] Damhaug AC Reid JK MA46, a FORTRAN code for the direct solution of sparse unsymmetric linear systems of equations from finite-element applications Technical Report RAL-TR-96-010 1996
[13] Chen, Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate, ACM Transactions on Mathematical Software 35 (2008)
[14] Gilbert, Computing row and column counts for sparse QR and LU factorization, BIT 41 (4) pp 693– (2001) · Zbl 0992.65016
[15] Demmel, A supernodal approach to sparse partial pivoting, SIAM Journal on Matrix Analysis and Applications 20 (3) pp 720– (1999) · Zbl 0931.65022
[16] Demmel JW Gilbert JR Li XS SuperLU users’ guide 2010
[17] Patwary, Experiments on union-find algorithms for the disjoint-set data structure, Experimental Algorithms 6049 pp 411– (2010) · Zbl 05703564
[18] Duff, Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems, ACM Transactions on Mathematical Software 22 (2) pp 227– (1996) · Zbl 0884.65020
[19] Reid, An out-of-core sparse Cholesky solver, ACM Transactions on Mathematical Software 36 (2) (2009) · Zbl 1364.65071
[20] Hogg JD Scott JA A modern analyse phase for sparse tree-based direct methods Technical Report RAL-TR-2010-031 2010
[21] Duff, MA57- a new code for the solution of sparse symmetric definite and indefinite systems, ACM Transactions on Mathematical Software 30 pp 118– (2004) · Zbl 1070.65525
[22] Schenk, Solving unsymmetric sparse systems of linear equations with PARDISO, Journal of Future Generation Computer Systems 20 pp 475– (2004) · Zbl 1062.65035
[23] Gupta A Joshi M Kumar V WSMP: a high-performance serial and parallel sparse linear solver Technical Report RC 22038 (98932) 2001 http://www.cs.umn.edu/ agupta/doc/wssmp-paper.ps
[24] Gupta A WSMP: Watson sparse matrix package (Part-I: direct solution of symmetric sparse systems) Technical Report RC 21886 2000 http://www.cs.umn.edu/ agupta/wsmp
[25] Duff IS Reid JK MA27 - a set of Fortran subroutines for solving sparse symmetric sets of linear equations Technical Report AERE-R 10533 1982
[26] Karypis G Kumar V METIS - family of multilevel partitioning algorithms 1998 http://glaros.dtc.umn.edu/gkhome/views/metis
[27] Karypis, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on Scientific Computing 20 pp 359– (1999) · Zbl 0915.68129
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.