Algorithm 651: Algorithm HFFT–high-order fast-direct solution of the Helmholtz equation

ABSTRACT

HFFT is a software package for solving the Helmholtz equation on bounded two- and three-dimensional rectangular domains with Dirichlet, Neumann, or periodic boundary conditions. The software is the result of combining new fourth-order accurate compact finite difference (HODIE) discretizations and a fast-direct solution technique (the Fourier method). In this paper we briefly describe the user interface to HFFT and present an example of its usage and several details of its implementation.

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. 1981. NCAR Program Library, National Center for Atmospheric Research, P. O. Box 3000, Boulder, CO 80307.
• 2: Ronald F. Boisvert, A fourth-order-accurate Fourier method for the Helmholtz equation in three dimensions, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.221-234, Sept. 1987 [doi>10.1145/29380.29863]
• 3: BUZBEE, B. L., GOLUB, G. H., AND NIELSON, C.W. On direct methods for solving Poisson's equations. SIAM J. Num. Anal. 7 (1970), 627-655.
• 4: COCHRAN, W.T. What is the fast Fourier transform? IEEE Trans. Audio Electroacoustics 15 (1967), 45-55.
• 5: EVANS, D.J. An algorithm for the solution of certain tridiagonal systems of linear equations. Computer J. 15 (1972), 356-359.
• 6: EVANS, D.J. Fast ADI methods for the solution of linear parabolic partial differential equations involving 2 space dimensions. BIT 17 (1977), 486-491.
• 7: Fortran Version 5 Reference Manual. Control Data Corporation, CDC Publications and Graphics Division, P. O. Box 3492, Sunnyvale, CA 94088-3492, 1983.
• 8: P. A. Fox , A. D. Hall , N. L. Schryer, Algorithm 528: Framework for a Portable Library [Z], ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.177-188, June 1978 [doi>10.1145/355780.355789]
• 9: 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]
• 10: LYNCH, R. E. O(h4) and O(h~) 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. Stepleman, Eds. IMACS, Rutgers Univ., New Brunswick, N.J., 1984, pp. 199-202.
• 11: LYNCH, R. E. O(h6) Accurate Finite Difference Approximation to Solutions of the Poisson Equation in Three Variables. CSD-TR 221, Computer Sciences Dept., Purdue Univ., West Lafayette, In., 1977.
• 12: 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.
• 13: MIKHLIN, S. G., ED. Linear Equations of Mathematical Physics. Holt, Reinhardt, and Winston, New York, 1967.
• 14: ORTEGA, J. M., AND VOI(~T, R. G. Solution of partial differential equations on vector and parallel computers. SIAM Rev. 17 (1985), 149-240.
• 15: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 16: SWARZTRAUBER, P. N., AND SWEET, R. Efficient FORTRAN Subprograms for the Solution of Elliptic Partial Dif/erential Equations. NCAR Tech. Note IA-109, National Center for Atmospheric Research, Boulder, Co., 1975.
• 17: SWARZTRAUBER, P.N. Vectorizing the FFTs. In Parallel Computation, G. Rodrigue, Ed. Academic Press, New York, 1982, pp. 51-84.
• 18: SWEET, R.A. Fast Fourier transforms on a staggered grid. 1985. To appear.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Elliptic equations

General Terms:
Algorithms

Keywords:
Fourier method, HODIE method, Helmholtz equation, fast-direct method, finite differences, high-order accuracy