$hp$-version additive Schwarz algorithms on triangular meshes

V. G. Korneev ; J. E. Flaherty ; T. Oden ; J. Fish

Matematičeskoe modelirovanie, Tome 14 (2002) no. 2, pp. 61-94.

Résumé

Domain decomposition Dirichlet–Dirichlet solvers for $hp$-version finite element methods on angular quasiuniform triangular meshes are studied under different assumptions on a reference element. The edge coordinate functions of a reference element are allowed to be either nodal, with special choices of nodes, or hierarchical polynomials of several types. In relation to the definition of these coordinate functions within the elements, we also distinguish two cases: arbitrary and so-called discrete quasiharmonic coordinate functions. The latter are obtained by means of explicitely given and nonexpensive prolongation operators. In all these situations, we are able to suggest preconditioners which are spectrally equivalent or almost spectrally equivalent to the global stiffness matrix, which require only element-by-element and edge-by-edge operations, thus, providing a high level of parallelization. They also considerably reduce the computational cost. In our domain decomposition algorithms, we essentially use prolongation operators in the polynomial spaces from the interface boundary inside subdomains of the decomposition following the approach initially used by S. Ivanov and V. Korneev for the $hp$-version with quadrilateral elements.

Bibliographie

[1] I. Babuška, M. Suri, “The $h-p$-version of the finite, element method with quasiuniform meshes”, Model. Math. et Anal. Numer., 21 (1987), 199–238 | MR | Zbl

[2] B. A. Szabo, I. Babuška, Finite Element Analysis, Wiley Interscience, New York, 1987

[3] L. Demkowicz, J. T. Oden, W. Rackowicz, O. Hardy, “Toward a universal $hp$ adaptive finite element strategy. Part 1. Constrained Approximation and data structure”, Comput. Methods Appl. Mech. Engrg., 77 (1989), 79–112 | DOI | MR | Zbl

[4] W. Rackowicz, J. T. Oden, L. Demkowicz, “Toward a universal $hp$ adaptive finite element strategy. Part 3. Design of $hp$ meshes”, Comput. Methods Appl. Mech. Engrg., 77 (1989), 181–212 | DOI | MR

[5] Ch. Schwab, $p$- and $ph$-Finite element Methods Theory and Applicatons in Solid and Fluid Mechanics, Clarendon Press, Oxford, 1998 | MR | Zbl

[6] J. Bramble, J. Pasciak, A. Schatz, “The construction of preconditioners for elliptic problems by substructuring, I”, Math. Comp., 47 (1986), 103–134 | DOI | MR | Zbl

[7] J. Bramble, J. Pasciak, A. Schatz, “The construction of preconditioners for elliptic problems by substructuring, IV”, Math. Comp., 53 (1989), 1–24 | DOI | MR | Zbl

[8] A. M. Matsokin, S. V. Nepomnyaschikh, “Alterniruyuschii metod Shvartsa v podprostranstve”, Izv. vuzov. Matem., 1985, no. 10, 61–66 | MR | Zbl

[9] S. V. Nepomnyaschikh, “Method of splitting into subspaces for solving elliptic boundary value problems in complex-form domains. Russian (cont. Sov.)”, J. Numer. Anal. Math. Model., 6 (1991), 151–168 | DOI | MR | Zbl

[10] O. B. Widlund, “Iterative substructuring methods: Algorithms and theory for elliptic problems in plane”, First International Symposium on Domain Decomposition Methods for Partial Differential Equations, eds. R. Glowinski et al., Philadelphia, PA, 1988, 113–128 | MR | Zbl

[11] P. L. Lions, On the Schwarz alternating methods. I. Domain Decomposition Methods for Partial Differential Equations, eds. R. Glowinski et al., SIAM, Philadelphia, 1988 | MR | Zbl

[12] I. Babuška, A. Craig, J. Mandel, J. Pitkäranta, “Efficient preconditioning for the inversion finite element method in two dimensions”, SIAM J. Numer. Anal., 28:3 (1991), 624–661 | DOI | MR | Zbl

[13] J. T. Oden, A. Patra, Y. S. Feng, “Domain decomposition solver for adaptive $hp$ finite elements”, Vllth International Conference on Domain Decomposition, State College, Pennsylvania, 1993

[14] S. A. Ivanov, V. G. Korneev, On the preconditioning in the domain decomposition technique for the $p$-version finite element method. Part I. Technische Universitat Chemnitz-Zwickau, Preprint SPC 95-35, 1995 | MR

[15] S.A.Ivanov, V. G. Korneev, On the preconditioning in the domain decomposition technique for the $p$-version finite element method. Part II. Technische Universitat Chemnitz-Zwickau, Preprint SPC 95-36, 1995 | MR

[16] S. A. Ivanov, V. G. Korneev, “Preconditioning in the domain decomposition methods for the $p$-version with the hierarchical bases”, Trudy mezhdunar. konf. OFEA-95 (Peterburg, Iyun 25–29, 1995) ; Матем. моделирование, 8:9 (1996), 63–73 | MR | Zbl

[17] V. G. Korneev, S. Jensen, “Preconditioning of the $p$-version of the finite element method”, Comput. Methods Appl. Mech. Engrg., 150 (1977), 215–238 | DOI | MR

[18] V. G. Korneev, S. Ensen, “Effektivnoe predobuslovlivanie metodom dekompozitsii oblasti dlya $p$-versii s ierarkhicheskim bazisom, I”, Izv. vuzov. Matem., 1999, no. 5, 37–56 | MR | Zbl

[19] V. G. Korneev, S. Ensen, “Effektivnoe predobuslovlivanie metodom dekompozitsii oblasti dlya $p$-versii s ierarkhicheskim bazisom, II”, Izv. vuzov. Matem., 1999, no. 11, 24–40 | MR | Zbl

[20] V. G. Korneev, S. Jensen, “Domain decomposition preconditioning in the hierarchical pversion of the finite element method”, Appl. Numerical Math., 29 (1999), 479–518 | DOI | MR | Zbl

[21] M. Ainsworth, “A preconditioner based on domain decomposition for $h-p$ finite element approximation on quasi-uniform meshes”, SIAM J. Numer. Anal., 33 (1996), 1358–1376 | DOI | MR | Zbl

[22] M. Ainsworih, B. Senior, “Aspects of an adaptive $ph$-finite element method: Adaptive strategy, conforming approximation and efficient solvers”, Methods Appl. Mech. Engrg., 150 (1977), 65–87 | DOI

[23] B. Guo, W. Cao, “Inexact solvers on element surfaces for the $p$ and $h-p$ finite element method”, Comput. Methods Appl. Mech. Engrg., 150 (1997), 173–191 | DOI | MR

[24] S. A. Ivanov, V. G. Korneev, “Vybor koordinatnykh koordinatnykh funktsii vysokogo poryadka i predobuslovlivanie v ramkakh metoda dekompozitsii oblasti”, Izv. vuzov. Matem., 1995, no. 4, 62–81 | MR | Zbl

[25] J. T. O den, A. Patra, Y. S. Feng, “Parallel Domain decomposition solver for adaptive $hp$ finite element methods”, SIAM J. Num. Anal., 34 (1997), 2090–2118 | DOI | MR

[26] L. F. Pavarino, “Additive Schwartz methods for the $p$-version finite element method”, Numer. Math., 66 (1994), 493–515 | DOI | MR | Zbl

[27] O. B. Widlund, “Preconditioners for Spectral and Mortar Finite Element Methods”, Proceedings of the Eighth International Conference on Domain Decomposition Methods (Beijing, PRC, May 15–19, 1995), Wiley-Interscience, Strasbourg, France, 1996 | MR

[28] M. A. Casarin, “Quasi-optimal Schwarz methods for the conforming spectral element discretization”, SIAM J. Num. Anal., 34 (1997), 2482–2502 | DOI | MR | Zbl

[29] M. S. Shephard, S. Dey, J. E. Flaherty, “A straight-forward structure to construct shape functions for variable $p$-order meshes”, Comput. Methods Appl. Mech. Engrg., 147 (1997), 209–234 | DOI | MR

[30] R. A. Adams, Sobolev Spaces, Academic Press, New York, 1975 | MR | Zbl

[31] V. G. Korneev, Skhemy metoda konechnykh elementov vysokikh poryadkov tochnosti, Izd. Leningr. un-ta, L., 1977 | MR

[32] V. G. Korneev, “Iteratsionnye metody resheniya sistem uravnenii metoda konechnykh elementov”, Zhurnal vychisl. matem. i matem. fiz., 17:5 (1997), 109–129 | MR

[33] V. G. Korneev, “O postroenii variatsionno-raznostnykh skhem vysokikh poryadkov tochnosti”, Vestn. Leningr. un-ta, 1970, no. 19, 28–40 | MR | Zbl

[34] P. Carnevali, R. B. Morris, Y. Tsuji, G. Taylor, “New basis functions and computational procedures for $p$-version finite element analysis”, Int. J. Numer. Meth. Engrg., 36 (1993), 3759–3779 | DOI | Zbl

[35] C. Bernardi, M. Dauge, Y. Maday, “Relévements de traces presérvant les polinomes”, C. R. Acad. Sci. Paris Sér. I Math., 315 (1992), 333–338 | MR | Zbl

[36] C. Bernardi, M. Dauge, Y. Maday, Polynomials in weighted Sobolev spaces: Basics and trace liftings, Publications du Laboratoire d'Analyse Numerique, R92039 Universite Pierre et Marie Curie, Paris, 1993

[37] C. Bernardi, Y. Maday, “Relévements polinomial de traces et application”, RAIRO Modél. Math. Anal. Numér, 24 (1990), 557–611 | MR | Zbl

[38] R. Munos-Sola, “Polynomial liftings on a tetrahedron and applications to the $h-p$ version of the finite element method in three dimensions”, SIAM J. Numer. Anal., 34 (1997), 282–314 | DOI | MR

[39] S. V. Nepomnyaschikh, Metod razdeleniya oblasti dlya ellipticheskikh zadach s razryvnymi koeffitsientami, Preprint No 891. Vychisl. Tsentr SO AN SSSR, Novosibirsk, 1990 | MR

[40] O. Axellson, Iterative Solution Methods, Cambridge University Press, New York, 1994 | MR

[41] A. A. Samarskii, E. S. Nikolaev, Metody resheniya setochnykh uravnenii, Nauka, M., 1978 | MR | Zbl

[42] I. S. Gradshtein, I. M. Ryzhik, Tablitsy integralov, summ, ryadov i proizvedenii, 4-oe izd., Fizmatgiz, M., 1962

[43] J. Bramble, Multigrid methods, Pitman Research Notes in Mathematical Sciences, 294, Longman Sci. Tech., Harlow, Essex, 1993 | MR | Zbl

[44] W. Hackbusch, Multi-grid Methods and Applications, Springer-Verlag, Berlin, 1985 | Zbl

[45] M. Dryja, “A finite element capacitance method for elliptic problems on regions partitioned into substructures”, Numer. Math., 44 (1984), 153–168 | DOI | MR | Zbl