Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1988-0917825-9
PII: S 0025-5718(1988)0917825-9
Keywords: Generalized Hilbert matrices, fast algorithms, computational complexity, singular integrals
Article copyright: © Copyright 1988 American Mathematical Society