Solving Discrete Dirichlet Problems on Spectral Finite Elements by Fast Domain Decomposition Algorithm

Abstract:

A key component of DD (domain decomposition) solvers for $hp$ discretizations of elliptic equations is the solver for the internal stiffness matrices of $p$-elements. We consider the algorithm of the linear complexity for solving such problems on spectral $p$-elements, which, therefore, in the leading DD solver plays the role of the second stage DD solver. It is based on the first order finite element preconditioning of the Orszag type for the reference element stiffness matrices. Earlier, for spectral elements, only fast solvers obtained with the use of special preconditioners in factored form were known. The most intricate part of the algorithm is the inter-subdomain Schur complement preconditioning by inexact iterative solver employing two preconditioners -- preconditioner-solver and preconditioner-multiplicator. From general point of view, the solver developed in the paper, is the DD solver for the discretization on a strongly variable in size and shape deteriorating mesh with the number of subdomains growing with the growth of the number of degrees of freedom.

• Periodical: Applied Mechanics and Materials (Volumes 587-589)
• Pages: 2312-2329
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.587-589.2312
• Online since: July 2014
• Authors: V.G. Korneev
• Keywords: Fast Solvers, Preconditioning, Schur Complement Preconditioning, Spectral Finite Elements

References

[1] Axelsson, O. and Vassilevski, P. (1989). Algebraic multilevel preconditioning methods, i. Num. Math. 56, 2-3 : 157-177.

[2] Bernardi, C. and Maday, Y. (1992). Polynomial interpolation results in Sobolev spaces, Journal of Computational and Applied Mathematics 43, 1-2, pp.53-80.

DOI: 10.1016/0377-0427(92)90259-z

[3] Bernardi, C. and Maday, Y. (1992). Spectral approximation for elliptic boundary value problems, Mathematiques & Applications, Vol. iv (Springer-Verlag, Paris), (in French).

[4] Bernardi, C. and Maday, Y. (1997). Spectral method, In P. Ciarlet and J. -L. Lions (eds. ), Handbook of numerical analysis, vol. V: Techniques of Scientific computing (Part 2) (North-Holland) : 209-485.

DOI: 10.1016/s1570-8659(97)80003-8

[5] Beuchler, S. (2002). Multigrid solver for the inner problem in domain decomposition methods for p-fem, SIAM J. Num. Anal. 40, 4 : 928-944.

DOI: 10.1137/s0036142901393851

[6] Beuchler, S., Schneider, R. and Schwab, C. (2004). Multiresolution weighted norm equivalence and applications, Numerische Mathematik 98, 1, pp.67-97.

DOI: 10.1007/s00211-003-0491-8

[7] Canuto, C. (1994). Stabilization of spectral methods by finite element bubble functions, Computer Methods in Applied Mechanics and Engineering 116, 1-4 : 13-26.

DOI: 10.1016/s0045-7825(94)80004-9

[8] Canuto, C., Hussani, M., Quarteroni, A. and Zang, A. (1988). Spectral Methods in Fluid Dynamics (Springer-Verlag, Berlin, Heidelberg).

[9] Canuto, C. and Quarteroni, A. (1982). Approximation results for orthogonal polynomials in sobolev spaces, Math. Comp. 38 : 67-86.

DOI: 10.1090/s0025-5718-1982-0637287-3

[10] Deville, M., Fischer, P. and Mund, E. (2002). High-Order Methods for Incompressible Fluid Flow (Cambridge University Press, Cambridge, England).

DOI: 10.1017/s0022112003005056

[11] Deville, M.O. and Mund, E.H. (1985). Chebyshev pseudospectral solution of second order elliptic equations with finite element preconditioning. J. Comput. Phys., 60 : 517-533.

DOI: 10.1016/0021-9991(85)90034-8

[12] Deville, M.O. and Mund, E.H. (1990). Finite-element preconditioning for pseudospectral solutions of elliptic problems. SIAM Journal on Scientific and Statistical Computations 1990; 11 : 311 - 342.

DOI: 10.1137/0911019

[13] Dolgov, S.V., Khoromskij, B.N., Oseledets, I. and Tyrtyshnikov, E.E. (2011).

[14] Dyakonov, E. (1989). Minimization of computational work. Asymptotically optimal algorithms for elliptic problems (Nauka, Moscow).

[15] Griebel, M. and Oswald, P. (1995). On the abstract theory of additive and multiplicative Schwarz algorithms, Numerische Mathematik 70, 2 : 163-180.

DOI: 10.1007/s002110050115

[16] Guo, B. and Wang, L. (2004). Jacobi approximations in non-uniformly Jacobi-weighted Sobolev spaces, Journal of Approximation Theory 128, 1 : 1-41.

DOI: 10.1016/j.jat.2004.03.008

[17] Hackbusch, W., Khoromskij, B. N. and Kriemann, R. (2005). Direct schur complement method by domain decomposition based on h-matrix approximation, Computing and Visualization in the Sciences 8, 3/4 : 179-188.

DOI: 10.1007/s00791-005-0008-3

[18] Hsiao, G., Khoromskij, B. and Wendland, W. (2001). Preconditioning for boundary element methods in domain decomposition, Eng. Analysis with Boundary Elements 25 : 323-338.

DOI: 10.1016/s0955-7997(01)00029-7

[19] Ivanov, S. and Korneev, V. (1996). Preconditioning in the domain decomposition methods for the p-version with the hierarchical bases, Matematicheskoie modelirovanie (Mathematical Modeling) 8, 9 : 63-73.

[20] Karniadakis, G. and Sherwin, S. (1999). Spectral hp element methods for CFD (Oxford University Press).

[21] Khoromskij, B. and Wittum, G. (1999). Robust schur complement method for strongly anisotropic elliptic equations, J. Numer. Linear Algebra with Appl. 6 : 1-33.

DOI: 10.1002/(sici)1099-1506(199912)6:8<621::aid-nla164>3.0.co;2-f

[22] Khoromskij, B. and Wittum, G. (2004). Numerical solution of elliptic differential equations by reduction to the interface (Springer, Berlin - New York).

[23] Korneev, V. (2002). Local dirichlet problems on subdomains of decomposition in hp discretizations, and optimal algorithms for their solution, Matematicheskoie Modelirovanie (Mathematical Modelling) 14, 5 : 51-74.

[24] Korneev, V. (2013). Fast domain decomposition type solver for stiffness matrices of reference p-elements Computational methods in applied mathematics, N 2: 161-184. Doi: 10. 1515/cmam2013-0003.

DOI: 10.1515/cmam-2013-0003

[25] Korneev, V. (2013).

[26] Korneev, V. and Jensen, S. (1997). Preconditioning of the p-version of the finite element method, Computer Meth. Appl. Mech. Engrg. 150, 1-4 : 215-238.

[27] Korneev, V. and Langer, U. (2004).

[28] Korneev, V., Poborchi, S. and Salgado, A. (2007).

[29] Korneev, V. and Rytov A. (2005).

[30] Korneev, V. and Rytov, A. (2007). Spectral discretizations of 3-d elliptic problems and fast domain decomposition methods, Computational Mathematics and Mathematical Physics 10 : 1727- -1745.

DOI: 10.1134/s0965542507100077

[31] Korneev, V. and Rytov, A. (2008). Fast domain decomposition algorithm for discretizations of 3-d elliptic equations by spectral elements, Comput. Methods Appl. Mech. Engrg. 197 : 1433- 1446.

DOI: 10.1016/j.cma.2007.10.013

[32] Nepomnyaschikh, S. (1991).

[33] Oswald, P. (1999).

[34] Orszag, A. (1980). Spectral methods for problems in complex geometries. Journal of Computational Physics, 37 : 70 - 92.

DOI: 10.1016/0021-9991(80)90005-4

[35] Pflaum, C. (2000). Robust confergence of multilevel algorithms for convection-difusion equations, SIAM Journal on Numerical Analysis 37, 2 : 443-469.

DOI: 10.1137/s0036142998346870

[36] Quarteroni, A. and Vali, A. (1999). Domain Decomposition Methods for Partial Differential Equations (Oxfort Sciences Publications).

[37] Rytov, A. (2006).

[38] Schieweck, N. (1986).