A fourth-order-accurate Fourier method for the Helmholtz equation in three dimensions

ABSTRACT

We present fourth-order-accurate compact discretizations of the Helmholtz equation on rectangular domains in two and three dimensions with any combination of Dirichlet, Neumann, or periodic boundary conditions. The resulting systems of linear algebraic equations have the same block-tridiagonal structure as traditional central differences and hence may be solved efficiently using the Fourier method. The performance of the method for a variety of test cases, including problems with nonsmooth solutions, is presented. The method is seen to be roughly twice as fast as deferred corrections and, in many cases, results in a smaller discretization error.

REFERENCES

• 1: ADAMS, J., SWARZTRAUBER, P. N., AND SWEET, R. A. FISHPAK, a package of Fortran subprograms for the solution of separable elliptic partial differential equations. Version 3.1, NCAR Program Library, National Center for Atmospheric Research, Boulder, Colo., 1981.
• 2: BOISVERT, R.F. Families of high order accurate discretizations of some elliptic problems. SIAM J. Sci. Stat. Comput. 2 (1981), 268-284.
• 3: BO~SVERT, R.F. High order compact difference formulas for elliptic problems with mixed boundary conditions. In Advances in Computer Methods for Partial Differential Equations IV, R. Vichnevetsky and R. S. Stepleman, Eds. IMACS, Rutgers Univ., New Brunswick, N.J., 1981, pp. 193-199.
• 4: BOISVERT, R.F. A fourth-order accurate fast direct method for the Helmholtz equation. In Elliptic Problem Solvers II, G. Birkhoff and A. Schoenstadt, Eds. Academic Press, Orlando, Fla., pp. 35-44.
• 5: BOISVERT, R.F. A fourth-order accurate Fourier method for the Helmholtz equation in three dimensions. Submitted for publication.
• 6: BUZBEE, B. L., GOLUB, G. H., AND NIELSON, C.W. On direct methods for solving Poisson's equations. SIAM j. Numer. Anal. 7 (1970), 627-655.
• 7: CIMENT, M., LEVENTHAL, S. H., AND WEINBERG, B.C. The operator compact implicit method for parabolic equations. J. Comput. Phys. 28 (1978), 135-166.
• 8: COLLATZ, L. The Numerical Treatment of Differential Equations. Springer-Verlag, Berlin, 1960.
• 9: DYKSEN, W.R. The tensor product generalized ADI method for elliptic problems. CSD-TR 493, Purdue Univ., Computer Sciences Dept., West Lafayette, In., 1984.
• 10: E. N. Houstis , T. S. Papatheodorou, High-Order Fast Elliptic Equation Solvers, ACM Transactions on Mathematical Software (TOMS), v.5 n.4, p.431-441, Dec. 1979 [doi>10.1145/355853.355859]
• 11: KAUFMAN, L., AND WARNER, D. D. High order, fast-direct methods for separable elliptic equations. SIAM J. Numer. Anal. 21 (1984), 672-694.
• 12: LYNCH, R.E. O(h4) and O(h6) finite difference approximations to the Helmholtz equation in n-dimensions. In Advances in Computer Methods for Partial Differential Equations. V. R. Vichnevetsky and R. S. Steplemen, Eds. IMACS, Rutgers Univ., New Brunswick, N.J., 1984, pp. 199-202.
• 13: LYNCH, R. E., AND RICE, J.R. High accuracy finite difference approximations to solutions of elliptic partial differential equations. Proc. Nat. Acad. Sci. 75 (1978), 2541-2544.
• 14: LYNCH, R. E., RICE, J. R., AND THOMAS, D.H. Tensor product analysis of partial differential equations. Bull. Am. Math. Soc. 70 (1964), 378-384.
• 15: MANOHAR, R., AND STEPHENSON, J. W. High order difference schemes for linear partial differential equations. SIAM J. ScL Star. Comput. 5 {1984), 69-77.
• 16: MAYO, A. Fast high order accurate solution of Laplace's equation on irregular regions. SIAM J. Sci. Star. Comput. 6 (1985), 144-157.
• 17: MERCIER, P., AND DEVILLE, M. A multidimensional compact higher order scheme for 3-d Poisson's equation. J. Comput. Phys. 39 (1981), 443-455.
• 18: PEREYRA, V. On improving the approximate solution of a functional equation by deferred corrections. Numer. Math. 8 {1966), 376-391.
• 19: PEREYRA, V., PROSKUROWSKI, W., AND WIDLUND, O. High order fast Laplace solvers for the Dirichlet problem on general regions. Math. Comput. 31 (1977), 1-16.
• 20: Wlodzimierz Proskurowski, Numerical Solution of Helmholtz's Equation by Implicit Capacitance Matrix Methods, ACM Transactions on Mathematical Software (TOMS), v.5 n.1, p.36-49, March 1979 [doi>10.1145/355815.355818]
• 21: Wlodzimierz Proskurowski, Algorithm 593: A Package for the Helmholtz Equation in Nonrectangular Planar Regions, ACM Transactions on Mathematical Software (TOMS), v.9 n.1, p.117-124, March 1983 [doi>10.1145/356022.356028]
• 22: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 23: SCHULTZ, M.H. Solving elliptic problems on an array processor system. In Elliptic Problem Solvers II, G. Birkhoff and A. Schoenstadt, Eds. Academic Press, Orlando, Fl., 1984, pp. 77-92.
• 24: SWARZTRAUBER, P. N. The methods of cyclic reduction, Fourier analysis, and the FACR algorithm for the discrete solution of Poisson's equation on a rectangle. SIAM Rev. 19 (1977), 490-501.
• 25: SWARZTRAUBER, P.N. Vectorizing the FFTs. In Parallel Computation, G. Rodrigue, Ed. Academic Press, New York, 1982, pp. 51-84.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Elliptic equations
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Theory, Verification