Evaluation of Fourier integrals using -splines

Authors:
M. Lax and G. P. Agrawal

Journal:
Math. Comp. **39** (1982), 535-548

MSC:
Primary 65D30; Secondary 42A15, 65R10

DOI:
https://doi.org/10.1090/S0025-5718-1982-0669645-5

Corrigendum:
Math. Comp. **43** (1984), 347.

Corrigendum:
Math. Comp. **43** (1984), 347.

MathSciNet review:
669645

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Finite Fourier integrals of functions possessing jumps in value, in the first or in the second derivative, are shown to be evaluated more efficiently, and more accurately, using a continuous Fourier transform (CFT) method than the discrete transform method used by the fast Fourier transform (FFT) algorithm. A *B*-spline fit is made to the input function, and the Fourier transform of the set of *B*-splines is performed analytically for a possibly nonuniform mesh. Several applications of the CFT method are made to compare its performance with the FFT method. The use of a 256-point FFT yields errors of order , whereas the same information used by the CFT algorithm yields errors of order --the machine accuracy available in single precision. Comparable accuracy is obtainable from the FFT over the limited original domain if more than 20,000 points are used.

**[1]**Flavian Abramovici,*The accurate calculation of Fourier integrals by the fast Fourier transform technique*, J. Comput. Phys.**11**(1973), no. 1, 28–37. MR**413436**, https://doi.org/10.1016/0021-9991(73)90146-0**[2]**M. Abramowitz & I. A. Stegun (Editors),*Handbook of Mathematical Functions*, Dover, New York, 1965, p. 300.**[3]**G. P. Agrawal & M. Lax, "Fraunhofer diffraction in the beam approximation from two longitudinally separated slits,"*J. Opt. Soc. Amer.*, v. 72, 1982, pp. 164-166.**[4]**Philip J. Davis,*Interpolation and approximation*, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1963. MR**0157156****[5]**Carl de Boor,*On calculating with 𝐵-splines*, J. Approximation Theory**6**(1972), 50–62. MR**338617**, https://doi.org/10.1016/0021-9045(72)90080-9**[6]**Carl de Boor,*Package for calculating with 𝐵-splines*, SIAM J. Numer. Anal.**14**(1977), no. 3, 441–472. MR**428691**, https://doi.org/10.1137/0714026**[7]**Bo Einarsson,*Numerical calculation of Fourier integrals with cubic splines*, Nordisk Tidskr. Informationsbehandling (BIT)**8**(1968), 279–286. MR**239757**, https://doi.org/10.1007/bf01933438**[8]**Bo Einarsson,*Use of Richardson extrapolation for the numerical calculation of Fourier transforms*, J. Comput. Phys.**21**(1976), no. 3, 365–370. MR**416080**, https://doi.org/10.1016/0021-9991(76)90036-x**[9]**L. N. G. Filon, "On a quadrature formula for trigonometric integrals,"*Proc. Roy. Soc. Edinburgh*, v. 49, 1928, pp. 38-47.**[10]**S. M. Flatte & F. D. Tappert, "Calculation of the effect of internal waves on oceanic sound transmission,"*J. Acoust. Soc. Amer.*, v. 58, 1975, pp. 1151-1159.**[11]**J. Gazdag, "Numerical convective schemes based on accurate computation of space derivatives,"*J. Comput. Phys.*, v. 13, 1973, pp. 100-113.**[12]**R. W. Hockney,*A fast direct solution of Poisson’s equation using Fourier analysis*, J. Assoc. Comput. Mach.**12**(1965), 95–113. MR**213048**, https://doi.org/10.1145/321250.321259**[13]**H. Jeffreys & B. S. Jeffreys,*Methods of Mathematical Physics*, Cambridge Univ. Press, Oxford, 1978, p. 262.**[14]**M. Lax, G. P. Agrawal & W. H. Louisell, "Continuous Fourier transform spline solution of unstable resonator field distribution,"*Opt. Lett.*, v. 9, 1979, pp. 303-305.**[15]**Roland C. Le Bail,*Use of fast Fourier transforms for solving partial differential equations in physics*, J. Comput. Phys.**9**(1972), 440–465. MR**309342**, https://doi.org/10.1016/0021-9991(72)90005-8**[16]**Martin J. Marsden and Gerald D. Taylor,*Numerical evaluation of Fourier integrals*, Numerische Methoden der Approximationstheorie, Band 1 (Tagung, Oberwolfach, 1971) Birkhäuser, Basel, 1972, pp. 61–76. Internat. Schriftenreihe Numer. Math., Band 16. MR**0386234****[17]**Jürg T. Marti,*An algorithm recursively computing the exact Fourier coefficients of 𝐵-splines with nonequidistant knots*, Z. Angew. Math. Phys.**29**(1978), no. 2, 301–305 (English, with German summary). MR**498770**, https://doi.org/10.1007/BF01601524**[18]**R. Piessens & M. Branders, "Computation of oscillating integrals,"*J. Comput. Appl. Math.*, v. 1, 1975, pp. 153-164.**[19]**Ann Haegemans,*Algorithm 34: an algorithm for the automatic integration over a triangle*, Computing**19**(1977), no. 2, 179–187 (English, with German summary). MR**455302**, https://doi.org/10.1007/BF02252356**[20]**I. J. Schoenberg,*Contributions to the problem of approximation of equidistant data by analytic functions. Part A. On the problem of smoothing or graduation. A first class of analytic approximation formulae*, Quart. Appl. Math.**4**(1946), 45–99. MR**0015914**, https://doi.org/10.1090/S0033-569X-1946-15914-5**[21]**I. J. Schoenberg,*Cardinal spline interpolation*, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1973. Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 12. MR**0420078****[22]**A. E. Siegman & E. A. Sziklas, "Mode calculations in unstable resonators with flowing saturable gain, 2: Fast Fourier transform method,"*Appl. Optics*, v. 14, 1975, pp. 1874-1889.**[23]**Sherwood D. Silliman,*The numerical evaluation by splines of Fourier transforms*, J. Approximation Theory**12**(1974), 32–51. MR**356556**, https://doi.org/10.1016/0021-9045(74)90056-2**[24]**R. C. Singleton, "An algorithm for computing the mixed radix fast Fourier transform,"*IEEE Trans. Audio Electroacoust.*, v. AU-17, 1969, pp. 93-103.**[25]**F. D. Tappert,*Numerical Solutions of the Korteweg-de Vries Equation and its Generalizations by the Split-Step Fourier Method*, Lectures in Appl. Math., vol. 15, Amer. Math. Soc., Providence, R. I., 1974, pp. 215-216.

Retrieve articles in *Mathematics of Computation*
with MSC:
65D30,
42A15,
65R10

Retrieve articles in all journals with MSC: 65D30, 42A15, 65R10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1982-0669645-5

Keywords:
Fourier integral,
*B*-splines,
fast Fourier transform,
continuous Fourier transform

Article copyright:
© Copyright 1982
American Mathematical Society