×

High-order unconditionally stable FC-AD solvers for general smooth domains. II: Elliptic, parabolic and hyperbolic PDEs; theoretical considerations. (English) Zbl 1188.65139

Summary: A new partial differential equation (PDE) solver was introduced recently, in Part I [ibid. 229, No. 6, 2009–2033 (2010; Zbl 1197.00034)], on the basis of two main concepts: the well-known alternating direction implicit (ADI) approach, on one hand, and a certain “Fourier Continuation” (FC) method for the resolution of the Gibbs phenomenon, on the other. Unlike previous alternating direction methods of order higher than one, which only deliver unconditional stability for rectangular domains, the new high-order FC-AD (Fourier-continuation alternating-direction) algorithm yields unconditional stability for general domains-at an \(\mathcal O(N\log (N))\) cost per time-step for an \(N\) point spatial discretization grid.
In the present contribution we provide an overall theoretical discussion of the FC-AD approach and we extend the FC-AD methodology to linear hyperbolic PDEs. In particular, we study the convergence properties of the newly introduced FC(Gram) Fourier continuation method for both approximation of general functions and solution of the alternating-direction ordinary differential equations. We also present (for parabolic PDEs on general domains, and, thus, for our associated elliptic solvers) a stability criterion which, when satisfied, ensures unconditional stability of the FC-AD algorithm. Use of this criterion in conjunction with numerical evaluation of a series of singular values (of the alternating-direction discrete one-dimensional operators) suggests clearly that the fifth-order accurate class of parabolic and elliptic FC-AD solvers we propose is indeed unconditionally stable for all smooth spatial domains and for arbitrarily fine discretizations.
To illustrate the FC-AD methodology in the hyperbolic PDE context, finally, we present an example concerning the wave equation demonstrating sixth-order spatial and fourth-order temporal accuracy, as well as a complete absence of the debilitating “dispersion error”, also known as “pollution error”, that arises as finite-difference and finite-element solvers are applied to solution of wave propagation problems.

MSC:

65M70 Spectral, collocation and related methods for initial value and initial-boundary value problems involving PDEs
35L05 Wave equation
65F10 Iterative numerical methods for linear systems

Citations:

Zbl 1197.00034
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bruno, O.; Lyon, M., High-order unconditionally-stable FC-AD solvers for general smooth domains I: Basic elements, J. Comput. Phys., 229, 6, 2009-2033 (2010) · Zbl 1185.65184
[2] Peaceman, D.; Rachford, H., The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math., 3, 1, 28-41 (1955) · Zbl 0067.35801
[3] Douglas, J., Alternating direction methods for three space variables, Numer. Math., 4, 41-63 (1962) · Zbl 0104.35001
[4] Douglas, J.; Pearcy, C., On convergence of alternating direction procedures in the presence of singular operators, Numer. Math., 5, 175-184 (1963) · Zbl 0115.34701
[5] Douglas, J.; Gunn, J., A general formulation of alternating direction methods. Part I. Parabolic and hyperbolic problems, Numer. Math., 6, 428-453 (1964) · Zbl 0141.33103
[6] Douglas, J.; Rachford, H., On the numerical solution of heat conduction problems in two and three space variables, Trans. Am. Math. Soc., 82, 2, 421-439 (1956) · Zbl 0070.35401
[7] Averbuch, A.; Vozovoi, L., Two-dimensional parallel solver for the solution of Navier-Stokes equations with constant and variable coefficients using ADI on cells, Parallel Comput., 24, 673-699 (1998) · Zbl 0911.68079
[8] Eckhoff, K., On a high order numerical method for solving partial differential equations in complex geometries, J. Sci. Comput., 12, 2, 119-138 (1997) · Zbl 0899.35003
[9] Næss, O.; Eckhoff, K., A modified Fourier Galerkin method for the Poisson and Helmholtz equations, J. Sci. Comput., 17, 529-539 (2002) · Zbl 0999.65122
[10] Zhao, G.; Liu, Q., The unconditionally stable pseudospectral time-domain (PSTD) method, IEEE Microw. Wireless Compon. Lett., 13, 11, 475-477 (2003)
[11] Morton, K.; Mayers, D., Numerical Solution of Partial Differential Equations (2005), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1126.65077
[12] Kantartzis, N.; Zygiridis, T.; Tsiboukis, T., An unconditionally stable higher order ADI-FDTD technique for the dispersionless analysis of generalized 3-D EMC structures, IEEE Trans. Magn., 40, 2, 1436-1439 (2004)
[13] Dyksen, W., Tensor product generalized ADI methods for separable elliptic problems, SIAM J. Numer. Anal., 24, 1, 59-75 (1987) · Zbl 0625.65102
[14] Lynch, R.; Rice, J.; Thomas, D., Direct solution of partial difference equations by tensor product methods, Numer. Math., 6, 185-199 (1964) · Zbl 0126.12703
[15] Abarbanel, S.; Ditkowski, A., Asymptotically stable fourth-order accurate schemes for the diffusion equation on complex shapes, J. Comput. Phys., 133, 279-288 (1997) · Zbl 0891.65099
[16] Colonius, T.; Lele, S., Computational aeroacoustics: progress on nonlinear problems of sound generation, Prog. Aerospace Sci., 40, 345-416 (2004)
[17] Jameson, L., High order schemes for resolving waves: number of points per wavelength, J. Sci. Comput., 15, 4, 417-433 (2000) · Zbl 1013.76058
[18] Babuska, I.; Sauter, S., Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?, SIAM J. Numer. Anal., 34, 6, 2392-2423 (1997) · Zbl 0894.65050
[19] Abarbanel, S.; Ditkowski, A.; Yefet, A., Bounded error schemes for the wave equation on complex domains, J. Sci. Comput., 26, 67-81 (2006) · Zbl 1092.65069
[20] D. Appelö, N. Petersson, A fourth-order accurate embedded boundary method for the wave equation, preprint.; D. Appelö, N. Petersson, A fourth-order accurate embedded boundary method for the wave equation, preprint.
[21] Li, J.; Greengard, L., High order marching schemes for the wave equation in complex geometry, J. Comput. Phys., 198, 295-309 (2004) · Zbl 1052.65075
[22] Wandzura, S., Stable, high-order discretization for evolution of the wave equation in 2+1 dimensions, J. Comput. Phys., 199, 763-775 (2004) · Zbl 1057.65055
[23] Hesthaven, J.; Warburton, T., Nodal Discontinuous Galerkin Methods (2007), Springer: Springer New York · Zbl 1175.65111
[24] Alpert, B.; Greengard, L.; Hagstrom, T., An integral evolution formula for the wave equation, J. Comput. Phys., 162, 2, 536-543 (2000) · Zbl 0966.65062
[25] O. Bruno, Fast, high-order, high-frequency integral methods for computational acoustics and electromagnetics, in: M. Ainsworth, P. Davies, D. Duncan, P. Martin, B. Rynne (Eds.), Topics in Computational Wave Propagation Direct and Inverse Problems Series, Lecture Notes in Computational Science and Engineering, vol. 31, 2003, pp. 43-82.; O. Bruno, Fast, high-order, high-frequency integral methods for computational acoustics and electromagnetics, in: M. Ainsworth, P. Davies, D. Duncan, P. Martin, B. Rynne (Eds.), Topics in Computational Wave Propagation Direct and Inverse Problems Series, Lecture Notes in Computational Science and Engineering, vol. 31, 2003, pp. 43-82.
[26] Boyd, J., A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds, J. Comput. Phys., 178, 118-160 (2002) · Zbl 0999.65132
[27] Bruno, O.; Han, Y.; Pohlman, M., Accurate, high-order representation of complex three-dimensional surfaces via Fourier-continuation analysis, J. Comput. Phys., 227, 1094-1125 (2007) · Zbl 1128.65017
[28] Phillips, G. M., Interpolation and Approximation by Polynomials, CMS Books in Mathematics (2003), Springer: Springer New York · Zbl 1023.41002
[29] Jackson, D., The Theory of Approximation, vol. 11 (1930), American Mathematical Society Colloquium Publications, American Mathematical Society: American Mathematical Society Colloquium Publications, American Mathematical Society New York · JFM 56.0936.01
[30] Canuto, C.; Hussaini, M.; Quarteroni, A.; Zang, T., Spectral Methods Fundamentals in Single Domains, Scientific Computation (2006), Springer: Springer Berlin · Zbl 1093.76002
[31] Stoer, J.; Bulirsch, R., Introduction to Numerical Analysis (2004), Springer: Springer New York · Zbl 0771.65002
[32] M. Lyon, High-order unconditionally-stable FC-AD PDE solvers for general domains, Ph.D. Thesis, California Institute of Technology, 2009.; M. Lyon, High-order unconditionally-stable FC-AD PDE solvers for general domains, Ph.D. Thesis, California Institute of Technology, 2009.
[33] Golub, G.; Van Loan, C., Matrix Computations (2006), The John Hopkins University Press: The John Hopkins University Press Baltimore
[34] Fornberg, B.; Zuev, J.; Lee, J., Stability and accuracy of time-extrapolated ADI-FDTD methods for solving wave equations, J. Comput. Appl. Math., 200, 178-192 (2007) · Zbl 1119.78016
[35] Strikwerda, J., Finite Difference Schemes and Partial Differential Equations (2004), SIAM: SIAM Philadelphia · Zbl 1071.65118
[36] Evans, L., Partial Differential Equations (1998), American Mathematical Society: American Mathematical Society Providence
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.