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 time complexity for the multiplication of generalized Hilbert matrices with vectors is shown. These matrices are defined by , , , , where and are distinct points in the complex plane and , . 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 .

**[1]**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****[2]**M. Comninou, "The interface crack,"*J. Appl. Mech.*, Transactions of ASME, 1977, pp. 631-636.**[3]**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****[4]**Ȧ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****[5]**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****[6]**F. Erdogan and G. D. Gupta,*On the numerical solution of singular integral equations*, Quart. Appl. Math.**29**(1971/72), 525–534. MR**0408277****[7]**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**0123585****[8]**Walter Gautschi and Jet Wimp,*Computing the Hilbert transform of a Jacobi weight function*, BIT**27**(1987), no. 2, 203–215. MR**894123**, 10.1007/BF01934185**[9]**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**, 10.1007/BF01941474**[10]**A. Gerasoulis, "Singular integral equations: Direct and iterative variant methods,"*Numerical Solution of Singular Integral Equations*(Gerasoulis Si Vichnevetsky, eds.), IMACS publication, 1984, pp. 133-141.**[11]**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**, 10.1137/0908017**[12]**G. H. Golub, "Trummer problem,"*SIGACT News*, v. 17, 1985, No. 2, ACM Special Interest Group on Automata and Computability Theory, p. 17.2-12.**[13]**L. Greengard and V. Rokhlin,*A fast algorithm for particle simulations*, J. Comput. Phys.**73**(1987), no. 2, 325–348. MR**918448**, 10.1016/0021-9991(87)90140-9**[14]**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****[15]**E. Horowitz, "A unified view of the complexity of evaluation and interpolation,"*Acta Inform.*, v. 3, 1974, pp. 123-133.**[16]**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****[17]**A. Kaya,*Applications of Integral Equations with Strong Singularities in Fracture Mechanics*, Ph.D. thesis, Lehigh University, 1984.**[18]**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.**[19]**L. Reichel,*A Matrix Problem with Applications to Rapid Solution of Integral Equations*, Report, Department of Mathematics, University of Kentucky, Lexington, 1986.**[20]**V. Rokhlin,*Rapid solution of integral equations of classical potential theory*, J. Comput. Phys.**60**(1985), no. 2, 187–207. MR**805870**, 10.1016/0021-9991(85)90002-6**[21]**P. Swarztrauber, FFTPACK, Netlib@anl-mcs, Private communication.**[22]**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**, 10.1137/0723055**[23]**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**, 10.1016/0045-7825(82)90048-2

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

Keywords:
Generalized Hilbert matrices,
fast algorithms,
computational complexity,
singular integrals

Article copyright:
© Copyright 1988
American Mathematical Society