Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computation of Gauss-Kronrod quadrature rules

Authors: D. Calvetti, G. H. Golub, W. B. Gragg and L. Reichel
Journal: Math. Comp. 69 (2000), 1035-1052
MSC (1991): Primary 65D30, 65D32
Published electronically: February 17, 2000
MathSciNet review: 1677474
Full-text PDF

Abstract | References | Similar Articles | Additional Information


Recently Laurie presented a new algorithm for the computation of $(2n+1)$-point Gauss-Kronrod quadrature rules with real nodes and positive weights. This algorithm first determines a symmetric tridiagonal matrix of order $2n+1$ 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 [Enhancements On Off] (What's this?)

  • 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 of the American Mathematical Society 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

G. H. Golub
Affiliation: Department of Computer Science, Stanford University, Stanford, California 94305

W. B. Gragg
Affiliation: Department of Mathematics, Naval Postgraduate School, Monterey, California 93943

L. Reichel
Affiliation: Department of Mathematics and Computer Science, Kent State University, Kent, Ohio 44242

Keywords: Jacobi matrix, inverse eigenvalue problem, divide-and-conquer algorithm, generalized Gauss-Kronrod rule
Received by editor(s): May 12, 1998
Published electronically: 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.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society