Gegenbauer polynomials and semiseparable matrices

In this paper, we develop a new Ο(n log n) algorithm for converting coefficients between expansions in different families of Gegenbauer polynomials up to a finite degree n. To this end, we show that the corresponding linear mapping is represented by the eigenvector matrix of an explicitly known diagonal plus upper triangular semiseparable matrix. The method is based on a new efficient algorithm for computing the eigendecomposition of such a matrix. Using fast summation techniques, the eigenvectors of an n X n matrix can be computed explicitly with Ο (n2) arithmetic operations and the eigenvector matrix can be applied to an arbitrary vector at cost Ο (n log n). All algorithms are accurate up to a prefixed accuracy Ε. We provide brief numerical results. Copyright © 2008, Kent State University.