Volume 30, pp. 26-53, 2008.

Gegenbauer polynomials and semiseparable matrices

Jens Keiner

Abstract

In this paper, we develop a new $\mathcal{O}(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\times n$ matrix can be computed explicitly with $\mathcal{O}\left(n^2\right)$ arithmetic operations and the eigenvector matrix can be applied to an arbitrary vector at cost $\mathcal{O}(n\log n)$. All algorithms are accurate up to a prefixed accuracy $\epsilon$. We provide brief numerical results.

Full Text (PDF) [359 KB], BibTeX

Key words

Gegenbauer polynomials, polynomial transforms, semiseparable matrices, eigendecomposition, spectral divide-and-conquer methods

AMS subject classifications

42C10, 42C20, 15A18, 15A23, 15A57, 65T50, 65Y20