Abstract
We present a recently developed preconditioning of square block matrices (PRESB) to be used within a parallel method to solve linear systems of equations arising from tensor-product discretizations of initial boundary-value problems for parabolic partial differential equations. We consider weak formulations in Bochner–Sobolev spaces and tensor-product finite element approximations for the heat and eddy current equations. The fast diagonalization method is employed to decouple the arising linear system of equations into auxiliary spatial complex-valued linear systems that can be solved concurrently. We prove that the real part of the system matrix is positive definite, which allows us to accelerate the flexible generalized minimal residual method (FGMRES) by the PRESB preconditioner. The action of PRESB on a vector includes two solutions with positive definite matrices. The spectrum of the preconditioned system lies between 1/2 and 1. Finally, we combine the PRESB-FGMRES method with multigrid-CG iterations and illustrate the numerical efficiency and the robustness for spatial discretizations up to 12 millions degrees of freedom.
Dedicated to the memory of Owe Axelsson.
Funding source: Vysoká Škola bánská - Technická Univerzita Ostrava
Award Identifier / Grant number: SP2023/67
Funding source: Ministerstvo Školství, Mládeže a Tělovýchovy
Award Identifier / Grant number: 90140
Funding statement: The work was partially supported by project SGS No. SP2023/67, VŠB-Technical University of Ostrava, Czech Republic. This work was also supported by the Ministry of Education, Youth and Sports of the Czech Republic through the e-INFRA CZ (ID:90140).
References
[1]
D. N. Arnold, R. S. Falk and R. Winther,
Multigrid in
[2] O. Axelsson and D. Lukáš, Preconditioning methods for eddy-current optimally controlled time-harmonic electromagnetic problems, J. Numer. Math. 27 (2019), no. 1, 1–21. 10.1515/jnma-2017-0064Search in Google Scholar
[3] O. Axelsson and J. Maubach, A time-space finite element method for nonlinear convection diffusion problems, Numerical Treatment of the Navier–Stokes Equations (Kiel 1989), Notes Numer. Fluid Mech. 30, Friedrich Vieweg, Braunschweig (1990), 6–23. 10.1007/978-3-663-14004-7_2Search in Google Scholar
[4] O. Axelsson and J. Maubach, Global space-time finite element methods for time-dependent convection diffusion problems, Advances in Optimization and Numerical Analysis (Oaxaca 1992), Math. Appl. 275, Kluwer Academic, Dordrecht (1994), 165–184. 10.1007/978-94-015-8330-5_11Search in Google Scholar
[5] O. Axelsson, M. Neytcheva and B. Ahmad, A comparison of iterative methods to solve complex valued linear algebraic systems, Numer. Algorithms 66 (2014), no. 4, 811–841. 10.1007/s11075-013-9764-1Search in Google Scholar
[6] T. A. Davis, J. R. Gilbert, S. I. Larimore and E. G. Ng, Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm, ACM Trans. Math. Software 30 (2004), no. 3, 377–380. 10.1145/1024074.1024080Search in Google Scholar
[7] Z. Dostál, T. Kozubek, M. Sadowská and V. Vondrák, Scalable Algorithms for Contact Problems, Adv. Mech. Math. 36, Springer, New York, 2016. 10.1007/978-1-4939-6834-3Search in Google Scholar
[8] L. Foltyn, D. Lukáš and I. Peterek, Domain decomposition methods coupled with parareal for the transient heat equation in 1 and 2 spatial dimensions, Appl. Math. 65 (2020), no. 2, 173–190. 10.21136/AM.2020.0219-19Search in Google Scholar
[9] M. J. Gander, 50 years of time parallel time integration, Multiple Shooting and Time Domain Decomposition Methods, Contrib. Math. Comput. Sci. 9, Springer, Cham (2015), 69–113. 10.1007/978-3-319-23321-5_3Search in Google Scholar
[10] M. J. Gander, L. Halpern and F. Nataf, Optimal Schwarz waveform relaxation for the one dimensional wave equation, SIAM J. Numer. Anal. 41 (2003), no. 5, 1643–1681. 10.1137/S003614290139559XSearch in Google Scholar
[11] M. J. Gander and M. Neumüller, Analysis of a new space-time parallel multigrid algorithm for parabolic problems, SIAM J. Sci. Comput. 38 (2016), no. 4, A2173–A2208. 10.1137/15M1046605Search in Google Scholar
[12] G. Guennebaud and B. Jacob, Eigen v3, http://eigen.tuxfamily.org, 2010. Search in Google Scholar
[13] C. Hofer, U. Langer, M. Neumüller and R. Schneckenleitner, Parallel and robust preconditioning for space-time isogeometric analysis of parabolic evolution problems, SIAM J. Sci. Comput. 41 (2019), no. 3, A1793–A1821. 10.1137/18M1208794Search in Google Scholar
[14] O. A. Ladyženskaja, V. A. Solonnikov and N. N. Ural’ceva, Linear and Quasi-Linear Equations of Parabolic Type, American Mathematical Society, Providence, 1968. 10.1090/mmono/023Search in Google Scholar
[15] U. Langer and M. Zank, Efficient direct space-time finite element solvers for parabolic initial-boundary value problems in anisotropic Sobolev spaces, SIAM J. Sci. Comput. 43 (2021), no. 4, A2714–A2736. 10.1137/20M1358128Search in Google Scholar
[16] J.-L. Lions, Y. Maday and G. Turinici, Résolution d’EDP par un schéma en temps “pararéel”, C. R. Acad. Sci. Paris Sér. I Math. 332 (2001), no. 7, 661–668. 10.1016/S0764-4442(00)01793-6Search in Google Scholar
[17] G. Loli, M. Montardini, G. Sangalli and M. Tani, An efficient solver for space-time isogeometric Galerkin methods for parabolic problems, Comput. Math. Appl. 80 (2020), no. 11, 2586–2603. 10.1016/j.camwa.2020.09.014Search in Google Scholar
[18] R. E. Lynch, J. R. Rice and D. H. Thomas, Direct solution of partial difference equations by tensor product methods, Numer. Math. 6 (1964), 185–199. 10.1007/BF01386067Search in Google Scholar
[19]
J.-C. Nédélec,
Mixed finite elements in
[20] M. Neumüller, Space-Time Methods: Fast Solvers and Applications, Monogr. Ser. TU Graz 20, Technische Universität Graz, Graz, 2013. Search in Google Scholar
[21] C. Pechstein, Finite and Boundary Element Tearing and Interconnecting Solvers for Multiscale Problems, Lect. Notes Comput. Sci. Eng. 90, Springer, Heidelberg, 2013. 10.1007/978-3-642-23588-7Search in Google Scholar
[22] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput. 14 (1993), no. 2, 461–469. 10.1137/0914028Search in Google Scholar
[23] J. Schöberl, NETGEN - an advancing front 2d/3d-mesh generator based on abstract rules, Comput. Vis. Sci. 1 (1997), 41–52. 10.1007/s007910050004Search in Google Scholar
[24] B. Smith, P. Bjørstad and W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University, Cambridge, 2004. Search in Google Scholar
[25] O. Steinbach, Space-time finite element methods for parabolic problems, Comput. Methods Appl. Math. 15 (2015), no. 4, 551–566. 10.1515/cmam-2015-0026Search in Google Scholar
[26] A. Toselli and O. Widlund, Domain Decomposition Methods—Algorithms and Theory, Springer Ser. Comput. Math. 34, Springer, Berlin, 2005. 10.1007/b137868Search in Google Scholar
[27] M. Zank, Inf-Sup Stable Space-Time Methods for Time-Dependent Partial Differential Equations, Monogr. Ser. TU Graz 36, Technische Universität Graz, Graz, 2020. Search in Google Scholar
[28] W. Zulehner, Nonstandard norms and robust estimates for saddle point problems, SIAM J. Matrix Anal. Appl. 32 (2011), no. 2, 536–560. 10.1137/100814767Search in Google Scholar
© 2024 Walter de Gruyter GmbH, Berlin/Boston