×

Robust preconditioners via generalized eigenproblems for hybrid sparse linear solvers. (English) Zbl 1411.65042

Summary: The solution of large sparse linear systems is one of the most time consuming kernels in many numerical simulations. The domain decomposition community has developed many efficient and robust methods in the last decades. While many of these solvers fall into the abstract Schwarz (aS) framework, their robustness was originally demonstrated on a case-by-case basis. In this paper, we propose a bound for the condition number of all deflated aS methods provided that the coarse grid consists of the assembly of local components that contain the kernel of some local operators. We show that classical results from the literature on particular instances of aS methods can be retrieved from this bound. We then show that such a coarse grid correction can be explicitly obtained algebraically via generalized eigenproblems, leading to a condition number independent of the number of domains. This result can be readily applied to retrieve or improve the bounds previously obtained via generalized eigenproblems in the particular cases of Neumann-Neumann (NN), additive Schwarz (AS), and optimized Robin, but it also generalizes them when applied with approximate local solvers. Interestingly, the proposed methodology turns out to be a comparison of the considered particular aS method with generalized versions of both NN and AS for tackling the lower and upper part of the spectrum, respectively. We furthermore show that the application of the considered grid corrections in an additive fashion is robust in the AS case although it is not robust for aS methods in general. In particular, the proposed framework allows for ensuring the robustness of the AS method applied on the Schur complement, either with deflation or additively, and with the freedom of relying on an approximate local Schur complement. Numerical experiments illustrate these statements.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65Y05 Parallel numerical computation

Software:

METIS; MUMPS; PaStiX
Full Text: DOI

References:

[1] E. Agullo, E. Darve, L. Giraud, and Y. Harness, {Low-rank factorizations in data sparse hierarchical algorithms for preconditioning symmetric positive definite matrices}, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1701-1725. · Zbl 1453.65061
[2] E. Agullo, L. Giraud, A. Guermouche, and J. Roman, {Parallel hierarchical hybrid linear solvers for emerging computing platforms}, C. R. Méc., 339 (2011), pp. 96-103, . · Zbl 1225.65036
[3] E. Agullo, L. Giraud, S. Nakov, and J. Roman, {Hierarchical Hybrid Sparse Linear Solver for Multicore Platforms}, Report, INRIA Bordeaux, 2016; also available online from .
[4] P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent, and J. Koster, {A fully asynchronous multifrontal solver using distributed dynamic scheduling}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15-41. · Zbl 0992.65018
[5] S. C. Brenner, {The condition number of the Schur complement in domain decomposition}, Numer. Math., 83 (1999), pp. 187-203. · Zbl 0936.65141
[6] L. M. Carvalho, L. Giraud, and G. Meurant, {Local preconditioners for two-level non-overlapping domain decomposition methods}, Numer. Linear Algebra Appl., 8 (2001), pp. 207-227. · Zbl 1051.65051
[7] B. Cockburn, J. Gopalakrishnan, and R. Lazarov, {Unified hybridization of discontinuous Galerkin, mixed, and continuous Galerkin methods for second order elliptic problems}, SIAM J. Numer. Anal., 47 (2009), pp. 1319-1365. · Zbl 1205.65312
[8] Y.-H. De Roeck and P. Le Tallec, {Analysis and test of a local domain decomposition preconditioner}, in Proceedings of the Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations, Vol. 4, 1991.
[9] C. R. Dohrmann, {A preconditioner for substructuring based on constrained energy minimization}, SIAM J. Sci. Comput., 25 (2003), pp. 246-258. · Zbl 1038.65039
[10] V. Dolean, P. Jolivet, and F. Nataf, {An Introduction to Domain Decomposition Methods: Algorithms, Theory, and Parallel Implementation}, Vol. 144, SIAM, Philadelphia, 2015. · Zbl 1364.65277
[11] Y. Efendiev, J. Galvis, R. Lazarov, and J. Willems, {Robust domain decomposition preconditioners for abstract symmetric positive definite bilinear forms}, ESAIM Math. Model. Numer. Anal., 46 (2012), pp. 1175-1199; also available online from . · Zbl 1272.65098
[12] C. Farhat, M. Lesoinne, P. LeTallec, K. Pierson, and D. Rixen, {FETI-DP: A dual\textendashprimal unified FETI method–Part I: A faster alternative to the two-level FETI method}, Internat. J. Numer. Methods Engrg., 50 (2001), pp. 1523-1544. · Zbl 1008.74076
[13] C. Farhat and F.-X. Roux, {A method of finite element tearing and interconnecting and its parallel solution algorithm}, Internat. J. Numer. Methods Engrg., 32 (1991), pp. 1205-1227. · Zbl 0758.65075
[14] V. Frayssé and L. Giraud, {A Set of Conjugate Gradient Routines for Real and Complex Arithmetics}, CERFACS technical report TR/PA/00/47, 2000.
[15] J. Galvis and Y. Efendiev, {Domain decomposition preconditioners for multiscale flows in high-contrast media}, Multiscale Model. Simul., 8 (2010), pp. 1461-1483, . · Zbl 1206.76042
[16] M. J. Gander, {Optimized Schwarz methods}, SIAM J. Numer. Anal., 44 (2006), pp. 699-731. · Zbl 1117.65165
[17] L. Grasedyck and W. Hackbusch, {Construction and arithmetics of H-matrices}, Computing, 70 (2003), pp. 295-334, . · Zbl 1030.65033
[18] R. Haferssas, P. Jolivet, and F. Nataf, {An additive Schwarz method type theory for Lions’s algorithm and a symmetrized optimized restricted additive Schwarz method}, SIAM J. Sci. Comput., 39 (2017), pp. A1345-A1365. · Zbl 1371.65129
[19] P. Hénon, P. Ramet, and J. Roman, {PASTIX: A high-performance parallel direct solver for sparse symmetric positive definite systems}, Parallel Comput., 28 (2002), pp. 301-321. · Zbl 0984.68208
[20] P. Jolivet, F. Hecht, F. Nataf, and C. Prud’homme, {Scalable domain decomposition preconditioners for heterogeneous elliptic problems}, in Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, ACM, New York, 2013, pp. 1-11, .
[21] G. Karypis and V. Kumar, {MeTis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4.0}, 2009, .
[22] A. Klawonn, M. Kuhn, and O. Rheinbach, {Adaptive coarse spaces for FETI-DP in three dimensions}, SIAM J. Sci. Comput., 38 (2016), pp. A2880-A2911. · Zbl 1346.74168
[23] A. Klawonn, M. Kühn, and O. Rheinbach, {Adaptive FETI-DP and BDDC methods with a generalized transformation of basis for heterogeneous problems}, Electron. Trans. Numer. Anal., 49 (2018), pp. 1-27. · Zbl 1448.65236
[24] A. Klawonn, P. Radtke, and O. Rheinbach, {A comparison of adaptive coarse spaces for iterative substructuring in two dimensions}, Electron. Trans. Numer. Anal., 45 (2016), pp. 75-106. · Zbl 1338.65084
[25] P. Le Tallec and M. Vidrascu, {Generalized Neumann-Neumann preconditioners for iterative substructuring}, in Proceedings of the Ninth International Symposium on Domain Decomposition Methods in Sciences and Engineering, 1998.
[26] J. Mandel, {Balancing domain decomposition}, Internat. J. Numer. Methods Biomed. Engrg., 9 (1993), pp. 233-241. · Zbl 0796.65126
[27] L. Mansfield, {On the conjugate gradient solution of the Schur complement system obtained from domain decomposition}, SIAM J. Numer. Anal., 27 (1990), pp. 1612-1620, . · Zbl 0722.65059
[28] T. P. A. Mathew, {Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations}, Lect. Notes Comput. Sci. Eng. 61, Springer, New York, 2008. · Zbl 1147.65101
[29] F. Nataf, H. Xiang, V. Dolean, and N. Spillane, {A coarse space construction based on local Dirichlet-to-Neumann maps}, SIAM J. Sci. Comput., 33 (2011), pp. 1623-1642, . · Zbl 1230.65134
[30] A. Quarteroni and A. Valli, {Domain Decomposition Methods for Partial Differential Equations}, Oxford University Press, Oxford, 1999. · Zbl 0931.65118
[31] M. Sarkis, {Partition of unity coarse spaces: Enhanced versions, discontinuous coefficients and applications to elasticity}, in Domain Decomposition Methods in Science and Engineering, Springer, New York, 2003, pp. 149-158.
[32] N. Spillane, {Méthodes de Décomposition de Domaine Robustes Pour Les Problèmes Symétriques Définis Positifs}, Ph.D. thesis, Université Pierre et Marie Curie, Paris, 2014.
[33] N. Spillane, V. Dolean, P. Hauret, F. Nataf, C. Pechstein, and R. Scheichl, {Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps}, Numer. Math., 126 (2014), pp. 741-770, . · Zbl 1291.65109
[34] N. Spillane and D. J. Rixen, {Automatic spectral coarse spaces for robust finite element tearing and interconnecting and balanced domain decomposition algorithms}, Internat. J. Numer. Methods Engrg., 95 (2013), pp. 953-990, . · Zbl 1352.65553
[35] A. Toselli and O. Widlund, {Domain Decomposition Methods–Algorithms and Theory}, Springer Ser. Comput. Math. 34, Springer, New York, 2006. · Zbl 1069.65138
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.