Fast structured Jacobi-Jacobi transforms

Jacobi polynomials are frequently used in scientific and engineering applications, and often times, one needs to use the so-called Jacobi-Jacobi transforms which are transforms between two Jacobi expansions with different indices. In this paper, we develop a fast structured algorithm for Jacobi-Jacobi transforms. The algorithm is based on two main ingredients. (i) Derive explicit formulas for connection matrices of two Jacobi expansions with arbitrary indices. In particular, if the indices have integer differences, the connection matrices are relatively sparse or highly structured. The benefit of simultaneous promotion or demotion of the indices is shown. (ii) If the indices have non-integer differences, we explore analytically or numerically a low-rank property hidden in the connection matrices. Combining these two ingredients, we develop a fast structured Jacobi-Jacobi transform with nearly linear complexity, after a one-time precomputation with quadratic complexity, between coefficients of two Jacobi expansions with arbitrary indices. An important byproduct of the fast Jacobi-Jacobi transform is the fast Jacobi transform between the function values at a set of Chebyshev-Gauss-type points and coefficients of the Jacobi expansion with arbitrary indices. Ample numerical results are presented to illustrate the computational efficiency and accuracy of our algorithm.