The spectral connection matrix for classical orthogonal polynomials of a single parameter

In this paper we study the so-called connection problem of, given a polynomial expressed in the basis of one set of orthogonal polynomials, computing the coefficients with respect to a different set of orthogonal polynomials. We restrict our current study to the classical real orthogonal polynomials of the Hermite, Laguerre, and Gegenbauer (including Legendre) families.The computational tool for this work is the class of quasiseparable matrices. While the relationships between orthogonal polynomials and rank-structured matrices such as quasiseparable matrices are very well-known, in this paper we investigate a more recently considered relationship. We prove that, while the matrix that implements the desired connection is not itself quasiseparable, it is an eigenvector matrix of one that is quasiseparable. We suggest to refer to this structured matrix as the spectral connection matrix.Finally, we present a simple algorithm exploiting the computationally favorable properties of quasiseparable matrices to implement the desired change of basis. By exploiting the quasiseparable structure, this algorithm enjoys an order of magnitude reduction of complexity as compared to the simple method of inverting the connection matrix directly. While not the focus of the paper, some very preliminary numerical experimentation shows some positive indications that even with this reduction in complexity the accuracy of the resulting change of basis algorithm is comparable to that of inverting the connection matrix directly.