A fast algorithm for Chebyshev, Fourier, and sinc interpolation onto an irregular grid. (English) Zbl 0768.65001
The problem is to evaluate efficiently the interpolatory sum \(f(x) \cong\sum f(x_ j)C_ j(x)\) at a set of \(N\) points which do not coincide with the regularly spaced interpolation points \(\{x_ j\}\). The fast Fourier transform (FFT) technique does not apply in this case and the cost of operations of direct summation becomes \(O(N^ 2)\) instead of \(O(N\log N)\) for FFT.
The author proposes an alternative solution: to use the FFT of length \(3N\) to interpolate the Chebyshev series to a very fine grid and then to apply the \(M\)th order Euler sum acceleration (or (\(2M+1\))-point Lagrangian interpolation) with \(M << N\) to approximate \(f\) on the irregular grid. The cost of interpolation is significantly reduced with no loss of accuracy.
The author proposes an alternative solution: to use the FFT of length \(3N\) to interpolate the Chebyshev series to a very fine grid and then to apply the \(M\)th order Euler sum acceleration (or (\(2M+1\))-point Lagrangian interpolation) with \(M << N\) to approximate \(f\) on the irregular grid. The cost of interpolation is significantly reduced with no loss of accuracy.
Reviewer: J.Gilewicz (Marseille)
MSC:
| 65B10 | Numerical summation of series |
| 65D05 | Numerical interpolation |
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
Keywords:
summation of series; Chebyshev interpolation; Fourier interpolation; sinc interpolation; interpolatory sum; fast Fourier transform; Chebyshev series; Euler sum acceleration; Lagrangian interpolationReferences:
| [1] | Boyd, J. P., Chebyshev and Fourier Spectral Methods (1989), Springer-Verlag: Springer-Verlag New York · Zbl 0681.65079 |
| [2] | Canuto, C.; Hussaini, M. Y.; Quarteroni, A.; Zang, T. A., Spectral Methods in Fluid Dynamics (1987), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0636.76009 |
| [3] | Bayliss, A.; Matkowsky, B. J., J. Comput. Phys., 71, 147 (1987) · Zbl 0616.65133 |
| [4] | Bayliss, A.; Gottlieb, D.; Matkowsky, B. J.; Minkoff, M., J. Comput. Phys., 81, 421 (1989) · Zbl 0668.65092 |
| [5] | Guillard, H.; Peyret, R., Comput. Meth. Appl. Mech. Eng., 66, 17 (1988) · Zbl 0652.65084 |
| [6] | Augenbaum, J., Appl. Numer. Math., 5, 459 (1989) · Zbl 0684.65103 |
| [7] | Augenbaum, J., (Lee, D.; Cakmak, A.; Vichnevetsky, R., Computational Acoustics-Seismo-Ocean Acoustics and Modeling (1990), Elsevier-North Holland: Elsevier-North Holland Amsterdam), 19 |
| [8] | Morse, P. M.; Feshbach, H., (Methods of Theoretical Physics, Vol. 1 (1953), Wiley: Wiley New York) · Zbl 0051.40603 |
| [9] | Boyd, J. P.; Moore, D. W., Dyn. Atmos. Oceans, 10, 51 (1986) |
| [10] | Boyd, J. P., Appl. Numer. Math., 7, 287 (1991) · Zbl 0726.65019 |
| [11] | Lanczos, C., Applied Analysis, ((1988), Dover: Dover New York), 457 · Zbl 0111.12403 |
| [12] | Hamming, R. W., Numerical methods for Scientists and Engineers, ((1986), Dover: Dover New York), 485 · Zbl 0952.65501 |
| [13] | Gradshteyn, I. S.; Ryzhik, I. M., Table of Integrals, Series, and Products, ((1965), Academic Press: Academic Press New York), 1075 · Zbl 0918.65002 |
| [14] | Hildebrand, F. B., Introduction to Numerical Analysis, ((1987), Dover: Dover New York), 139 · Zbl 0070.12401 |
| [15] | Boyd, J. P., Comput. Meths. Appl. Mech. Eng. (1993), in press |
| [16] | Boyd, J. P., J. Comput. Phys., 103, 184 (1992) · Zbl 0765.65022 |
| [17] | Rosenbaum, J. H.; Boudreaux, G. F., Geophysics, 46, 1667 (1990) |
| [18] | Bisseling, R. H.; Kosloff, R.; Kosloff, D., Comput. Phys. Commun., 39, 313 (1990) |
| [19] | Suli, E.; Ware, A., SIAM J. Numer. Anal., 28, 423 (1991) · Zbl 0743.65080 |
| [20] | Rasch, P. J.; Williamson, D. L., SIAM J. Sci. Stat. Comput., 11, 656 (1990) · Zbl 0707.65007 |
| [21] | Kuo, H.-C.; Williams, R. T., Mon. Weather Rev., 118, 1278 (1990) |
| [22] | Smolarkiewicz, P. K.; Rasch, P. J., J. Atmos. Sci., 48, 793 (1991) |
| [23] | Maday, Y.; Patera, A. T.; Ronquist, E. M., J. Sci. Comput., 5, 263 (1990) · Zbl 0724.76070 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
