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?)

  • [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

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
Keywords: Generalized Hilbert matrices, fast algorithms, computational complexity, singular integrals
Article copyright: © Copyright 1988 American Mathematical Society