On domain decomposition preconditioner of BPS type for finite element discretizations of 3D elliptic equations

V. G. Korneev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 9

Résumé

BPS is a well known an efficient and rather general domain decomposition Dirichlet-Dirichlet type preconditioner, suggested in the famous series of papers Bramble, Pasciak and Schatz (1986–1989). Since then, it has been serving as the origin for the whole family of domain decomposition Dirichlet-Dirichlet type preconditioners-solvers as for $h$ so $hp$ discretizations of elliptic problems. For its original version, designed for $h$ discretizations, the named authors proved the bound $O(1+\log^2H/h)$ for the relative condition number under some restricting conditions on the domain decomposition and finite element discretization. Here $H/h$ is the maximal relation of the characteristic size H of a decomposition subdomain to the mesh parameter $h$ of its discretization. It was assumed that subdomains are images of the reference unite cube by trilinear mappings. Later similar bounds related to $h$ discretizations were proved for more general domain decompositions, defined by means of coarse tetrahedral meshes. These results, accompanied by the development of some special tools of analysis aimed at such type of decompositions, were summarized in the book of Toselli and Widlund (2005). This paper is also confined to $h$ discretizations. We further expand the range of admissible domain decompositions for constructing BPS preconditioners, in which decomposition subdomains can be convex polyhedrons, satisfying some conditions of shape regularity. We prove the bound for the relative condition number with the same dependence on $H/h$ as in the bound given above. Along the way to this result, we simplify the proof of the so called abstract bound for the relative condition number of the domain decomposition preconditioner. In the part, related to the analysis of the interface sub-problem preconditioning, our technical tools are generalization of those used by Bramble, Pasciak and Schatz.

Bibliographie

[1] O. Axelsson, P. S. Vassilevskii, “Algebraic Multilevel Preconditioning Methods”, SIAM J. Numer. Anal., 56 (157–177), 1989 | MR | Zbl

[2] P. E. Bjørstad, J. Mandel, “On the Spectra of Sums of Orthogonal Projections with Applications to Parallel Computing”, BIT, 31 (1991), 76–88 | DOI | MR

[3] J. H. Bramble, J. E. Pasciak, A. H. Schatz, “The Construction of Preconditioners for Elliptic Problems by Substructuring, I”, Math. Comput., 47(175) (1986), 103–134 | DOI | MR | Zbl

[4] J. H. Bramble, J. E. Pasciak, A. H. Schatz, “The Construction of Preconditioners for Elliptic Problems by Substructuring, II”, Math. Comput., 49(179) (1987), 1–16 | DOI | MR | Zbl

[5] J. H. Bramble, J. E. Pasciak, A. H. Schatz, “The Construction of Preconditioners for Elliptic Problems by Substructuring, III”, Math. Comput., 51(184) (1988), 415–430 | MR | Zbl

[6] J. H. Bramble, J. E. Pasciak, A. H. Schatz, “The Construction of Preconditioners for Elliptic Problems by Substructuring, IV”, Math. Comput., 53(187) (1989), 1–24 | MR | Zbl

[7] J. H. Bramble, J. E. Pasciak, J. Xu, “Parallel Multilevel Preconditioners”, Math. Comput., 55 (1990), 1–22 | DOI | MR | Zbl

[8] J. H. Bramble, J. Xu, “Some Estimates for a Weighted $L^2$ Projections”, Math. Comput., 50 (1991), 463–476 | MR

[9] J. H. Bramble, X. Zhang, “The Analysis of Multigrid Methods”, Handbook of Numerical Analysis, VII, North-Holland, Amsterdam, 2000, 173–415 | DOI | MR | Zbl

[10] M. A. Casarin, “Quasi-Optimal Schwarz Methods for the Conforming Spectral Element Discretization”, SIAM J. Numer. Anal., 34 (1997), 2482–2502 | DOI | MR | Zbl

[11] T. F. Chan, T. P. Mathew, “Domain Decomposition Algorithms”, Acta Numer., 1994, 61–143 | DOI | MR | Zbl

[12] P. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, 1978 | MR | Zbl

[13] Ph. Clement, “Approximation by Finite Element Functions Using Local Regularizations”, Rev. Franc. Aitomat. Inf. Recherche Oper. Ser. Rouge Anal. Numer., 9:2 (2002), 77–84 | MR

[14] G. Haase, U. Langer, A. Meyer, “The Approximate Dirichlet Domain Decomposition Method. I; II”, Computing, 47 (1991), 137–167 | DOI | MR

[15] G. Haase, U. Langef, A. Meyer, S. V. Nepomnyaschikh, “Hierarchical Extension Operators and Local Multigrid Methods in Domain Decomposition Preconditioners”, East-West J. Numer. Math., 2 (1994), 173–193 | MR | Zbl

[16] G. Haase, S. V. Nepomnyaschikh, “Extension Explicit Operators on Hierarchical Grids”, East-West J. Numer. Math., 5 (1997), 231–248 | MR | Zbl

[17] M. Jung, U. Langer, “Application of Multilevel Methods to Practical Problems”, Surv. Math. Ind., 1 (1991), 217–257 | MR | Zbl

[18] M. Jung, U. Langer, A. Meyer, W. Queck, M. Schneider, “Multigrid Preconditioning and Their Application”, Proceedings of the 3rd GDR Multigrid Seminar (Biesenthal, May 2–6, 1988), 11–52 ; Report R-Math03/89, Karl-Weierstrass-Inst. Math., Berlin, 1989 | MR

[19] V. Korneev, Finite Element Methods of High Orders of Accuracy, Leningr. Gos. Univ., Leningrad, 1977 (in Russian) | MR | Zbl

[20] V. Korneev, U. Langer, “Domain Decomposition Methods and Preconditioning”, Encyclopedia of Computational Mechanics, v. 1, eds. E. Stein, R. de Borst, Th. J. R. Hudges, Wiley, New York, 2004, 617–647

[21] V. Korneev, U. Langer, L. Xanthis, “On Fast Domain Decomposition Solving Procedures for $hp$-Discretizations of 3D Elliptic Problems”, Comput. Methods Appl. Math., 3 (2003), 536–559 | MR | Zbl

[22] V. Korneev, U. Langer, L. Xanthis, “Fast Adaptive Domain Decomposition Algorithms for $hp$-Discretizations of 2D and 3D Elliptic Equations: Recent Advances”, Int. J. Comput. Math. Appl., 4 (2003), 27–44 | Zbl

[23] V. Korneev, U. Langer, L. Xanthis, “Fast Adaptive Domain Decomposition Algorithms for $hp$-Discretizations of 2D and 3D Elliptic Equations: Recent Advances”, Proceedings of HERCMA 2003, v. 1, ed. E. A. Lipitakis, LEA, Athens, 2003, 23–36

[24] V. Korneev, A. Rytov, “On the Interrelation between Fast Solvers for Spectral and Hierarchical $p$ Elements”, Int. J. Comput. Math. Appl., 6 (2005), 99–113

[25] V. Korneev, A. Rytov, “On Existence of the Essential Interrelation between Spectral and Hierarchical Elements”, Proceedings of the 6th All-Russia Seminar on Mesh Methods for Boundary Value Problems and Applications, Kazan. Gos. Univ., Kazan, 2005, 141–150

[26] V. Korneev, A. Rytov, “Fast Domain Decomposition Algorithm for Discretizations of 3d Elliptic Equations by Spectral Elements”, Comput. Methods Appl. Mech. Eng., 197 (2008), 1433–1446 | DOI | MR | Zbl

[27] V. I. Lebedev, V. I. Agoshkov, Poincare–Steklov Operators and Their Applications in Analysis, Otd. Vychisl. Mat., Akad. Nauk SSSR, Moscow, 1983 (in Russian) | MR

[28] P. Le Tallec, “Domain Decomposition Methods in Computational Mechanics”, Computational Mechanics Advances, ed. J. T. Oden, North-Holland, Amsterdam, 121–220 | MR

[29] J.-L. Lions, “On the Schwarz Alternating Methods, I”, First International Symposium on Domain Decomposition Methods for Partial Differential Equations, eds. R. Glowinski, G. H. Golub, G. A. Meurant, J. Periaux, SIAM, Philadelphia, PA, 1988, 1–42 | MR

[30] A. M. Matsokin, S. V. Nepomnyaschikh, “A Schwarz Alternating Method in a Subspace”, Sov. Math., 29:10 (1985), 78–84 | MR | Zbl

[31] V. G. Mazy'a, Sobolev Spaces, Springer-Verlag, Berlin, 1985 | MR

[32] J. Neas, I. Hlavaek, Mathematical Theory of Elastic and Elastoplastic Bodies: An Introduction, Elsevier Scientific, Amsterdam, 1980

[33] S. V. Nepomnyaschikh, “Mesh Theorems on Traces, Normalizations of Function Traces and Their Inversion”, Russ. J. Numer. Anal. Math. Model., 6 (1991), 223–242 | MR | Zbl

[34] L. F. Pavarino, O. B. Widlund, “Potylogarithmic Bound for an Iterative Substructuring Method for Spectral Elements in Three Dimensions”, SIAM J. Numer. Anal., 37 (1996), 1303–1335 | DOI | MR

[35] L. F. Pavarino, O. B. Widlund, “Iterative Substructuring Methods for spectral Element Discretizations of Elliptic Systems. I: Compressible Linear Elasticity”, SIAM J. Numer. Anal., 37 (1999), 353–374 | DOI | MR

[36] L. F. Pavarino, O. B. Widlund, “Iterative Substructuring Methods for Spectral Element Discretizations of Elliptic Systems. II: Mixed Methods for Linear Elasticity and Stokes Now”, SIAM J. Numer. Anal., 37 (1999), 375–402 | DOI | MR

[37] A. Quarteroni, A. Vali, Domain Decomposition Methods for Partial Differential Equations, Oxford Science, Oxford, 1999 | Zbl

[38] L. Scott, S. Zhang, “Finite Element Interpolation of Nonsmooth Functions Satisfying Boundary Conditions”, Math. Comput., 54 (1990), 483–493 | DOI | MR | Zbl

[39] B. Smith, P. Bjørstad, W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge Univ. Press, Cambridge, 1996 | MR

[40] A. Toselli, O. Widlund, Domain Decomposition Methods-Algorithms and Theory, Springer-Verlag, New York, 2005 | MR | Zbl

[41] H. Yserentant, “The Preconditioner Based on Multilevel Splitting of Finite Element Spaces”, Numer. Math., 58:2 (1990), 163–184 | DOI | MR | Zbl

[42] J. Xu, “The Error Analysis and the Improved Algorithms for Infinite Elements”, Proceedings of DD5 International Conference (Beijing, China, 1985), 326–331 | MR

[43] J. Xu, PhD Thesis, Cornell, 1989

[44] J. Xu, “Iterative Methods by Space Decomposition and Subspace Correction: A Unifying Approach”, SIAM Rev., 34 (1992), 581–613 | DOI | MR | Zbl

[45] J. Zou, J. Xu, “Some Nonoverlapping Domain Decomposition Methods”, SIAM Rev., 40 (1998), 857–914 | DOI | MR | Zbl

[46] X. Zhang, PhD Thesis, Courant Institute of Mathematical Science, New York, 1991

[47] X. Zhang, “Multilevel Schwarz Methods”, Numer. Math., 63 (1992), 521–539 | DOI | MR | Zbl