×

Sparse direct factorizations through unassembled hyper-matrices. (English) Zbl 1227.65111

Summary: We present a novel strategy for sparse direct factorizations that is geared towards the matrices that arise from \(hp\)-adaptive Finite Element Methods. In that context, a sequence of linear systems derived by successive local refinement of the problem domain needs to be solved. Thus, there is an opportunity for a factorization strategy that proceeds by updating (and possibly downdating) the factorization. Our scheme consists of storing the matrix as unassembled element matrices, hierarchically ordered to mirror the refinement history of the domain. The factorization of such an ’unassembled hyper-matrix’ proceeds in terms of element matrices, only assembling nodes when they need to be eliminated. The main benefits are efficiency from the fact that only updates to the factorization are made, high scalar efficiency since the factorization process uses dense matrices throughout, and a workflow that integrates naturally with the application.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Amestoy, P. R.; Duff, I. S.; L’Excellent, J.-Y.; Koster, J., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal., 23, 15-41 (2001), also ENSEEIHT-IRIT Technical Report RT/APO/99/2 · Zbl 0992.65018
[2] Balay, S.; Gropp, W. D.; McInnes, L. C.; Smith, B. F., Efficient management of parallelism in object oriented numerical software libraries, (Arge, E.; Bruaset, A. M.; Langtangen, H. P., Modern Software Tools in Scientific Computing (1997), Birkhauser Press), 163-202 · Zbl 0882.65154
[4] Barragy, E.; van de Geijn, R., Blas performance for selected segments of a high \(p\) EBE finite element code, Int. J. Numer. Methods Engrg., 38, 1327-1340 (1995) · Zbl 0824.76044
[8] Davis, T. A.; Duff, I. S., A combined unifrontal/multifrontal method for unsymmetric sparse matrices, ACM Trans. Math. Softw., 25, 1-19 (1999) · Zbl 0962.65027
[9] Davis, T. A., Direct Methods for Sparse Linear Systems (2006), SIAM: SIAM Philadelphi, PA · Zbl 1119.65021
[11] Demkowicz, L., Computing with hp-Adaptive Finite Elements, One and Two Dimensional Elliptic and Maxwell Problems, vol. 1 (2007), Chapman & Hall/CRC
[12] Demmel, J. W.; Eisenstat, S. C.; Gilbert, J. R.; Li, X. S.; Liu, J. W.H., A supernodal approach to sparse partial pivoting, SIAM J. Matrix Anal. Appl., 20, 3, 720-755 (1999) · Zbl 0931.65022
[13] Demmel, J. W.; Gilbert, J. R.; Li, X. S., An asynchronous parallel supernodal algorithm for sparse gaussian elimination, SIAM J. Matrix Anal. Appl., 20, 4, 915-952 (1999) · Zbl 0939.65036
[14] Dongarra, J. J.; Croz, J. D.; Hammarling, S.; Duff, I., A set of level 3 basic linear algebra subprograms, ACM Trans. Math. Softw., 16, 1, 1-17 (1990) · Zbl 0900.65115
[15] Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J., 23, 298-305 (1973) · Zbl 0265.05119
[17] George, A.; Liu, J. H.-W., Computer Solution of Large Sparse Positive Definite Systems (1981), Prentice-Hall, Inc.: Prentice-Hall, Inc. Englewood Cliffs, New Jersey, 07632 · Zbl 0516.65010
[19] Hendrickson, B.; Leland, R., An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM J. Sci. Comput., 16, 452-469 (1995) · Zbl 0816.68093
[20] Heroux, M. A.; Bartlett, R. A.; Howle, V. E.; Hoekstra, R. J.; Hu, J. J.; Kolda, T. G.; Lehoucq, R. B.; Long, K. R.; Pawlowski, R. P.; Phipps, E. T.; Salinger, A. G.; Thornquist, H. K.; Tuminaro, R. S.; Willenbring, J. M.; Williams, A.; Stanley, K. S., An overview of the trilinos project, ACM Trans. Math. Softw., 1-27 (2004)
[21] Herrero, J. R.; Navarro, J. J., Sparse hypermatrix cholesky: customization for high performance, IAENG Int. J. Appl. Math., 36, 1, 6-12 (2007) · Zbl 1227.65030
[24] Lawson, C.; Hanson, R.; Kincaid, D.; Krogh, F., Basic linear algebra subprograms for FORTRAN usage, Trans. Math. Softw., 5, 308-323 (1979) · Zbl 0412.65022
[26] Li, X. S.; Demmel, J. W., SuperLU_DIST: a scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Trans. Math. Softw., 29, 2, 110-140 (2003) · Zbl 1068.90591
[27] Lipton, R. J.; Rose, D. J.; Tarjan, R. E., Generalized nested dissection, SIAM J. Numer. Anal., 16, 346-358 (1979) · Zbl 0435.65021
[28] Lipton, R. J.; Tarjan, R. E., A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177-189 (1979) · Zbl 0432.05022
[32] Pardo, D.; Demkowicz, L., Integration of hp-adaptivity and a two grid solver for elliptic problems, Comput. Methods Appl. Mech. Engrg., 195, 674-710 (2006) · Zbl 1093.65112
[34] Pothen, A.; Simon, H. D.; Liou, K.-P., Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11, 3, 430-452 (1990) · Zbl 0711.65034
[35] Schwab, Ch., \(p\)- and hp-Finite Element Methods: Theory and Applications in Solid and Fluid Mechanics (1998), Oxford University Press · Zbl 0910.73003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.