The structure of matrices in rational Gauss quadrature

Jagels, Carl; Reichel, Lothar

doi:10.1090/S0025-5718-2013-02695-6

The structure of matrices in rational Gauss quadrature
HTML articles powered by AMS MathViewer

by Carl Jagels and Lothar Reichel PDF

Math. Comp. 82 (2013), 2035-2060 Request permission

Abstract:

This paper is concerned with the approximation of matrix functionals defined by a large, sparse or structured, symmetric definite matrix. These functionals are Stieltjes integrals with a measure supported on a compact real interval. Rational Gauss quadrature rules that are designed to exactly integrate Laurent polynomials with a fixed pole in the vicinity of the support of the measure may yield better approximations of these functionals than standard Gauss quadrature rules with the same number of nodes. Therefore it can be attractive to approximate matrix functionals by these rational Gauss rules. We describe the structure of the matrices associated with these quadrature rules, derive remainder terms, and discuss computational aspects. Also discussed are rational Gauss-Radau rules and the applicability of pairs of rational Gauss and Gauss-Radau rules to computing lower and upper bounds for certain matrix functionals.

References

E. J. Allen, J. Baglama, and S. K. Boyd, Numerical approximation of the product of the square root of a matrix with a vector, Linear Algebra Appl. 310 (2000), no. 1-3, 167–181. MR 1753175, DOI 10.1016/S0024-3795(00)00068-9
Gregory S. Ammar and William B. Gragg, Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 9 (1988), no. 1, 61–76. SIAM Conference on Linear Algebra in Signals, Systems, and Control (Boston, Mass., 1986). MR 938136, DOI 10.1137/0609005
Zhaojun Bai, Mark Fahey, and Gene Golub, Some large-scale matrix computation problems, J. Comput. Appl. Math. 74 (1996), no. 1-2, 71–89. TICAM Symposium (Austin, TX, 1995). MR 1430368, DOI 10.1016/0377-0427(96)00018-0
Bernhard Beckermann and Lothar Reichel, Error estimates and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal. 47 (2009), no. 5, 3849–3883. MR 2576523, DOI 10.1137/080741744
Michele Benzi and Paola Boito, Quadrature rule-based bounds for functions of adjacency matrices, Linear Algebra Appl. 433 (2010), no. 3, 637–652. MR 2653828, DOI 10.1016/j.laa.2010.03.035
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
D. Calvetti and L. Reichel, Lanczos-based exponential filtering for discrete ill-posed problems, Numer. Algorithms 29 (2002), no. 1-3, 45–65. Matrix iterative analysis and biorthogonality (Luminy, 2000). MR 1896945, DOI 10.1023/A:1014899604567
C. Díaz-Mendoza, P. González-Vera, M. Jiménez Paiz, and O. Njåstad, Orthogonality and recurrence for ordered Laurent polynomial sequences, J. Comput. Appl. Math. 235 (2010), no. 4, 982–997. MR 2727633, DOI 10.1016/j.cam.2010.07.013
Vladimir Druskin and Leonid Knizhnerman, Extended Krylov subspaces: approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl. 19 (1998), no. 3, 755–771. MR 1616584, DOI 10.1137/S0895479895292400
Vladimir Druskin, Leonid Knizhnerman, and Mikhail Zaslavsky, Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts, SIAM J. Sci. Comput. 31 (2009), no. 5, 3760–3780. MR 2556561, DOI 10.1137/080742403
Walter Gautschi, The interplay between classical analysis and (numerical) linear algebra—a tribute to Gene H. Golub, Electron. Trans. Numer. Anal. 13 (2002), 119–147. MR 1961202
Walter Gautschi, Orthogonal polynomials: computation and approximation, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004. Oxford Science Publications. MR 2061539
Gene H. Golub, Some modified matrix eigenvalue problems, SIAM Rev. 15 (1973), 318–334. MR 329227, DOI 10.1137/1015032
G. H. Golub and Gérard Meurant, Matrices, moments and quadrature, Numerical analysis 1993 (Dundee, 1993) Pitman Res. Notes Math. Ser., vol. 303, Longman Sci. Tech., Harlow, 1994, pp. 105–156. MR 1267758
Gene H. Golub and Gérard Meurant, Matrices, moments and quadrature with applications, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2010. MR 2582949
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
A. A. Gonchar and G. López Lagomasino, On Markov’s theorem for multipoint Padé approximants, Math. USSR Sb., 34 (1978), pp. 449–459.
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
Nicholas J. Higham, Functions of matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Theory and computation. MR 2396439, DOI 10.1137/1.9780898717778
Carl Jagels and Lothar Reichel, The extended Krylov subspace method and orthogonal Laurent polynomials, Linear Algebra Appl. 431 (2009), no. 3-4, 441–458. MR 2528942, DOI 10.1016/j.laa.2009.03.006
Carl Jagels and Lothar Reichel, Recursion relations for the extended Krylov subspace method, Linear Algebra Appl. 434 (2011), no. 7, 1716–1732. MR 2775750, DOI 10.1016/j.laa.2010.08.042
William B. Jones and Olav Njåstad, Orthogonal Laurent polynomials and strong moment theory: a survey, J. Comput. Appl. Math. 105 (1999), no. 1-2, 51–91. Continued fractions and geometric function theory (CONFUN) (Trondheim, 1997). MR 1690578, DOI 10.1016/S0377-0427(99)00027-8
G. López Lagomasino, L. Reichel, and L. Wunderlich, Matrices, moments, and rational quadrature, Linear Algebra Appl. 429 (2008), no. 10, 2540–2554. MR 2456794, DOI 10.1016/j.laa.2008.04.047
O. Njåstad and W. J. Thron, The theory of sequences of orthogonal L-polynomials, in Padé Approximants and Continued Fractions, eds. H. Waadeland and H. Wallin, Det Kongelige Norske Videnskabers Selskab, Skrifter 1, 1983, pp. 54–91.
Raf Vandebril, Marc Van Barel, and Nicola Mastronardi, Matrix computations and semiseparable matrices. Vol. 1, Johns Hopkins University Press, Baltimore, MD, 2008. Linear systems. MR 2378139