# How do I do Chebyshev interpolation in multi-dimentional space?

This topic is used in spectral methods, for collocation grid.

Literature mentions Chebyshev interpolation on a grid (defined by $\xi_j = cos(\pi \cdot j/N)$, $x_j = (\xi_j+1) L/2$, $j=0,...,N$) includes 2 steps

1/ Calculation of Chebyshev coefficients (sum over all points $x$)

$c_n = \sum_{j=0}^N f(x_j) \cdot T_n (\xi_j)\cdot w_j$ — In the $x$ direction. Does not depend on a specific $x$, only on $n$...

2/ The interpolation itself

$result(x) = \sum_{n=0}^{N} c_n \cdot T_n\left ( 2\cdot {x \over L}-1\right )$

How can the same be done in 2-dimensional space?

I could come up with these steps, but no literature supporting such point.

(This is $N_x + N_y$ coefficients, as mentioned in one of the answers.)

A. Calculation of Chebyshev coefficients (sum over all points $x$)

• $c_n^{(y_0)} = \sum_{j=0}^{N_x} f(x_j, y_0) \cdot T_n (\xi_j)\cdot w^{(x)}_j$ — in the $x$ direction
• $d_n^{(x_0)} = \sum_{k=0}^{N_y} f(x_0, y_k) \cdot T_n (\eta_k)\cdot w^{(y)}_k$ — in the $y$ direction

B. The interpolation itself $$result(x,y) = \sum_{n=0}^{N_x} \sum_{k=0}^{N_y} c_n^{(y_k)} d_n^{(x_n)} \cdot T_n\left ( 2\cdot {x \over L_x}-1\right ) \cdot T_k\left ( 2\cdot {y \over L_y}-1\right )$$

(Or these two steps, which are a quite different thing.)

(This is $N_x \cdot N_y$ coefficients, as mentioned in one of the answers.)

A. Calculation of Chebyshev coefficients (sum over all points $x$) $$c_{n,k} = \sum_{j=0}^{N_y} \sum_{i=0}^{N_x} f(x_i, y_j) \cdot T_n (\xi_i)\cdot T_k (\eta_j)\cdot w^{(x)}_i \cdot w^{(y)}_j$$ B. The interpolation itself $$result(x,y) = \sum_{i=0}^{N_x} \sum_{j=0}^{N_y} c_{i,j} \cdot T_i\left ( 2\cdot {x \over L_x}-1\right ) \cdot T_j\left ( 2\cdot {y \over L_y}-1\right )$$

• You might want to consider using the Padua points instead. – J. M. Apr 19 '17 at 1:12

Note that it's most common to use a nodal (rather than modal) Chebyshev basis, in which case the coefficients are just the values at the Chebyshev nodes.

Your definition is not a very useful interpolation in 2D. You want something like

$$\mathrm{result}(x,y) = \sum_{n=0}^{N_x} \sum_{k=0}^{N_y} c_{n,k} T_n\left(\frac{2 x}{L_x} - 1\right) T_k\left(\frac{2 y}{L_y} - 1\right).$$

Note that this has $N_x N_y$ coefficients rather than $N_x + N_y$. If the functions you want to represent have rapid decay in mixed derivatives, you can use "sparse grids" to reduce the number of coefficients.

• This is version 2 from the question? – user5273 Jan 30 '14 at 2:15
• That version did not exist when I was writing. Your indices look mixed up. – Jed Brown Jan 30 '14 at 5:38
• Do they look correct now? – user5273 Jan 30 '14 at 23:15
• Hi Jed, Is $C_{nk}$ simply $C_n*C_k$ where $C_{n/k}$ is defined 1-d Chebyshev grid? – lorniper Jan 24 '17 at 21:04
• @lorniper No. There are $N_x N_y$ degrees of freedom, but your suggestion would have only $N_x + N_y$ data. – Jed Brown Jan 25 '17 at 21:14