A fast algorithm for the multiplication of generalized Hilbert matrices with vectors

Abstract:

The existence of a fast algorithm with an ${O_A}(n{(\log n)^2})$ time complexity for the multiplication of generalized Hilbert matrices with vectors is shown. These matrices are defined by ${({B_p})_{i,j}} = 1/{({t_i} - {s_j})^p}$, $i,j = 1, \ldots ,n$, $p = 1, \ldots ,q$, $q \ll n$, where ${t_i}$ and ${s_i}$ are distinct points in the complex plane and ${t_i} \ne {s_j}$, $i,j = 1, \ldots ,n$. The major contribution of the paper is the stable implementation of the algorithm for two important sets of points, the Chebyshev points and the nth roots of unity. Such points have applications in the numerical approximation of Cauchy singular integral equations. The time complexity of the algorithm, for these special sets of points, reduces to ${O_A}(n\log n)$.