Computation of Gauss-Kronrod quadrature rules
HTML articles powered by AMS MathViewer
- by D. Calvetti, G. H. Golub, W. B. Gragg and L. Reichel PDF
- Math. Comp. 69 (2000), 1035-1052 Request permission
Abstract:
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
- 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.
- Daniel Boley and Gene H. Golub, A survey of matrix inverse eigenvalue problems, Inverse Problems 3 (1987), no. 4, 595–622. MR 928047
- Carlos F. Borges and William B. Gragg, A parallel divide and conquer algorithm for the generalized real symmetric definite tridiagonal eigenproblem, Numerical linear algebra (Kent, OH, 1992) de Gruyter, Berlin, 1993, pp. 11–29. MR 1244151
- J. M. Bull and T. L. Freeman, Parallel globally adaptive quadrature on the KSR-1, Adv. Comput. Math., 2 (1994), pp. 357–373.
- D. Calvetti and L. Reichel, On an inverse eigenproblem for Jacobi matrices, Adv. Comput. Math., 11 (1999), pp. 11–20.
- Walter Gautschi, On generating orthogonal polynomials, SIAM J. Sci. Statist. Comput. 3 (1982), no. 3, 289–317. MR 667829, DOI 10.1137/0903018
- Walter Gautschi, Gauss-Kronrod quadrature—a survey, Numerical methods and approximation theory, III (Niš, 1987) Univ. Niš, Niš, 1988, pp. 39–66. MR 960329
- I. Gladwell, Vectorisation of one-dimensional quadrature codes, Numerical integration (Halifax, N.S., 1986) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 203, Reidel, Dordrecht, 1987, pp. 231–238. MR 907123
- G. H. Golub and J. Kautský, Calculation of Gauss quadratures with multiple free and fixed knots, Numer. Math. 41 (1983), no. 2, 147–163. MR 703119, DOI 10.1007/BF01390210
- Gene H. Golub and John H. Welsch, Calculation of Gauss quadrature rules, Math. Comp. 23 (1969), 221-230; addendum, ibid. 23 (1969), no. 106, loose microfiche suppl, A1–A10. MR 0245201, DOI 10.1090/S0025-5718-69-99647-1
- Ming Gu and Stanley C. Eisenstat, A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J. Matrix Anal. Appl. 16 (1995), no. 1, 172–191. MR 1311425, DOI 10.1137/S0895479892241287
- Dirk P. Laurie, Calculation of Gauss-Kronrod quadrature rules, Math. Comp. 66 (1997), no. 219, 1133–1145. MR 1422788, DOI 10.1090/S0025-5718-97-00861-2
- Giovanni Monegato, A note on extended Gaussian quadrature rules, Math. Comp. 30 (1976), no. 136, 812–817. MR 440878, DOI 10.1090/S0025-5718-1976-0440878-3
- Giovanni Monegato, Stieltjes polynomials and related quadrature rules, SIAM Rev. 24 (1982), no. 2, 137–158. MR 652464, DOI 10.1137/1024039
- 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.
- Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society Colloquium Publications, Vol. XXIII, American Mathematical Society, Providence, R.I., 1975. MR 0372517
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
- 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. - © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 69 (2000), 1035-1052
- MSC (1991): Primary 65D30, 65D32
- DOI: https://doi.org/10.1090/S0025-5718-00-01174-1
- MathSciNet review: 1677474