A black-box rational Arnoldi variant for Cauchy-Stieltjes matrix functions. (English) Zbl 1276.65026
Summary: Rational Arnoldi is a powerful method for approximating functions of large sparse matrices times a vector. The selection of asymptotically optimal parameters for this method is crucial for its fast convergence. We present and investigate a novel strategy for the automated parameter selection when the function to be approximated is of Cauchy-Stieltjes (or Markov) type, such as the matrix square root or the logarithm. The performance of this approach is demonstrated by numerical examples involving symmetric and nonsymmetric matrices. These examples suggest that our black-box method performs at least as well, and typically better, as the standard rational Arnoldi method with parameters being manually optimized for a given matrix.
MSC:
| 65F60 | Numerical computation of matrix exponential and similar matrix functions |
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A16 | Matrix exponential and similar functions of matrices |
Keywords:
rational Arnoldi method; matrix square root; matrix logarithm; optimal parameters; large sparse matrices; automated parameter selection; numerical exampleSoftware:
mftoolboxReferences:
| [1] | Afanasjew, M., Eiermann, M., Ernst, O.G., Güttel, S.: Implementation of a restarted Krylov subspace method for the evaluation of matrix functions. Linear Algebra Appl. 429, 2293-2314 (2008) · Zbl 1153.65042 · doi:10.1016/j.laa.2008.06.029 |
| [2] | Allen, E.J., Baglama, J., Boyd, S.K.: Numerical approximation of the product of the square root of a matrix with a vector. Linear Algebra Appl. 310, 167-181 (2000) · Zbl 0972.65029 · doi:10.1016/S0024-3795(00)00068-9 |
| [3] | Arioli, M., Loghin, D.: Matrix square-root preconditioners for the Steklov-Poincaré operator. Technical Report RAL-TR-2008-003, Rutherford Appleton Laboratory (2008) · Zbl 1392.65042 |
| [4] | Abramowitz, M., Stegun, I.A.: Pocketbook of Mathematical Functions. Verlag Harri Deutsch, Frankfurt am Main (1984) · Zbl 0643.33002 |
| [5] | Bagby, T.: On interpolation by rational functions. Duke Math. J. 36, 95-104 (1969) · Zbl 0223.30049 · doi:10.1215/S0012-7094-69-03614-X |
| [6] | Beckermann, B., Güttel, S.: Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions. Numer. Math. 121, 205-236 (2012) · Zbl 1271.65059 · doi:10.1007/s00211-011-0434-8 |
| [7] | Beckermann, B., Güttel, S., Vandebril, R.: On the convergence of rational Ritz values. SIAM J. Matrix Anal. Appl. 31, 1740-1774 (2010) · Zbl 1213.15009 · doi:10.1137/090755412 |
| [8] | Beckermann, B., Reichel, L.: Error estimation and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47, 3849-3883 (2009) · Zbl 1204.65041 · doi:10.1137/080741744 |
| [9] | Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418-477 (2002) · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176 |
| [10] | Botchev, M.A.: Residual, restarting and Richardson iteration for the matrix exponential. Memorandum 1928, Department of Applied Mathematics, University of Twente, Enschede (2010) · Zbl 1278.65052 |
| [11] | Coroian, D.I., Dragnev, P.: Constrained Leja points and the numerical solution of the constrained energy problem. J. Comput. Appl. Math. 131, 427-444 (2001) · Zbl 0982.65077 · doi:10.1016/S0377-0427(00)00258-2 |
| [12] | Crouzeix, M.: Numerical range and functional calculus in Hilbert space. J. Funct. Anal. 244, 668-690 (2007) · Zbl 1116.47004 · doi:10.1016/j.jfa.2006.10.013 |
| [13] | Druskin, V., Greenbaum, A., Knizhnerman, L.: Using nonorthogonal Lanczos vectors in the computation of matrix functions. SIAM J. Sci. Comput. 19, 38-54 (1998) · Zbl 0912.65021 · doi:10.1137/S1064827596303661 |
| [14] | Druskin, V., Knizhnerman, L.: Spectral approach to solving three-dimensional Maxwell’s diffusion equations in the time and frequency domains. Radio Sci. 29, 937-953 (1994) · doi:10.1029/94RS00747 |
| [15] | Druskin, V., Knizhnerman, L.: Extended Krylov subspaces: approximation of the matrix square root and related functions. SIAM J. Matrix Anal. Appl. 19, 755-771 (1998) · Zbl 0912.65022 · doi:10.1137/S0895479895292400 |
| [16] | Druskin, V., Knizhnerman, L.: Gaussian spectral rules for the three-point second differences, I: a two-point positive definite problem in a semi-infinite domain. SIAM J. Numer. Anal. 37, 403-422 (1999) · Zbl 0947.65127 · doi:10.1137/S0036142997330792 |
| [17] | Druskin, V., Knizhnerman, L., Zaslavsky, M.: Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts. SIAM J. Sci. Comput. 31, 3760-3780 (2009) · Zbl 1204.65042 · doi:10.1137/080742403 |
| [18] | Druskin, V., Lieberman, C., Zaslavsky, M.: On adaptive choice of shifts in rational Krylov subspace reduction of evolutionary problems. SIAM J. Sci. Comput. 32, 2485-2496 (2010) · Zbl 1221.65255 · doi:10.1137/090774082 |
| [19] | Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Control Lett. 60, 546-560 (2011) · Zbl 1236.93035 · doi:10.1016/j.sysconle.2011.04.013 |
| [20] | Eiermann, M., Ernst, O.G.: A restarted Krylov subspace method for the evaluation of matrix functions. SIAM J. Numer. Anal. 44, 2481-2504 (2006) · Zbl 1129.65019 · doi:10.1137/050633846 |
| [21] | Eiermann, M., Ernst, O.G., Güttel, S.: Deflated restarting for matrix functions. SIAM J. Matrix Anal. Appl. 32, 621-641 (2011) · Zbl 1264.65070 · doi:10.1137/090774665 |
| [22] | van den Eshof, J., Frommer, A., Lippert, T., Schilling, K., van der Vorst, H.A.: Numerical methods for the QCD overlap operator, I: sign-function and error bounds. Comput. Phys. Commun. 146, 203-224 (2002) · Zbl 1008.81508 · doi:10.1016/S0010-4655(02)00455-1 |
| [23] | Gonchar, A.A.: Zolotarev problems connected with rational functions. Math. USSR Sb. 7, 623-635 (1969) · Zbl 0203.07302 · doi:10.1070/SM1969v007n04ABEH001107 |
| [24] | Güttel, S.: Rational Krylov methods for operator functions. PhD thesis, TU Bergakademie Freiberg (2010) |
| [25] | Güttel, S.: Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection. In: GAMM Mitteilungen (2013, accepted for publication) · Zbl 1292.65043 |
| [26] | Güttel, S., Knizhnerman, L.: Automated parameter selection for Markov functions. Proc. Appl. Math. Mech. 11, 15-18 (2011) · doi:10.1002/pamm.201110005 |
| [27] | Henrici, P.: Applied and Computational Complex Analysis, vol. I. Wiley, New York (1988) · Zbl 0635.30001 |
| [28] | Higham, N.J.: Functions of Matrices. Theory and Computation. SIAM, Philadelphia (2008) · Zbl 1167.15001 · doi:10.1137/1.9780898717778 |
| [29] | Hochbruck, M., Lubich, C., Selhofer, H.: Exponential integrators for large systems of differential equations. SIAM J. Sci. Comput. 19, 1552-1574 (1998) · Zbl 0912.65058 · doi:10.1137/S1064827595295337 |
| [30] | Knizhnerman, L.: Adaptation of the Lanczos and Arnoldi methods to the spectrum, or why the two Krylov subspace methods are powerful. Chebyshev Dig. 3(2), 141-164 (2002) · Zbl 1106.65030 |
| [31] | Knizhnerman, L., Simoncini, V.: A new investigation of the extended Krylov subspace method for matrix function evaluations. Numer. Linear Algebra Appl. 17, 615-638 (2010) · Zbl 1240.65154 |
| [32] | Lehoucq, R.B., Meerbergen, K.: Using generalized Cayley transformations within an inexact rational Krylov sequence method. SIAM J. Matrix Anal. Appl. 20, 131-148 (1998) · Zbl 0931.65035 · doi:10.1137/S0895479896311220 |
| [33] | Levin, A.L., Saff, E.B.: Optimal ray sequences of rational functions connected with the Zolotarev problem. Constr. Approx. 10, 235-273 (1994) · Zbl 0804.41014 · doi:10.1007/BF01263066 |
| [34] | Nehari, Z.: Conformal Mapping. Dover, New York (1975) · Zbl 0048.31503 |
| [35] | Ruhe, A.: Rational Krylov sequence methods for eigenvalue computation. Linear Algebra Appl. 58, 391-405 (1984) · Zbl 0554.65025 · doi:10.1016/0024-3795(84)90221-0 |
| [36] | Ruhe, A.: Rational Krylov algorithms for nonsymmetric eigenvalue problems. IMA Vol. Math. Appl. 60, 149-164 (1994) · Zbl 0803.65045 · doi:10.1007/978-1-4613-9353-5_10 |
| [37] | Saad, Y.: Analysis of some Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 29, 209-228 (1992) · Zbl 0749.65030 · doi:10.1137/0729014 |
| [38] | Trefethen, L. N.; Griffiths, D. F. (ed.); Watson, G. A. (ed.), Pseudospectra of matrices, 234-266 (1992), Harlow · Zbl 0798.15005 |
| [39] | Walsh, J.L.: Interpolation and Approximation by Rational Functions in the Complex Domain. AMS, Providence (1969) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
