# zbMATH — the first resource for mathematics

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.

##### MSC:
 65B10 Numerical summation of series 65D05 Numerical interpolation 65T50 Numerical methods for discrete and fast Fourier transforms
Full Text:
##### References:
 [1] Boyd, J.P., Chebyshev and Fourier spectral methods, (1989), Springer-Verlag New York [2] Canuto, C.; Hussaini, M.Y.; Quarteroni, A.; Zang, T.A., Spectral methods in fluid dynamics, (1987), Springer-Verlag New York/Berlin · Zbl 0636.76009 [3] Bayliss, A.; Matkowsky, B.J., J. comput. phys., 71, 147, (1987) [4] Bayliss, A.; Gottlieb, D.; Matkowsky, B.J.; Minkoff, M., J. comput. phys., 81, 421, (1989) [5] Guillard, H.; Peyret, R., Comput. meth. appl. mech. eng., 66, 17, (1988) [6] Augenbaum, J., Appl. numer. math., 5, 459, (1989) [7] Augenbaum, J., (), 19 [8] Morse, P.M.; Feshbach, H., () [9] Boyd, J.P.; Moore, D.W., Dyn. atmos. oceans, 10, 51, (1986) [10] Boyd, J.P., Appl. numer. math., 7, 287, (1991) [11] Lanczos, C., Applied analysis, (), 457 · Zbl 0111.12403 [12] Hamming, R.W., Numerical methods for scientists and engineers, (), 485 · Zbl 0952.65501 [13] Gradshteyn, I.S.; Ryzhik, I.M., Table of integrals, series, and products, (), 1075 · Zbl 0918.65002 [14] Hildebrand, F.B., Introduction to numerical analysis, (), 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) [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) [20] Rasch, P.J.; Williamson, D.L., SIAM J. sci. stat. comput., 11, 656, (1990) [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)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.