January 25 - 27, 2007

Diagonal plus upper or lower triangular semi-separable matrices and fast Gegenbauer polynomial transforms

Jens Keiner (University of Lübeck)

We develop an efficient algorithm for computing the eigendecomposition of diagonal plus upper or lower triangular semiseparable matrices for which the eigenvalues are always known a-priori. By using fast summation techniques, we obtain an O(n2) algorithm for computing the eigenvectors explicitly and an O(n log n) algorithm for applying the eigenvector matrix, or optionally its inverse, to an arbitrary vector. Both algorithms are approximate, i.e. accurate up to a prefixed accuracy ε. This extends an existing divide-and-conquer algorithm for symmetric diagonal plus semiseparable matrices. As an application, we develop a fast algorithm for converting expansion coefficients between different representations in terms of Gegenbauer polynomials.

Impressum       Valid HTML 4.0 Transitional