×

Distributed algebraic tearing and interconnecting techniques. (English) Zbl 07128067

Summary: A class of novel parallel preconditioning schemes in conjunction with a Krylov subspace iterative method for solving general sparse linear systems is presented. The proposed preconditioning schemes are domain decomposition methods that enforce the continuity of the solution on the subdomain interfaces using Lagrange multipliers, without requiring geometric information, namely algebraic tearing and interconnecting methods. Hence, they are applicable to a wide variety of problems as they are based only on the adjacency graph corresponding to the coefficient matrix. A modification of the proposed schemes, which improves performance while reducing the required operations is also presented. The algebraic tearing and interconnecting methods are designed for distributed systems with multicore nodes. Numerical results concerning the convergence behavior and the parallel performance of the proposed schemes are given along with discussions.

MSC:

65-XX Numerical analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agullo, E.; Giraud, L.; Guermouche, A.; Haidar, A.; Roman, J., Parallel algebraic domain decomposition solver for the solution of augmented systems, Adv. Eng. Softw., 60, 23-30 (2013)
[2] Amestoy, Pr; Davis, Ta; Duff, Is, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl., 17, 4, 886-905 (1996) · Zbl 0861.65021
[3] Anderson, E., Bai, Z., Dongarra, J., Greenbaum, A., McKenney, A., Croz, J., Hammarling, S., Demmel, J., Bischof, C., Sorensen, D.: LAPACK: a portable linear algebra library for high-performance computers. In: Proceedings of the 1990 ACM/IEEE Conference on Supercomputing, Supercomputing ’90, pp. 2-11. IEEE Computer Society Press, Los Alamitos (1990)
[4] Axelsson, O., Iterative Solution Methods (1996), Cambridge: Cambridge University Press, Cambridge · Zbl 0845.65011
[5] Benzi, M., Preconditioning techniques for large linear systems: a survey, J. Comput. Phys., 182, 2, 418-477 (2002) · Zbl 1015.65018
[6] Benzi, M.; Tûma, M., A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math., 30, 2, 305-340 (1999) · Zbl 0949.65043
[7] Chapman, B.; Jost, G.; Van Der Pas, R., Using Openmp: Portable Shared Memory Parallel Programming, vol. 10 (2008), Cambridge: MIT Press, Cambridge
[8] Davis, Ta, Direct Methods for Sparse Linear Systems (2006), Philadelphia: SIAM, Philadelphia · Zbl 1119.65021
[9] Davis, Ta; Hu, Y., The University of Florida Sparse Matrix Collection, ACM Trans. Math. Softw. (TOMS), 38, 1, 1, 1-1, 25 (2011) · Zbl 1365.65123
[10] Dohrmann, Cr, A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput., 25, 1, 246-258 (2003) · Zbl 1038.65039
[11] Farhat, C.; Lesoinne, M.; Letallec, P.; Pierson, K.; Rixen, D., FETI-DP: a dual-primal unified FETI method—part I: a faster alternative to the two-level FETI method, Int. J. Numer. Methods Eng., 50, 7, 1523-1544 (2001) · Zbl 1008.74076
[12] Farhat, C.; Mandel, J.; Roux, Fx, Optimal convergence properties of the FETI domain decomposition method, Comput. Methods Appl. Mech. Eng., 115, 3, 365-385 (1994)
[13] Farhat, C.; Roux, F-X, A method of finite element tearing and interconnecting and its parallel solution algorithm, Int. J. Numer. Methods Eng., 32, 6, 1205-1227 (1991) · Zbl 0758.65075
[14] Filelis-Papadopoulos, Christos K.; Gravvanis, George A., GENERIC APPROXIMATE SPARSE INVERSE MATRIX TECHNIQUES, International Journal of Computational Methods, 11, 6, 1350084 (2014) · Zbl 1359.65042
[15] Filelis-Papadopoulos, Ck; Gravvanis, Ga, A class of generic factored and multi-level recursive approximate inverse techniques for solving general sparse systems, Eng. Comput., 33, 1, 74-99 (2016)
[16] Giraud, L.; Haidar, A.; Saad, Y., Sparse approximations of the Schur complement for parallel algebraic hybrid solvers in 3D, Numerical Mathematics Theory, Methods and Applications, 3, 3, 276-294 (2010) · Zbl 1240.65093
[17] Golub, G., Van Loan, C.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037
[18] Gropp, W.; Lusk, E.; Skjellum, A., Using MPI: Portable Parallel Programming with the Message-Passing Interface, vol. 1 (1999), Cambridge: MIT Press, Cambridge
[19] Grote, Mj; Huckle, T., Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18, 3, 838-853 (1997) · Zbl 0872.65031
[20] Henson, Ve; Yang, Um, BoomerAMG: a parallel algebraic multigrid solver and preconditioner, Appl. Numer. Math., 41, 155-177 (2000) · Zbl 0995.65128
[21] Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20, 1, 359-392 (1998) · Zbl 0915.68129
[22] Karypis, G.; Kumar, V., Multilevel k-way partitioning scheme for irregular graphs, J. Parallel Distrib. Comput., 48, 1, 96-129 (1998) · Zbl 0918.68073
[23] Klawonn, A.; Rheinbach, O., Highly scalable parallel domain decomposition methods with an application to biomechanics, ZAMM - J. Appl. Math. Mech. / Z. Angew. Math. Mech., 90, 1, 5-32 (2010) · Zbl 1355.65169
[24] Lawson, Cl; Hanson, Rj; Kincaid, Dr; Krogh, Ft, Basic Linear Algebra Subprograms for Fortran usage, ACM Trans. Math. Softw. (TOMS), 5, 3, 308-323 (1979) · Zbl 0412.65022
[25] Li, R.; Saad, Y., Low-rank correction methods for algebraic domain decomposition preconditioners, SIAM J. Matrix Anal. Appl., 38, 3, 807-828 (2017) · Zbl 1371.65029
[26] Li, R.; Xi, Y.; Saad, Y., Schur complement-based domain decomposition preconditioners with low-rank corrections, Numerical Linear Algebra with Applications, 23, 4, 706-729 (2016) · Zbl 1399.65238
[27] Li, Z.; Saad, Y., SchurRAS: a restricted version of the overlapping Schur complement preconditioner, SIAM J. Sci. Comput., 27, 5, 1787-1801 (2006) · Zbl 1099.65034
[28] Mandel, J., Balancing domain decomposition, Commun. Numer. Methods Eng., 9, 3, 233-241 (1993) · Zbl 0796.65126
[29] Manguoglu, M., A domain-decomposing parallel sparse linear system solver, J. Comput. Appl. Math., 236, 3, 319-325 (2011) · Zbl 1228.65051
[30] Mathew, T., Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations, vol. 61 (2008), Berlin: Springer Science & Business Media, Berlin · Zbl 1147.65101
[31] Moutafis, Be; Filelis-Papadopoulos, Ck; Gravvanis, Ga, Parallel multi-projection preconditioned methods based on semi-aggregation techniques, Journal of Computational Science, 22, 45-54 (2017)
[32] Naumov, M.; Manguoglu, M.; Sameh, Ah, A tearing-based hybrid parallel sparse linear system solver, J. Comput. Appl. Math., 234, 10, 3025-3038 (2010) · Zbl 1193.65029
[33] Polizzi, E.; Sameh, Ah, A parallel hybrid banded system solver: the SPIKE algorithm, Parallel Comput., 32, 2, 177-194 (2006)
[34] Pothen, A.; Fan, C-J, Computing the block triangular form of a sparse matrix, ACM Trans. Math. Softw. (TOMS), 16, 4, 303-324 (1990) · Zbl 0900.65117
[35] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Philadelphia: SIAM, Philadelphia · Zbl 1031.65046
[36] Saad, Y.; Schultz, Mh, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869 (1986) · Zbl 0599.65018
[37] Schenk, O.; Gärtner, K.; Fichtner, W., Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors, BIT Numer. Math., 40, 1, 158-176 (2000) · Zbl 0957.65016
[38] Schenk, O.; Gärtner, K., Solving unsymmetric sparse systems of linear equations with PARDISO, Futur. Gener. Comput. Syst., 20, 3, 475-487 (2004) · Zbl 1062.65035
[39] Smith, B.; Bjorstad, P.; Gropp, W., Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 0857.65126
[40] Toselli, A.; Widlund, Ob, Domain Decomposition Methods: Algorithms and Theory, vol. 34 (2005), Berlin: Springer, Berlin · Zbl 1069.65138
[41] Van Der Vorst, Ha, Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13, 2, 631-644 (1992) · Zbl 0761.65023
[42] Van Der Vorst, Ha, Iterative Krylov Methods for Large Linear Systems, vol. 13 (2003), Cambridge: Cambridge University Press, Cambridge · Zbl 1023.65027
[43] Zhu, Y.; Sameh, Ah, PSPIKE+: a family of parallel hybrid sparse linear system solvers, J. Comput. Appl. Math., 311, Supplement C, 682-703 (2017) · Zbl 1355.65056
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.