Fast evaluation of discrete integral transforms by Chebyshev and Leja polynomial approximation

We present and compare two fast methods for the evaluation of a discrete integral transform (T_n u)_i = \sum_{}^n w_j K(x_i, t_j , u_j), i = 1, ..., q , where n and q are large, based on polynomial approximation of the action of the transform. The first resorts to truncated Chebyshev series expansion while the second reduces to interpolation at Leja sequences. Our approach has a different conception compared with other well-known fast methods, which usually work on the kernel and are restricted to linear transforms. Working instead on the action of T_n, we are able to exploit the “smoothing effect” of integration and to treat also nonlinear instances. Both Chebyshev and Leja polynomial approximation reduce the complexity from O(nq) to O(n + q) in several applications, but the Leja approach turns out to be more efficient and shows speed-up ratios, w.r.t. direct evaluation, up to two orders of magnitude.