Evaluation of Fourier integrals using 𝐵-splines

Lax, M.; Agrawal, G. P.

doi:10.1090/S0025-5718-1982-0669645-5

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 ${10^{ - 2}}$ , whereas the same information used by the CFT algorithm yields errors of order ${10^{ - 7}}$ --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.