×

A fast algorithm for the multiplication of generalized Hilbert matrices with vectors. (English) Zbl 0648.65040

The generalized Hilbert matrices \(B_ p\), \(p=1,2,...,q\) \((q\ll n)\) are defined by: \((B_ p)_{i,j}=(t_ i-s_ j)^{-p}\), \(i,j=1,2,...,n\); where \(t_ i\) and \(s_ i\) are distinct points in the complex plane and \(t_ i\neq s_ j\). A fast algorithm with an \(O_ A(n(\log n)^ 2)\) time complexity for the multiplication of these matrices with vectors is presented. [For the definition of \(O_ A(f(n))\) see A. V. Aho, J. E. Hopcroft and J. D. Ullman, The design and analysis of computer algorithms (1974; Zbl 0326.68005)]. This algorithm extends a previous one for Trummer’s problem [cf. the author, M. D. Grigoriadis and L. Sun, SIAM J. Sci. Stat. Comput. 8, 135-138 (1987; Zbl 0618.65030)]. Stable implementation of the algorithm for sets of Chebyshev points and for the nth roots of unity are given; these points appear in the quadrature approximation of Cauchy singular integrals.
Reviewer: A.de Castro

MSC:

65F30 Other matrix algorithms (MSC2010)
65R20 Numerical methods for integral equations
65D30 Numerical integration
68Q25 Analysis of algorithms and problem complexity

Software:

FFTPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[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. · Zbl 0326.68005
[2] M. Comninou, ”The interface crack,” J. Appl. Mech., Transactions of ASME, 1977, pp. 631-636. · Zbl 0369.73092
[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. · Zbl 0344.65020
[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.
[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. · Zbl 0522.65088
[6] F. Erdogan and G. D. Gupta, On the numerical solution of singular integral equations, Quart. Appl. Math. 29 (1971/72), 525 – 534. · Zbl 0236.65083
[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). · Zbl 0213.16303
[8] Walter Gautschi and Jet Wimp, Computing the Hilbert transform of a Jacobi weight function, BIT 27 (1987), no. 2, 203 – 215. · Zbl 0629.65023 · doi: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. · Zbl 0476.65090 · doi:10.1007/BF01941474
[10] A. Gerasoulis, ”Singular integral equations: Direct and iterative variant methods,” Numerical Solution of Singular Integral Equations , 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. · Zbl 0618.65030 · doi: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. · Zbl 0629.65005 · doi: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. · Zbl 0313.30001
[15] E. Horowitz, ”A unified view of the complexity of evaluation and interpolation,” Acta Inform., v. 3, 1974, pp. 123-133. · Zbl 0263.65008
[16] N. I. Ioakimidis, Three iterative methods for the numerical determination of stress intensity factors, Engrg. Fracture Mech. 14 (1981), no. 3, 557 – 564.
[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. · Zbl 0706.11047
[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. · Zbl 0629.65122 · doi: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. · Zbl 0596.30013 · doi: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. · Zbl 0478.65078 · doi:10.1016/0045-7825(82)90048-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.