nach oben

BIT Numerical Mathematics

Erschienen in:

01.09.2013

A black-box rational Arnoldi variant for Cauchy–Stieltjes matrix functions

verfasst von: Stefan Güttel, Leonid Knizhnerman

Erschienen in: BIT Numerical Mathematics | Ausgabe 3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Exponential almost Runge-Kutta methods for semilinear problems

Nächster Artikel Stochastic Runge-Kutta methods with deterministic high order for ordinary differential equations

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The definition of K(κ) is not consistent in the literature. We stick to the definition used in [34, Chap. VI]. In Matlab one would type ellipke(kappa^2) to obtain the value K(κ).

As available from http://ta.twi.tudelft.nl/nw/users/gijzen/IDR.html.

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) MathSciNetMATHCrossRef

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) MathSciNetMATHCrossRef

Arioli, M., Loghin, D.: Matrix square-root preconditioners for the Steklov–Poincaré operator. Technical Report RAL-TR-2008-003, Rutherford Appleton Laboratory (2008)

Abramowitz, M., Stegun, I.A.: Pocketbook of Mathematical Functions. Verlag Harri Deutsch, Frankfurt am Main (1984) MATH

Bagby, T.: On interpolation by rational functions. Duke Math. J. 36, 95–104 (1969) MathSciNetMATHCrossRef

Beckermann, B., Güttel, S.: Superlinear convergence of the rational Arnoldi method for the approximation of matrix functions. Numer. Math. 121, 205–236 (2012) MathSciNetMATHCrossRef

Beckermann, B., Güttel, S., Vandebril, R.: On the convergence of rational Ritz values. SIAM J. Matrix Anal. Appl. 31, 1740–1774 (2010) MATHCrossRef

Beckermann, B., Reichel, L.: Error estimation and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47, 3849–3883 (2009) MathSciNetMATHCrossRef

Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418–477 (2002) MathSciNetMATHCrossRef

10.

Botchev, M.A.: Residual, restarting and Richardson iteration for the matrix exponential. Memorandum 1928, Department of Applied Mathematics, University of Twente, Enschede (2010)

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) MathSciNetMATHCrossRef

12.

Crouzeix, M.: Numerical range and functional calculus in Hilbert space. J. Funct. Anal. 244, 668–690 (2007) MathSciNetMATHCrossRef

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) MathSciNetMATHCrossRef

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) CrossRef

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) MathSciNetMATHCrossRef

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) MathSciNetMATHCrossRef

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) MathSciNetMATHCrossRef

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) MathSciNetMATHCrossRef

19.

Druskin, V., Simoncini, V.: Adaptive rational Krylov subspaces for large-scale dynamical systems. Syst. Control Lett. 60, 546–560 (2011) MathSciNetMATHCrossRef

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) MathSciNetMATHCrossRef

21.

Eiermann, M., Ernst, O.G., Güttel, S.: Deflated restarting for matrix functions. SIAM J. Matrix Anal. Appl. 32, 621–641 (2011) MathSciNetMATHCrossRef

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) MATHCrossRef

23.

Gonchar, A.A.: Zolotarev problems connected with rational functions. Math. USSR Sb. 7, 623–635 (1969) CrossRef

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)

26.

Güttel, S., Knizhnerman, L.: Automated parameter selection for Markov functions. Proc. Appl. Math. Mech. 11, 15–18 (2011) CrossRef

27.

Henrici, P.: Applied and Computational Complex Analysis, vol. I. Wiley, New York (1988)

28.

Higham, N.J.: Functions of Matrices. Theory and Computation. SIAM, Philadelphia (2008) MATHCrossRef

29.

Hochbruck, M., Lubich, C., Selhofer, H.: Exponential integrators for large systems of differential equations. SIAM J. Sci. Comput. 19, 1552–1574 (1998) MathSciNetMATHCrossRef

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) MathSciNetMATH

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) MathSciNetMATH

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) MathSciNetMATHCrossRef

33.

Levin, A.L., Saff, E.B.: Optimal ray sequences of rational functions connected with the Zolotarev problem. Constr. Approx. 10, 235–273 (1994) MathSciNetMATHCrossRef

34.

Nehari, Z.: Conformal Mapping. Dover, New York (1975)

35.

Ruhe, A.: Rational Krylov sequence methods for eigenvalue computation. Linear Algebra Appl. 58, 391–405 (1984) MathSciNetMATHCrossRef

36.

Ruhe, A.: Rational Krylov algorithms for nonsymmetric eigenvalue problems. IMA Vol. Math. Appl. 60, 149–164 (1994) MathSciNetCrossRef

37.

Saad, Y.: Analysis of some Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 29, 209–228 (1992) MathSciNetMATHCrossRef

38.

Trefethen, L.N.: Pseudospectra of matrices. In: Griffiths, D.F., Watson, G.A. (eds.) Numerical Analysis 1991, pp. 234–266. Longman Scientific and Technical, Harlow (1992)

39.

Walsh, J.L.: Interpolation and Approximation by Rational Functions in the Complex Domain. AMS, Providence (1969)

Titel: A black-box rational Arnoldi variant for Cauchy–Stieltjes matrix functions
verfasst von: Stefan Güttel
Leonid Knizhnerman
Publikationsdatum: 01.09.2013
Verlag: Springer Netherlands
Erschienen in: BIT Numerical Mathematics / Ausgabe 3/2013
Print ISSN: 0006-3835
Elektronische ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-013-0420-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 3/2013

Nodal splines on compact intervals

Stochastic Runge-Kutta methods with deterministic high order for ordinary differential equations

Approximation of Fejér partial sums by interpolating functions

A posteriori error analysis for a continuous space-time finite element method for a hyperbolic integro-differential equation

Exponential almost Runge-Kutta methods for semilinear problems

Discrete stability of perfectly matched layers for anisotropic wave equations in first and second order formulation

Premium Partner