Fast measure modification of orthogonal polynomials via matrices with displacement structure

It is well known that matrices with low Hessenberg-structured displacement rank enjoy fast algorithms for certain matrix factorizations. We show how $n\times n$ principal finite sections of the Gram matrix for the orthogonal polynomial measure modification problem has such a displacement structure, unlocking a collection of fast algorithms for computing connection coefficients (as the upper-triangular Cholesky factor) between a known orthogonal polynomial family and the modified family. In general, the ${\cal O}(n^3)$ complexity is reduced to ${\cal O}(n^2)$, and if the symmetric Gram matrix has upper and lower bandwidth b, then the ${\cal O}(b^2n)$ complexity for a banded Cholesky factorization is reduced to ${\cal O}(b n)$. In the case of modified Chebyshev polynomials, we show that the Gram matrix is a symmetric Toeplitz-plus-Hankel matrix, and if the modified Chebyshev moments decay algebraically, then a hierarchical off-diagonal low-rank structure is observed in the Gram matrix, enabling a further reduction in the complexity of an approximate Cholesky factorization powered by randomized numerical linear algebra.