×

Comparison of eigenvalue ratios in artificial boundary perturbation and Jacobi preconditioning for solving Poisson equation. (English) Zbl 1380.65330

Summary: The Shortley-Weller method is a standard finite difference method for solving the Poisson equation with Dirichlet boundary condition. Unless the domain is rectangular, the method meets an inevitable problem that some of the neighboring nodes may be outside the domain. In this case, an usual treatment is to extrapolate the function values at outside nodes by quadratic polynomial. The extrapolation may become unstable in the sense that some of the extrapolation coefficients increase rapidly when the grid nodes are getting closer to the boundary. A practical remedy, which we call artificial perturbation, is to treat grid nodes very near the boundary as boundary points. The aim of this paper is to reveal the adverse effects of the artificial perturbation on solving the linear system and the convergence of the solution. We show that the matrix is nearly symmetric so that the ratio of its minimum and maximum eigenvalues is an important factor in solving the linear system. Our analysis shows that the artificial perturbation results in a small enhancement of the eigenvalue ratio from \(O(1 /(h \cdot h_{\mathrm{min}})\) to \(O(h^{- 3})\) and triggers an oscillatory order of convergence. Instead, we suggest using Jacobi or ILU-type preconditioner on the matrix without applying the artificial perturbation. According to our analysis, the preconditioning not only reduces the eigenvalue ratio from \(O(1 /(h \cdot h_{\mathrm{min}})\) to \(O(h^{- 2})\), but also keeps the sharp second order convergence.

MSC:

65N06 Finite difference methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs

Software:

GRSIM
Full Text: DOI

References:

[1] Axelsson, O., On the Eigenvalue Distribution of Relaxed Incomplete Factorization Methods and the Rate of Convergence of Conjugate Gradient Methods (1989), Dept. of Math., Catholic University: Dept. of Math., Catholic University Nijmegen, The Netherlands, Technical Report
[2] Axelsson, O.; Eijkhout, V., Robust vectorizable preconditioners for three-dimensional elliptic difference equations with anisotropy, (te Riele, H. J.J.; Dekker, Th. J.; van der Vorst, H. A., Algorithm and Applications on Vector and Parallel Computers (1987), North Holland: North Holland Amsterdam), 279-306
[3] Beauwens, R., Upper eigenvalue bounds for pencils of matrices, Linear Algebra Appl., 62, 87-104 (1984) · Zbl 0575.65029
[4] Beauwens, R., On Axelsson’s perturbations, Linear Algebra Appl., 68, 221-242 (1985) · Zbl 0599.65023
[5] Beauwens, R.; Notay, Y.; Tombuyses, B., S/P images of upper triangular M-matrices, Numer. Linear Algebra Appl., 1, 19-31 (1994) · Zbl 0813.65071
[6] Benzi, M., Preconditioning techniques for large linear systems: a survey, J. Comput. Phys., 182, 418-477 (2002) · Zbl 1015.65018
[7] Bridson, R., Fluid Simulation for Computer Graphics (2008), A K Peters, Ltd.: A K Peters, Ltd. 888 Worcester street, Wellesley, MA 02482
[8] Ciarlet, P., Introduction to Numerical Linear Algebra and Optimization, Cambridge Texts Appl. Math. (1998), Cambridge University Press: Cambridge University Press 40 West 20th street, New York, NY 1001
[9] Dupont, T.; Kendall, R.; Rachford, H., An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. Numer. Anal., 5, 559-573 (1968) · Zbl 0174.47603
[10] Gibou, F.; Fedkiw, R.; Cheng, L.-T.; Kang, M., A second order accurate symmetric discretization of the Poisson equation on irregular domains, J. Comput. Phys., 176, 205-227 (2002) · Zbl 0996.65108
[11] Greenbaum, A., Iterative Methods for Solving Linear Systems (1997), SIAM: SIAM Philadelphia, PA · Zbl 0883.65022
[12] Gustafsson, I., A class of first order factorization methods, BIT, 18, 142-156 (1978) · Zbl 0386.65006
[13] Horn, R.; Johnson, C., Matrix Analysis (1991), Cambridge University Press: Cambridge University Press New York · Zbl 0729.15001
[14] Notay, Y., Conditioning analysis of modified block incomplete factorizations, Linear Algebra Appl., 154-156, 711-722 (1991) · Zbl 0735.65028
[15] Notay, Y., Conditioning of Stieltjes matrices by S/P consistently ordered approximate factorizations, Appl. Numer. Math., 10, 381-396 (1991) · Zbl 0756.65049
[16] Ng, Y.-T.; Chen, H.; Min, C.; Gibou, F., Guidelines for Poisson solvers on irregular domains with Dirichlet boundary conditions using the ghost fluid method, J. Sci. Comput., 41, 300-320 (2009) · Zbl 1203.65223
[17] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042
[18] Shah, A. A., GRSIM: a FORTRAN subroutine for the solution of non-symmetric linear systems, Commun. Numer. Methods Eng., 18, 803-815 (2002) · Zbl 1015.65016
[19] Shortley, G. H.; Weller, R., Numerical solution of Laplace’s equation, J. Appl. Phys., 9, 334-348 (1938) · Zbl 0019.03801
[20] Yoon, G.; Min, C., Analyses on the finite difference method by Gibou et al. for Poisson equation, J. Comput. Phys., 280, 184-194 (2015) · Zbl 1349.65573
[21] Yoon, G.; Min, C., A simple proof of Gustafsson’s conjecture in case of Poisson equation on rectangular domains, Am. J. Comput. Math., 5, 75-79 (2015)
[22] Yoon, G.; Min, C., Convergence analysis of the standard central finite difference method for Poisson equation, J. Sci. Comput., 67, 602-617 (2016) · Zbl 1345.65063
[23] Zheng, H.; Cheng, S. G.; Liu, Q. S., A decomposition procedure for nearly-symmetric matrices with applications to some nonlinear problems, Mech. Res. Commun., 37, 78-84 (2010) · Zbl 1272.74512
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.