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

DOI:
https://doi.org/10.1090/S0025-5718-1988-0917825-9

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 *n*th 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)$.

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The design and analysis of computer algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR**0413592**
M. Comninou, "The interface crack," - Paul Concus and Gene H. Golub,
*A generalized conjugate gradient method for nonsymmetric systems of linear equations*, Computing methods in applied sciences and engineering (Second Internat. Sympos., Versailles, 1975) Springer, Berlin, 1976, pp. 56–65. Lecture Notes in Econom. and Math. Systems, Vol. 134. MR**0468130** - Ȧke Björck and Germund Dahlquist,
*Numerical methods*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Translated from the Swedish by Ned Anderson; Prentice-Hall Series in Automatic Computation. MR**0368379** - David Elliott,
*The numerical treatment of singular integral equations—a review*, Treatment of integral equations by numerical methods (Durham, 1982) Academic Press, London, 1982, pp. 297–312. MR**755364** - F. Erdogan and G. D. Gupta,
*On the numerical solution of singular integral equations*, Quart. Appl. Math.**29**(1971/72), 525–534. MR**408277**, DOI https://doi.org/10.1090/S0033-569X-1972-0408277-4 - N. Gastinel,
*Inversion d’une matrice généralisant la matrice de Hilbert*, Chiffres**3**(1960), 149–152 (French, with English, German and Russian summaries). MR**123585** - Walter Gautschi and Jet Wimp,
*Computing the Hilbert transform of a Jacobi weight function*, BIT**27**(1987), no. 2, 203–215. MR**894123**, DOI https://doi.org/10.1007/BF01934185 - Apostolos Gerasoulis,
*On the existence of approximate solutions for singular integral equations of Cauchy type discretized by Gauss-Chebyshev quadrature formulae*, BIT**21**(1981), no. 3, 377–380. MR**640939**, DOI https://doi.org/10.1007/BF01941474
A. Gerasoulis, "Singular integral equations: Direct and iterative variant methods," - A. Gerasoulis, M. D. Grigoriadis, and Liping Sun,
*A fast algorithm for Trummer’s problem*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 1, S135–S138. MR**873954**, DOI https://doi.org/10.1137/0908017
G. H. Golub, "Trummer problem," - L. Greengard and V. Rokhlin,
*A fast algorithm for particle simulations*, J. Comput. Phys.**73**(1987), no. 2, 325–348. MR**918448**, DOI https://doi.org/10.1016/0021-9991%2887%2990140-9 - Peter Henrici,
*Applied and computational complex analysis*, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Volume 1: Power series—integration—conformal mapping—location of zeros; Pure and Applied Mathematics. MR**0372162**
E. Horowitz, "A unified view of the complexity of evaluation and interpolation," - N. I. Ioakimidis,
*Three iterative methods for the numerical determination of stress intensity factors*, Engrg. Fracture Mech.**14**(1981), no. 3, 557–564. MR**618911**
A. Kaya, - V. Rokhlin,
*Rapid solution of integral equations of classical potential theory*, J. Comput. Phys.**60**(1985), no. 2, 187–207. MR**805870**, DOI https://doi.org/10.1016/0021-9991%2885%2990002-6
P. Swarztrauber, FFTPACK, Netlib@anl-mcs, Private communication.
- Manfred R. Trummer,
*An efficient implementation of a conformal mapping method based on the Szegő kernel*, SIAM J. Numer. Anal.**23**(1986), no. 4, 853–872. MR**849287**, DOI https://doi.org/10.1137/0723055 - G. Tsamasphyros and P. S. Theocaris,
*A recurrence formula for the direct solution of singular integral equations*, Comput. Methods Appl. Mech. Engrg.**31**(1982), no. 1, 79–89. MR**669261**, DOI https://doi.org/10.1016/0045-7825%2882%2990048-2

*J. Appl. Mech.*, Transactions of ASME, 1977, pp. 631-636.

*Numerical Solution of Singular Integral Equations*(Gerasoulis Si Vichnevetsky, eds.), IMACS publication, 1984, pp. 133-141.

*SIGACT News*, v. 17, 1985, No. 2, ACM Special Interest Group on Automata and Computability Theory, p. 17.2-12.

*Acta Inform.*, v. 3, 1974, pp. 123-133.

*Applications of Integral Equations with Strong Singularities in Fracture Mechanics*, Ph.D. thesis, Lehigh University, 1984. A. M. Odlyzko & A. Schönhage,

*Fast Algorithms for Multiple Evaluations of the Riemann Zeta Function*, Technical Report, AT & T Bell Laboratories, Murray Hill, N.J., 1986. L. Reichel,

*A Matrix Problem with Applications to Rapid Solution of Integral Equations*, Report, Department of Mathematics, University of Kentucky, Lexington, 1986.

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