Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: A. Gerasoulis
Journal: Math. Comp. 50 (1988), 179-188
MSC: Primary 65F30; Secondary 65D30, 65R20
MathSciNet review: 917825
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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)$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30, 65D30, 65R20

Retrieve articles in all journals with MSC: 65F30, 65D30, 65R20

Additional Information

Keywords: Generalized Hilbert matrices, fast algorithms, computational complexity, singular integrals
Article copyright: © Copyright 1988 American Mathematical Society