|
Computation of Gauss-Kronrod quadrature rules
Author(s):
D.
Calvetti;
G.
H.
Golub;
W.
B.
Gragg;
L.
Reichel.
Journal:
Math. Comp.
69
(2000),
1035-1052.
MSC (1991):
Primary 65D30, 65D32
Posted:
February 17, 2000
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
Recently Laurie presented a new algorithm for the computation of  -point Gauss-Kronrod quadrature rules with real nodes and positive weights. This algorithm first determines a symmetric tridiagonal matrix of order  from certain mixed moments, and then computes a partial spectral factorization. We describe a new algorithm that does not require the entries of the tridiagonal matrix to be determined, and thereby avoids computations that can be sensitive to perturbations. Our algorithm uses the consolidation phase of a divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem. We also discuss how the algorithm can be applied to compute Kronrod extensions of Gauss-Radau and Gauss-Lobatto quadrature rules. Throughout the paper we emphasize how the structure of the algorithm makes efficient implementation on parallel computers possible. Numerical examples illustrate the performance of the algorithm.
References:
- 1.
- E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov and D. Sorensen, LAPACK Users' Guide, SIAM, Philadelphia, 1992.
- 2.
- D. Boley and G. H. Golub, A survey of matrix inverse eigenvalue problems, Inverse Problems, 3 (1987), pp. 595-622. MR 89m:65036
- 3.
- C. F. Borges and W. B. Gragg, A parallel divide and conquer algorithm for the generalized symmetric definite tridiagonal eigenvalue problem, Numerical Linear Algebra, (L. Reichel, A. Ruttan and R. S. Varga, eds.), de Gruyter, Berlin, 1993, pp. 11-29. MR 94k:65051
- 4.
- J. M. Bull and T. L. Freeman, Parallel globally adaptive quadrature on the KSR-1, Adv. Comput. Math., 2 (1994), pp. 357-373. CMP 95:01
- 5.
- D. Calvetti and L. Reichel, On an inverse eigenproblem for Jacobi matrices, Adv. Comput. Math., 11 (1999), pp. 11-20.
- 6.
- W. Gautschi, On generating orthogonal polynomials, SIAM J. Sci. Stat. Comput., 3 (1982), pp. 289-317. MR 84e:65022
- 7.
- W. Gautschi, Gauss-Kronrod quadrature--a survey, Numerical Methods and Approximation Theory III, (G. V. Milovanovic, ed.), University of Nis, 1987, pp. 39-66. MR 89k:41035
- 8.
- I. Gladwell, Vectorization of one dimensional quadrature codes, Numerical Integration, (P. Keast and G. Fairweather, eds.), Reidel, Dordrecht, 1987, pp. 231-238. MR 88i:65039
- 9.
- G. H. Golub and J. Kautsky, Calculation of Gauss quadratures with multiple free and fixed knots, Numer. Math., 41 (1983), pp. 147-163. MR 84i:65030
- 10.
- G. H. Golub and J. H. Welsch, Calculation of Gauss quadrature rules, Math. Comp., 23 (1969), pp. 221-230. MR 39:6513
- 11.
- M. Gu and S. C. Eisenstat, A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 172-191. MR 95j:65035
- 12.
- D. P. Laurie, Calculation of Gauss-Kronrod quadrature rules, Math. Comp., 66 (1997), pp. 1133-1145. MR 98m:65030
- 13.
- G. Monegato, A note on extended Gaussian quadrature rules, Math. Comp., 30 (1976), pp. 812-817. MR 55:13746
- 14.
- G. Monegato, Stieltjes polynomials and related quadrature rules, SIAM Rev., 24 (1982), pp. 137-158. MR 83d:65067
- 15.
- M. A. Napierala and I. Gladwell, Reducing ranking effects in parallel adaptive quadrature, in Proc. Seventh SIAM Conference on Parallel Processing for Scientific Computing, D. H. Bailey, J. R. Gilbert, M. V. Masagni, R. S. Schreiber, H. D. Simon, V. J. Torzon and L. T. Watson, eds., SIAM, Philadelphia, 1995, pp. 261-266.
- 16.
- G. Szego, Orthogonal Polynomials, 4th ed., Amer. Math. Society, Providence, 1975. MR 51:8724
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(1991):
65D30, 65D32
Retrieve articles in all Journals with MSC
(1991):
65D30, 65D32
Additional Information:
D.
Calvetti
Affiliation:
Department of Mathematics, Case Western Reserve University, Cleveland, Ohio 44106
Email:
dxc57@po.cwru.edu
G.
H.
Golub
Affiliation:
Department of Computer Science, Stanford University, Stanford, California 94305
Email:
golub@chebyshev.stanford.edu
W.
B.
Gragg
Affiliation:
Department of Mathematics, Naval Postgraduate School, Monterey, California 93943
Email:
gragg@nps.navy.mil
L.
Reichel
Affiliation:
Department of Mathematics and Computer Science, Kent State University, Kent, Ohio 44242
Email:
reichel@mcs.kent.edu
DOI:
10.1090/S0025-5718-00-01174-1
PII:
S 0025-5718(00)01174-1
Keywords:
Jacobi matrix,
inverse eigenvalue problem,
divide-and-conquer algorithm,
generalized Gauss-Kronrod rule
Received by editor(s):
May 12, 1998
Posted:
February 17, 2000
Additional Notes:
Research of the first author was supported in part by NSF grants DMS-9404692 and DMS-9896073.
Research of the second author was supported in part by NSF grant CCR-9505393.
Research of the fourth author was supported in part by NSF grant DMS-9404706.
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org