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

DOI:
https://doi.org/10.1090/S0025-5718-00-01174-1

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 -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.

**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**

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:
https://doi.org/10.1090/S0025-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

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