A fast algorithm for the multiplication of generalized Hilbert matrices with vectors
Author:
A. Gerasoulis
Journal:
Math. Comp. 50 (1988), 179188
MSC:
Primary 65F30; Secondary 65D30, 65R20
MathSciNet review:
917825
Fulltext 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 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 .
 [1]
Alfred
V. Aho, John
E. Hopcroft, and Jeffrey
D. Ullman, The design and analysis of computer algorithms,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley Series in Computer Science and Information
Processing. MR
0413592 (54 #1706)
 [2]
M. Comninou, "The interface crack," J. Appl. Mech., Transactions of ASME, 1977, pp. 631636.
 [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
(57 #7968)
 [4]
Ȧke
Björck and Germund
Dahlquist, Numerical methods, PrenticeHall, Inc., Englewood
Cliffs, N.J., 1974. Translated from the Swedish by Ned Anderson;
PrenticeHall Series in Automatic Computation. MR 0368379
(51 #4620)
 [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
(53 #12042)
 [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
(23 #A910)
 [8]
Walter
Gautschi and Jet
Wimp, Computing the Hilbert transform of a Jacobi weight
function, BIT 27 (1987), no. 2, 203–215.
MR 894123
(88i:65154), http://dx.doi.org/10.1007/BF01934185
 [9]
Apostolos
Gerasoulis, On the existence of approximate solutions for singular
integral equations of Cauchy type discretized by GaussChebyshev quadrature
formulae, BIT 21 (1981), no. 3, 377–380.
MR 640939
(82m:65122), http://dx.doi.org/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. 133141.
 [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, http://dx.doi.org/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.212.
 [13]
L.
Greengard and V.
Rokhlin, A fast algorithm for particle simulations, J. Comput.
Phys. 73 (1987), no. 2, 325–348. MR 918448
(88k:82007), http://dx.doi.org/10.1016/00219991(87)901409
 [14]
Peter
Henrici, Applied and computational complex analysis,
WileyInterscience [John Wiley & Sons], New YorkLondonSydney, 1974.
Volume 1: Power series—integration—conformal
mapping—location of zeros; Pure and Applied Mathematics. MR 0372162
(51 #8378)
 [15]
E. Horowitz, "A unified view of the complexity of evaluation and interpolation," Acta Inform., v. 3, 1974, pp. 123133.
 [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
(82h:73071)
 [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
(86k:65120), http://dx.doi.org/10.1016/00219991(85)900026
 [21]
P. Swarztrauber, FFTPACK, Netlib@anlmcs, 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
(87k:30013), http://dx.doi.org/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
(83h:73074), http://dx.doi.org/10.1016/00457825(82)900482
 [1]
 A. Aho, J. E. Hopcroft & J. D. Ullman, The Design and Analysis of Computer Algorithms, AddisonWesley, Reading, Mass., 1974. MR 0413592 (54:1706)
 [2]
 M. Comninou, "The interface crack," J. Appl. Mech., Transactions of ASME, 1977, pp. 631636.
 [3]
 P. Concus & G. H. Golub, A Generalized Conjugate Gradient Method for Nonsymmetric Systems of Linear Equations, Lecture Notes in Economics and Mathematical Systems, v. 134, SpringerVerlag, Berlin, 1976, pp. 5665. MR 0468130 (57:7968)
 [4]
 G. Dahlquist & A. Björck, Numerical Methods, PrenticeHall, Englewood Cliffs, N.J., 1974. MR 0368379 (51:4620)
 [5]
 D. Elliott, "The numerical treatment of singular integral equationsA review," Treatment of Integral Equations by Numerical Methods (C. T. H. Baker and G. F. Miller, eds.), Academic Press, New York, 1982, pp. 297312. MR 755364
 [6]
 F. Erdogan & G. D. Gupta, "On the numerical solution of singular integral equations," Quart. Appl. Math., v. 29, 1972, pp. 525534. MR 0408277 (53:12042)
 [7]
 N. Gastinel, "Inversion d'une matrice généralisant la matrice de Hilbert," Chiffres, v. 3, 1960, pp. 149152. MR 0123585 (23:A910)
 [8]
 W. Gautschi & J. Wimp, "Computing the Hilbert transform of a Jacobi weight function," BIT, v. 27, 1987, pp. 203215. MR 894123 (88i:65154)
 [9]
 A. Gerasoulis, "On the existence of approximate solutions for singular integral equations of Cauchy type discretized by GaussChebyshev quadrature formulae," BIT, v. 21, 1981, pp. 377380. MR 640939 (82m:65122)
 [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. 133141.
 [11]
 A. Gerasoulis, M. D. Grigoriadis & Liping Sun, "A fast algorithm for Trummer's problem," SIAM J. Sci. Statist. Comput., v. 8, 1987, pp. sl35sl38. MR 873954
 [12]
 G. H. Golub, "Trummer problem," SIGACT News, v. 17, 1985, No. 2, ACM Special Interest Group on Automata and Computability Theory, p. 17.212.
 [13]
 L. Greengard & V. Rokhlin, A Fast Algorithm for Particle Simulations, Research report YALEU/DCS/RR459, April 1986. MR 918448 (88k:82007)
 [14]
 P. Henrici, Applied and Computational Complex Analysis, III, Wiley, New York, 1986. MR 0372162 (51:8378)
 [15]
 E. Horowitz, "A unified view of the complexity of evaluation and interpolation," Acta Inform., v. 3, 1974, pp. 123133.
 [16]
 N. I. Ioakimidis, "Three iterative methods for the numerical determination of stress intensity factors," Engrg. Fracture Mech., v. 14, 1981, pp. 557564. MR 618911 (82h:73071)
 [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., v. 60, 1985, pp. 187207. MR 805870 (86k:65120)
 [21]
 P. Swarztrauber, FFTPACK, Netlib@anlmcs, Private communication.
 [22]
 M. Trummer, "An efficient implementation of a conformal mapping method using the Szegö kernel," SIAM J. Numer. Anal., v. 23, 1986, pp. 853872. MR 849287 (87k:30013)
 [23]
 G. Tsamasphyros & P. S. Theocaris, "A recurrence formula for the direct solution of singular integral equations," Comput. Methods Appl. Mech. Engrg., v. 31, 1982, pp. 7989. MR 669261 (83h:73074)
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/S00255718198809178259
PII:
S 00255718(1988)09178259
Keywords:
Generalized Hilbert matrices,
fast algorithms,
computational complexity,
singular integrals
Article copyright:
© Copyright 1988
American Mathematical Society
