Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximation of the matrix exponential for matrices with a skinny field of values

  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

The backward error analysis is a great tool which allows selecting in an effective way the scaling parameter s and the polynomial degree of approximation m when the action of the matrix exponential \(\exp (A)v\) has to be approximated by \(\left( p_m(s^{-1}A)\right) ^sv=\exp (A+\varDelta A)v\). We propose here a rigorous bound for the relative backward error \(\left\Vert \varDelta A\right\Vert _{2}/\left\Vert A\right\Vert _{2}\), which is of particular interest for matrices whose field of values is skinny, such as the discretization of the advection–diffusion or the Schrödinger operators. The numerical results confirm the superiority of the new approach with respect to methods based on the classical power series expansion of the backward error for the matrices of our interest, both in terms of computational cost and achieved accuracy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Al-Mohy, A.H., Higham, N.J.: A new scaling and squaring algorithm for the matrix exponential. SIAM J. Matrix Anal. Appl. 31(3), 970–989 (2009)

    Article  MathSciNet  Google Scholar 

  2. Al-Mohy, A.H., Higham, N.J.: Computing the action of the matrix exponential with an application to exponential integrators. SIAM J. Sci. Comput. 33(2), 488–511 (2011)

    Article  MathSciNet  Google Scholar 

  3. Bos, L.P., Caliari, M.: Application of modified Leja sequences to polynomial interpolation. Dolomites Res. Notes Approx. 8, 66–74 (2015)

    MathSciNet  MATH  Google Scholar 

  4. Caliari, M.: Accurate evaluation of divided differences for polynomial interpolation of exponential propagators. Computing 80(2), 189–201 (2007)

    Article  MathSciNet  Google Scholar 

  5. Caliari, M., Kandolf, P., Ostermann, A., Rainer, S.: The Leja method revisited: backward error analysis for the matrix exponential. SIAM J. Sci. Comput. 38(3), A1639–A1661 (2016)

    Article  MathSciNet  Google Scholar 

  6. Caliari, M., Kandolf, P., Zivcovich, F.: Backward error analysis of polynomial approximations for computing the action of the matrix exponential. BIT Numer. Math. 58(4), 907–935 (2018)

    Article  MathSciNet  Google Scholar 

  7. Crouzeix, M., Palencia, C.: The numerical range is a \((1+\sqrt{2})\)-spectral set. SIAM J. Matrix Anal. Appl. 38(2), 649–655 (2017)

    Article  MathSciNet  Google Scholar 

  8. Frommer, A., Güttel, S., Schweitzer, M.: Efficient and stable Arnoldi restarts for matrix functions based on quadrature. SIAM J. Matrix Anal. Appl. 35(2), 661–683 (2014)

    Article  MathSciNet  Google Scholar 

  9. Gaudrealt, S., Rainwater, G., Tokman, M.: KIOPS: A fast adaptive Krylov subspace solver for exponential integrators. J. Comput. Phys. 372(1), 236–255 (2018)

    Article  MathSciNet  Google Scholar 

  10. Güttel, S.: Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection. GAMM-Mitt. 36(1), 8–31 (2013)

    Article  MathSciNet  Google Scholar 

  11. Higham, N.J.: Estimating the matrix \(p\)-norm. Numer. Math. 62, 539–555 (1992)

    Article  MathSciNet  Google Scholar 

  12. Higham, N.J.: The scaling and squaring method for the matrix exponential revisited. SIAM J. Matrix Anal. Appl. 26(4), 1179–1193 (2005)

    Article  MathSciNet  Google Scholar 

  13. Higham, N.J.: Functions of Matrices. SIAM, Philadelphia (2008)

    Book  Google Scholar 

  14. Higham, N.J., Tisseur, F.: A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra. SIAM J. Matrix Anal. Appl. 21(4), 1185–1201 (2000)

    Article  MathSciNet  Google Scholar 

  15. Hochbruck, M., Ostermann, A.: Exponential integrators. Acta Numer. 19, 209–286 (2010)

    Article  MathSciNet  Google Scholar 

  16. Johnson, C.R.: Numerical determination of the field of values of a general complex matrix. SIAM J. Numer. Anal. 15(3), 595–602 (1978)

    Article  MathSciNet  Google Scholar 

  17. McCurdy, A., Ng, K.C., Parlett, B.N.: Accurate computation of divided differences of the exponential function. Math. Comput. 43(168), 501–528 (1984)

    Article  MathSciNet  Google Scholar 

  18. Moler, C.B., Van Loan, C.F.: Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Rev. 45(1), 3–49 (2003)

    Article  MathSciNet  Google Scholar 

  19. Moret, I., Novati, P.: RD-rational approximation of the matrix exponential operator. BIT Numer. Math. 44, 595–615 (2004)

    Article  Google Scholar 

  20. Niesen, J., Wright, W.M.: Algorithm 919: A Krylov subspace algorithm for evaluating the \(\phi \)-functions appearing in exponential integrators. ACM Trans. Math. Softw. 38(3), 1–19 (2012)

    Article  MathSciNet  Google Scholar 

  21. Schmelzer, T., Trefethen, L.N.: Evaluating matrix functions for exponential integrators via Carathéodory–Fejér approximation and contour integrals. Electron. Trans. Numer. Anal. 29, 1–18 (2007)

    MathSciNet  MATH  Google Scholar 

  22. Tal-Ezer, H.: High degree polynomial interpolation in Newton form. SIAM J. Sci. Stat. Comput. 12(3), 648–667 (1991)

    Article  MathSciNet  Google Scholar 

  23. van den Eshof, J., Hochbruck, M.: Preconditioning Lanczos approximations to the matrix exponential. SIAM J. Sci. Comput. 27(4), 1438–1457 (2006)

    Article  MathSciNet  Google Scholar 

  24. Zivcovich, F.: Fast and accurate computation of divided differences for analytic functions, with an application to the exponential function. Dolomites Res. Notes Approx. 12, 28–42 (2019)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Verona, Verona, Italy

    Marco Caliari & Franco Zivcovich

  2. University of Trento, Trento, Italy

    Fabio Cassini

Authors
  1. Marco Caliari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fabio Cassini
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Franco Zivcovich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marco Caliari.

Additional information

Communicated by Christian Lubich.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Caliari, M., Cassini, F. & Zivcovich, F. Approximation of the matrix exponential for matrices with a skinny field of values. Bit Numer Math 60, 1113–1131 (2020). https://doi.org/10.1007/s10543-020-00809-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10543-020-00809-0

Keywords

Mathematics Subject Classification

Search

Navigation