×

Local Fourier analysis of balancing domain decomposition by constraints algorithms. (English) Zbl 1425.65135

Summary: Local Fourier analysis is a commonly used tool for the analysis of multigrid and other multilevel algorithms, providing both insight into observed convergence rates and predictive analysis of the performance of many algorithms. In this paper, for the first time, we adapt local Fourier analysis to examine variants of two- and three-level balancing domain decomposition by constraints (BDDC) algorithms, to better understand the eigenvalue distributions and condition number bounds on these preconditioned operators. This adaptation is based on a modified choice of basis for the space of Fourier harmonics that greatly simplifies the application of local Fourier analysis in this setting. The local Fourier analysis is validated by considering the two-dimensional Laplacian and predicting the condition numbers of the preconditioned operators with different sizes of subdomains. Several variants are analyzed, showing that the two- and three-level performance of the “lumped” variant can be greatly improved when used in multiplicative combination with a weighted diagonal scaling preconditioner, with weight optimized through the use of local Fourier analysis.

MSC:

65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Badia, A. F. Martín, and J. Principe, FEMPAR: An object-oriented parallel finite element framework, Arch. Comput. Methods Eng., 25 (2018), pp. 195-271. · Zbl 1392.65005
[2] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, A. Dener, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, D. A. May, L. C. McInnes, R. T. Mills, T. Munson, K. Rupp, P. Sanan, B. F. Smith, S. Zampini, H. Zhang, and H. Zhang, PETSc users manual: Revision 3.10, Techncal report ANL-95/11 - Rev 3.10, Argonne National Laboratory, Argonne, IL, 2018.
[3] M. Bolten and H. Rittich, Fourier analysis of periodic stencils in multigrid methods, SIAM J. Sci. Comput., 40 (2018), pp. A1642-A1668. · Zbl 1402.65175
[4] T. Boonen, J. Van Lent, and S. Vandewalle, Local Fourier analysis of multigrid for the curl-curl equation, SIAM J. Sci. Comput., 30 (2008), pp. 1730-1755. · Zbl 1168.65422
[5] J. H. Bramble, J. E. Pasciak, J. P. Wang, and J. Xu, Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comp., 57 (1991), pp. 1-21. · Zbl 0754.65085
[6] A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp., 31 (1977), pp. 333-390. · Zbl 0373.65054
[7] S. C. Brenner, E.-H. Park, and L.-Y. Sung, A BDDC preconditioner for a symmetric interior penalty Galerkin method, Electron. Trans. Numer. Anal., 46 (2017), pp. 190-214. · Zbl 1368.65230
[8] S. C. Brenner and L.-Y. Sung, BDDC and FETI-DP without matrices or vectors, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1429-1435. · Zbl 1173.65363
[9] W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, SIAM, Philadelphia, 2000. · Zbl 0958.65128
[10] C. R. Dohrmann, A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput., 25 (2003), pp. 246-258. · Zbl 1038.65039
[11] C. R. Dohrmann, Preconditioning of saddle point systems by substructuring and a penalty approach, in Domain Decomposition Methods in Science and Engineering XVI, Lecture Notes Comput. Sci. Eng. 55, Springer, Berlin, 2007, pp. 53-64.
[12] C. R. Dohrmann and O. B. Widlund, A BDDC algorithm with deluxe scaling for three-dimensional \(H({curl})\) problems, Commun. Pure Appl. Math., 69 (2016), pp. 745-770. · Zbl 1343.65136
[13] V. Dolean, P. Jolivet, and F. Nataf, An introduction to domain decomposition methods: Algorithms, theory, and parallel implementation, SIAM, Philadelphia, 2015. · Zbl 1364.65277
[14] M. Dryja, J. Galvis, and M. Sarkis, BDDC methods for discontinuous Galerkin discretization of elliptic problems, J. Complexity, 23 (2007), pp. 715-739. · Zbl 1133.65097
[15] M. Dryja and O. B. Widlund, Towards a unified theory of domain decomposition algorithms for elliptic problems, in Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989), SIAM, Philadelphia, 1990, pp. 3-21.
[16] M. Dryja and O. B. Widlund, A FETI-DP method for a mortar discretization of elliptic problems, Recent Developments in Domain Description Methods, Lect. Notes Comput. Sci. Eng. 23, Springer, Berlin, 2002, pp. 41-52. · Zbl 1007.65094
[17] C. Farhat, M. Lesoinne, P. LeTallec, K. Pierson, and D. Rixen, FETI-DP: A dual-primal 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
[18] S. Friedhoff and S. MacLachlan, A generalized predictive analysis tool for multigrid methods, Numer. Linear Algebra Appl., 22 (2015), pp. 618-647. · Zbl 1349.65427
[19] S. Friedhoff, S. MacLachlan, and C. Börgers, Local Fourier analysis of space-time relaxation and multigrid schemes, SIAM J. Sci. Comput., 35 (2013), pp. S250-S276. · Zbl 1281.65127
[20] M. J. Gander, F. Magoulès, and F. Nataf, Optimized Schwarz methods without overlap for the Helmholtz equation, SIAM J. Sci. Comput., 24 (2002), pp. 38-60. · Zbl 1021.65061
[21] P. Kumar, C. Rodrigo, F. J. Gaspar, and C. W. Oosterlee, On local Fourier analysis of multigrid methods for PDEs with jumping and random coefficients, SIAM J. Sci. Comput., 41 (2019), pp. A1385-A1413. · Zbl 1435.65053
[22] C.-C. J. Kuo and B. C. Levy, Two-color Fourier analysis of the multigrid method with red-black Gauss-Seidel smoothing, Appl. Math. Comput., 29 (1989), pp. 69-87. · Zbl 0663.65104
[23] J. Li, A dual-primal FETI method for incompressible Stokes equations, Numer. Math., 102 (2005), pp. 257-275. · Zbl 1185.76813
[24] J. Li and O. Widlund, BDDC algorithms for incompressible Stokes equations, SIAM J. Numer. Anal., 44 (2006), pp. 2432-2455. · Zbl 1233.76077
[25] J. Li and O. Widlund, FETI-DP, BDDC, and block Cholesky methods, Internat. J. Numer. Methods Engrg., 66 (2006), pp. 250-271.
[26] J. Li and O. Widlund, A BDDC preconditioner for saddle point problems, in Domain Decomposition Methods in Science and Engineering XVI, Lect. Notes Comput. Sci. Eng. 55, Springer, Berlin, 2007, pp. 413-420.
[27] J. Li and O. Widlund, On the use of inexact subdomain solvers for BDDC algorithms, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1415-1428. · Zbl 1173.65365
[28] S. P. MacLachlan and C. W. Oosterlee, Local Fourier analysis for multigrid with overlapping smoothers applied to systems of PDEs, Numer. Linear Algebra Appl., 18 (2011), pp. 751-774. · Zbl 1265.65256
[29] J. Mandel and C. R. Dohrmann, Convergence of a balancing domain decomposition by constraints and energy minimization, Numer. Linear Algebra Appl., 10 (2003), pp. 639-659. · Zbl 1071.65558
[30] J. Mandel, C. R. Dohrmann, and R. Tezaur, An algebraic theory for primal and dual substructuring methods by constraints, Appl. Numer. Math., 54 (2005), pp. 167-193. · Zbl 1076.65100
[31] J. Mandel, B. r. Sousedík, and C. R. Dohrmann, Multispace and multilevel BDDC, Computing, 83 (2008), pp. 55-85.
[32] L. F. Pavarino, O. B. Widlund, and S. Zampini, BDDC preconditioners for spectral element discretizations of almost incompressible elasticity in three dimensions, SIAM J. Sci. Comput., 32 (2010), pp. 3604-3626. · Zbl 1278.74058
[33] C. Rodrigo, F. J. Gaspar, and F. J. Lisbona, Multicolor Fourier analysis of the multigrid method for quadratic FEM discretizations, Appl. Math. Comput., 218 (2012), pp. 11182-11195. · Zbl 1280.65139
[34] B. Sousedík, J. Šístek, and J. Mandel, Adaptive-multilevel BDDC and its parallel implementation, Computing, 95 (2013), pp. 1087-1119. · Zbl 1307.65175
[35] K. Stüben and U. Trottenberg, Multigrid methods: Fundamental algorithms, model problem analysis and applications, in Multigrid Methods, Lecture Notes in Math. 960, 1982, pp. 1-176.
[36] A. Toselli and O. Widlund, Domain Decomposition Methods: Algorithms and Theory, Springer Ser. Comput. Math. 34, Springer, Berlin, 2005. · Zbl 1069.65138
[37] U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, San Diego, CA, 2001.
[38] X. Tu, Domain Decomposition Algorithms: Methods with Three Levels and for Flow in Porous Media, Ph.D. thesis, New York University, New York, 2006.
[39] X. Tu, Three-level BDDC in three dimensions, SIAM J. Sci. Comput., 29 (2007), pp. 1759-1780. · Zbl 1163.65094
[40] X. Tu, Three-level BDDC in two dimensions, Internat. J. Numer. Methods Engrg., 69 (2007), pp. 33-59. · Zbl 1134.65087
[41] P. Wesseling, An introduction to multigrid methods, Pure Appl. Math., Wiley, Chichester, England, 1992. · Zbl 0760.65092
[42] R. Wienands and W. Joppich, Practical Fourier Analysis for Multigrid Methods, CRC Press, Boca Raton, FL, 2004. · Zbl 1062.65133
[43] S. Zampini, PCBDDC: A class of robust dual-primal methods in PETSc, SIAM J. Sci. Comput., 38 (2016), pp. S282-S306. · Zbl 1352.65632
[44] S. Zampini and X. Tu, Multilevel balancing domain decomposition by constraints deluxe algorithms with adaptive coarse spaces for flow in porous media, SIAM J. Sci. Comput., 39 (2017), pp. A1389-A1415. · Zbl 1426.76582
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.