Representation of sparse Legendre expansions (Q1930163)

The sparse Legendre representation is of the form \(f(t)=\sum_{j=1}^M c_j P_{e_j}(t)\) where \(P_{e_j}\) represents a Legendre polynomial of degree \(e_j\). In this paper, an algorithm is given to compute the degrees \(0\leq e_1<e_2<\cdots<e_M=N\) and the coefficients \(\{c_j\}_{j=1}^M\) where \(M\ll N\), given the values \(f(1),f'(1),\ldots,f^{(2M-1)}(1)\). The \(e_j\) are computed from the values \(z_j=e_j(e_j+1)/2\). The latter appear naturally in the process of taking derivatives. The \(z_j\) are found as the zeros of a polynomial whose coefficients can be computed by solving a linear Hankel system. Once the degrees \(e_j\) are known, the coefficients \(c_j\) can also be computed by solving a linear system.