Hierarchical Interpolative Factorization Preconditioner for Parabolic Equations
- PDF / 1,391,090 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 223 Views
Hierarchical Interpolative Factorization Preconditioner for Parabolic Equations Jordi Feliu-Fabà1
· Lexing Ying2
Received: 13 April 2020 / Revised: 18 September 2020 / Accepted: 8 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This note proposes an efficient preconditioner for solving linear and semi-linear parabolic equations. With the Crank–Nicholson time stepping method, the algebraic system of equations at each time step is solved with the conjugate gradient method, preconditioned with hierarchical interpolative factorization. Stiffness matrices arising in the discretization of parabolic equations typically have large condition numbers, and therefore preconditioning becomes essential, especially for large time steps. We propose to use the hierarchical interpolative factorization as the preconditioning for the conjugate gradient iteration. Computed only once, the hierarchical interpolative factorization offers an efficient and accurate approximate inverse of the linear system. As a result, the preconditioned conjugate gradient iteration converges in a small number of iterations. Compared to other classical exact and approximate factorizations such as Cholesky or incomplete Cholesky, the hierarchical interpolative factorization can be computed in linear time and the application of its inverse has linear complexity. Numerical experiments demonstrate the performance of the method and the reduction of conjugate gradient iterations. Keywords Hierarchical interpolative factorization · Parabolic equations · Heat equation · Reaction–diffusion equations
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10915-02001343-5) contains supplementary material, which is available to authorized users.
B
Jordi Feliu-Fabà [email protected] Lexing Ying [email protected]
1
Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA, USA
2
Department of Mathematics and Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA, USA 0123456789().: V,-vol
123
50
Page 2 of 14
Journal of Scientific Computing
(2020) 85:50
1 Introduction This note is concerned with the numerical solution of parabolic equations of the form ∂u(x, t) = ∇ · a(x)∇u(x) + r u(x, t) , x ∈ Ω ⊂ Rd , ∂t
(1)
in two and three dimensions, with appropriate boundary conditions on ∂Ω and initial conditions u(x, 0) = u 0 (x). Here, a(x) > 0 is the coefficient field of the diffusion operator and r u(x, t) is the reaction term. We are interested on approximating the unknown field u(x, t). Such reaction–diffusion equations can model a great variety of physical phenomena, such as heat conduction with internal heat generation, population dynamics [7,16] or pattern formation [22] in biology. The most common spatial discretizations for solving (1) are finite difference and finite element methods. Such a spatial discretization results in a time-dependent system of form ∂u(t) = Mu(t) + r (t), ∂t
(2
Data Loading...
