Spectral discretizations of 3-d elliptic problems and fast domain decomposition methods

V. Korneev   ; A. Rytov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 10, pp. 1727-1745

Résumé

An important for applications, the class of $hp$ discretizations of second-order elliptic equations consists of discretizations based on spectral finite elements. The development of fast domain decomposition algorithms for them was restrained by the absence of fast solvers for the basic components of the method, i.e., for local interior problems on decomposition subdomains and their faces. Recently, the authors have established that such solvers can be designed using special factorized preconditioners. In turn, factorized preconditioners are constructed using an important analogy between the stiffness matrices of spectral and hierarchical basis $hp$-elements (coordinate functions of the latter are defined as tensor products of integrated Legendre polynomials). Due to this analogy, for matrices of spectral elements, fast solvers can be developed that are similar to those for matrices of hierarchical elements. Based on these facts and previous results on the preconditioning of other components, fast domain decomposition algorithms for spectral discretizations are obtained.

Bibliographie

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

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

[3] Pavarino L. E., Widlund O. B., “Polylogarithmic bound for an iterative substructuring method for spectral elements in three dimensions”, SIAM J. Numer. Analys., 37:4 (1996), 1303–1335 | DOI | MR

[4] Ivanov S. A., Korneev V. G., “Preconditioning in the domain decomposition methods for the $p$-version with the hierarchical bases”, Matematicheskoie modelirovanie (Math. Modelling), 8:9 (1996), 63–73 | MR | Zbl

[5] Korneev V. G., Jensen S., “Preconditioning of the $p$-version of the finite element method”, Computer Meth. Appl. Mech. Engrg., 150:1–4 (1997), 215–238 | DOI | MR | Zbl

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

[7] Oden J. T., Patra A., Feng Y. S., “Parallel Domain decomposition solver for adaptive $hp$ finite element methods”, SIAM J. Numer. Analys, 34 (1997), 2090–2118 | DOI | MR | Zbl

[8] Korneev V. G., Flaherty J., Oden T., Fish J., “$Hp$-version additive Schwarz algorithms on triangular meshes”, Matematicheskoie modelirovanie (Math. Modelling), 14:2 (2002), 61–94 | MR | Zbl

[9] Toselli A., Widlund O., Domain decomposition methods – algorithms and theory, Springer, Berlin etc., 2005 | MR | Zbl

[10] Orzag A., “Spectral methods for problems in complex geometries”, J. Comput. Phys., 37 (1980), 70–92 | DOI | MR

[11] Korneev V. G., “Almost optimal method for solving Dirichlet problems on subdomains of decomposition of hierarchical $hp$-version”, Differcntsial'nye uravnenia (Different. Equations), 37:7 (2001), 1–10 | MR

[12] Korneev V. G., “Local Dirichlet problems on subdomains of decomposition in $hp$ discretizations, and optimal algorithms for their solution”, Matematicheskoie modelirovanie (Math. Modelling), 14:5 (2002), 51–74 | MR | Zbl

[13] Beuchter S., “Multigrid solver for the inner problem in domain decomposition methods for $p$-FEM”, SIAM J. Numer. Analys., 40:4 (2002), 928–944 | DOI | MR

[14] Beuchter S., Schneider R., Schwab R., “Multiresolution weighted norm equivalences and applications”, Numer. Math., 98:1 (2004), 67–97 | DOI | MR

[15] Korneev V., Langer U., Xanthis L., “On fast domain decomposition solving procedures for $hp$-discretizations of 3-d elliptic problems”, Comput. Meth. Appl. Math., 3:4 (2003), 536–559 | MR | Zbl

[16] Korneev V., Langer U., Xanthis L., “Fast adaptive domain decomposition algorithms for $hp$-discretizations of 2-d and 3-d elliptic equations: recent advances”, HERMIS-$\mu\pi$: Internat. J. Comput. Math. and its Applic., 4 (2003), 27–44 | MR | Zbl

[17] Korneev V., Xanthis L., Anoufriev I., “Solving finite element hp discretizations of elliptic problems by fast DD algorithms”, Tr. St. Petersburg State Polytechn. Univ., 485, 2002, 126–153

[18] Korneev V. G., Xanthis L., Anufriev I. E., Hierarchical and Lagrange hp discretizations and fast domain decomposition solvers for them, SFB Rept 02-18, Johannes Kepler Univ. Linz, Linz, 2002

[19] Anoufriev I., Korneev V., Rytov A., “Computer testing of fast domain decomposition algorithms for $hp$ discretizations of 2-nd order elliptic equations”, Proc. Hellenic-European Conf. Computer Math. and its Applic. V. 1 (HERCMA 2003), LEA Publs., Athens, 2003, 99–108

[20] Anoufriev I., Korneev V., “Fast domain decomposition solver for degenerating PDE of 4th order in 3D domain”, Matematica Balkanika, 6:1 (2006), 101–112

[21] Shen J., Wang F., Xu J., “A finite element multigrid preconditioner for Chebyshev-collocation methods”, Appl. Numer. Math., 33 (2000), 471–477 | DOI | MR | Zbl

[22] Korneev V., Rytov A., “On the interrelation between fast solvers for spectral and hierarchical $p$ elements”, HERMIS-$\mu\pi$: Internat. J. Comput. Math. and its Applic., 6 (2005), 99–113 http://www.aueb.gr/pympe/hermis/hermis volume-6/

[23] Korneev V., Rytov A., “On existence of the essential interrelation between spectral and hierarchical elements”, Mesh Methods for Boundary Value Problems and Applic., Proc. 6-th All-Russian Seminar (Materialy 6-ogo vserossiiskogo seminara), Kazan State Univ., Kazan, 2005, 141–150

[24] Smith B. F., “A domain decomposition algorithm for elliptic problems in three dimentions”, Numer. Math., 60:4 (1991), 219–234 | DOI | MR

[25] Dryja M., Smith B. F., Widlimd O. B., “Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions”, SIAM J. Numer. Analys., 31:6 (1994), 1662–1694 | DOI | MR | Zbl

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

[27] Bramble J. H., Pasciak J. E., Schatz A. H., “The constraction of preconditioners for elliptic problems by substructuring. II”, Math. Comput., 49:17 (1987), 1–16 | DOI | MR | Zbl

[28] Bramble J. H., Pasciak J. E., Schatz A. H., “The constraction of preconditioners for elliptic problems by substructuring. III”, Math. Comput., 51:184 (1988), 415–430 | DOI | MR | Zbl

[29] Bramble J. H., Pasciak J. E., Schatz A. H., “The constraction of preconditioners for elliptic problems by substructuring. IV”, Math. Comput., 53:187 (1989), 1–24 | DOI | MR | Zbl

[30] Bernardi Ch., Maday Y., “Polynomial interpolation results in Sobolev spaces”, J. Comput. and Appl. Math., 43 (1992), 53–80 | DOI | MR | Zbl

[31] Bernardi Ch., Maday Y., Approximations spectrales de problemes aux limites elliptiques, Math. Appl., 10, Springer, Paris, 1992 | MR

[32] Canuto C., “Stabilizaiton of spectral methods by finite element bubble functions”, Comput. Meth. Appl. Mech. Engrg., 116 (1994), 13–26 | DOI | MR | Zbl

[33] Grisvard P., Elliptic problems in nonsmooth domains, Pitman Publishing, Boston, 1985 | MR | Zbl

[34] Lions J.-L., Maqenes E. M., Nonhomogeneous boundary value problems and applications, v. 1, Springer, Berlin etc., 1972

[35] Ciarlet P., The finite element method for elliptic problems, North-Holland Publishing Co., Amsterdam etc., 1978 | MR | Zbl

[36] “On the construction of variational-difference schemes of higher orders of accuracy”, Vestnik Leningrad Univ. Math., 3 (1976), 301–316 | MR | Zbl

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

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

[39] Korneev V., Langer U., “Domain decomposition methods and preconditioning”, Encyclopedia Comput. Mech., v. 1, John Wiley Sons, Ltd., 2004, 617–647