Evaluation of Fourier integrals using $B$-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.
- 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, DOI https://doi.org/10.1016/0021-9991%2873%2990146-0 M. Abramowitz & I. A. Stegun (Editors), Handbook of Mathematical Functions, Dover, New York, 1965, p. 300. 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.
- Philip J. Davis, Interpolation and approximation, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1963. MR 0157156
- Carl de Boor, On calculating with $B$-splines, J. Approximation Theory 6 (1972), 50–62. MR 338617, DOI https://doi.org/10.1016/0021-9045%2872%2990080-9
- Carl de Boor, Package for calculating with $B$-splines, SIAM J. Numer. Anal. 14 (1977), no. 3, 441–472. MR 428691, DOI https://doi.org/10.1137/0714026
- Bo Einarsson, Numerical calculation of Fourier integrals with cubic splines, Nordisk Tidskr. Informationsbehandling (BIT) 8 (1968), 279–286. MR 239757, DOI https://doi.org/10.1007/bf01933438
- Bo Einarsson, Use of Richardson extrapolation for the numerical calculation of Fourier transforms, J. Comput. Phys. 21 (1976), no. 3, 365–370. MR 416080, DOI https://doi.org/10.1016/0021-9991%2876%2990036-x L. N. G. Filon, "On a quadrature formula for trigonometric integrals," Proc. Roy. Soc. Edinburgh, v. 49, 1928, pp. 38-47. 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. J. Gazdag, "Numerical convective schemes based on accurate computation of space derivatives," J. Comput. Phys., v. 13, 1973, pp. 100-113.
- R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. Assoc. Comput. Mach. 12 (1965), 95–113. MR 213048, DOI https://doi.org/10.1145/321250.321259 H. Jeffreys & B. S. Jeffreys, Methods of Mathematical Physics, Cambridge Univ. Press, Oxford, 1978, p. 262. 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.
- 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, DOI https://doi.org/10.1016/0021-9991%2872%2990005-8
- 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
- Jürg T. Marti, An algorithm recursively computing the exact Fourier coefficients of $B$-splines with nonequidistant knots, Z. Angew. Math. Phys. 29 (1978), no. 2, 301–305 (English, with German summary). MR 498770, DOI https://doi.org/10.1007/BF01601524 R. Piessens & M. Branders, "Computation of oscillating integrals," J. Comput. Appl. Math., v. 1, 1975, pp. 153-164.
- 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, DOI https://doi.org/10.1007/BF02252356
- 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 15914, DOI https://doi.org/10.1090/S0033-569X-1946-15914-5
- 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 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.
- Sherwood D. Silliman, The numerical evaluation by splines of Fourier transforms, J. Approximation Theory 12 (1974), 32–51. MR 356556, DOI https://doi.org/10.1016/0021-9045%2874%2990056-2 R. C. Singleton, "An algorithm for computing the mixed radix fast Fourier transform," IEEE Trans. Audio Electroacoust., v. AU-17, 1969, pp. 93-103. 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
Keywords:
Fourier integral,
<I>B</I>-splines,
fast Fourier transform,
continuous Fourier transform
Article copyright:
© Copyright 1982
American Mathematical Society