Backward error analysis of polynomial approximations for computing the action of the matrix exponential. (English) Zbl 06989583
Summary: We describe how to perform the backward error analysis for the approximation of \(\exp (A)v\) by \(p(s^{-1}A)^sv\), for any given polynomial \(p(x)\). The result of this analysis is an optimal choice of the scaling parameter \(s\) which assures a bound on the backward error, i.e. the equivalence of the approximation with the exponential of a slightly perturbed matrix. Thanks to the SageMath package expbea we have developed, one can optimize the performance of the given polynomial approximation. On the other hand, we employ the package for the analysis of polynomials interpolating the exponential function at so called Leja-Hermite points. The resulting method for the action of the matrix exponential can be considered an extension of both Taylor series approximation and Leja point interpolation. We illustrate the behavior of the new approximation with several numerical examples.
MSC:
| 65D05 | Numerical interpolation |
| 65F30 | Other matrix algorithms (MSC2010) |
| 65F60 | Numerical computation of matrix exponential and similar matrix functions |
Keywords:
backward error analysis; action of matrix exponential; Leja-Hermite interpolation; Taylor seriesReferences:
| [1] | Al-Mohy, AH; Higham, NJ, A new scaling and squaring algorithm for the matrix exponential, SIAM J. Matrix Anal. Appl., 31, 970-989, (2009) · Zbl 1194.15021 · doi:10.1137/09074721X |
| [2] | Al-Mohy, AH; Higham, NJ, Computing the action of the matrix exponential with an application to exponential integrators, SIAM J. Sci. Comput., 33, 488-511, (2011) · Zbl 1234.65028 · doi:10.1137/100788860 |
| [3] | Bergamaschi, L.; Caliari, M.; Vianello, M., Efficient approximation of the exponential operator for discrete 2D advection-diffusion problems, Numer. Linear Algebra Appl., 10, 271-289, (2003) · Zbl 1071.65048 · doi:10.1002/nla.288 |
| [4] | Berrut, JP; Trefethen, N., Barycentric Lagrange Interpolation, SIAM Rev., 46, 501-517, (2004) · Zbl 1061.65006 · doi:10.1137/S0036144502417715 |
| [5] | Bos, LP; Caliari, M., Application of modified Leja sequences to polynomial interpolation, Dolomites Res. Notes Approx., 8, 66-74, (2015) · Zbl 1370.41002 · doi:10.1186/s13104-015-1021-3 |
| [6] | Caliari, M., Accurate evaluation of divided differences for polynomial interpolation of exponential propagators, Computing, 80, 189-201, (2007) · Zbl 1120.65009 · doi:10.1007/s00607-007-0227-1 |
| [7] | Caliari, M.; Kandolf, P.; Ostermann, A.; Rainer, S., The Leja method revisited: backward error analysis for the matrix exponential, SIAM J. Sci. Comput., 38, a1639-a1661, (2016) · Zbl 1339.65061 · doi:10.1137/15M1027620 |
| [8] | Caliari, M.; Ostermann, A.; Rainer, S., Meshfree exponential integrators, SIAM J. Sci. Comput., 35, a431-a452, (2013) · Zbl 1264.65164 · doi:10.1137/100818236 |
| [9] | Caliari, M.; Vianello, M.; Bergamaschi, L., Interpolating discrete advection-diffusion propagators at Leja sequences, J. Comput. Appl. Math., 172, 79-99, (2004) · Zbl 1055.65105 · doi:10.1016/j.cam.2003.11.015 |
| [10] | Deadman, E., Estimating the condition number of \(f(A)b\), Numer. Algorithms, 70, 287-308, (2015) · Zbl 1326.65058 · doi:10.1007/s11075-014-9947-4 |
| [11] | Druskin, VL; Knizhnerman, LA, Two polynomial methods of calculating functions of symmetric matrices, USSR Comput. Math. Math. Phys., 29, 112-121, (1989) · Zbl 0719.65035 · doi:10.1016/S0041-5553(89)80020-5 |
| [12] | Fischer, TM, On the algorithm by Al-Mohy and Higham for computing the action of the matrix exponential: a posteriori roundoff error estimation, Linear Algebra Appl., 531, 141-168, (2017) · Zbl 1372.65137 · doi:10.1016/j.laa.2017.05.042 |
| [13] | Higham, N.J.: Functions of Matrices. SIAM, Philadelphia (2008) · Zbl 1167.15001 · doi:10.1137/1.9780898717778 |
| [14] | Higham, NJ; Relton, SD, Higher order Fréchet derivatives of matrix functions and the level-2 condition number SIAM, J. Matrix Anal. Appl., 35, 1019-1037, (2014) · Zbl 1308.65066 · doi:10.1137/130945259 |
| [15] | Higham, NJ; Tisseur, F., A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra, SIAM J. Matrix Anal. Appl., 21, 1185-1201, (2000) · Zbl 0959.65061 · doi:10.1137/S0895479899356080 |
| [16] | Hochbruck, M.; Ostermann, A., Exponential integrators, Acta Numer., 19, 209-286, (2010) · Zbl 1242.65109 · doi:10.1017/S0962492910000048 |
| [17] | Kalantari, B., Generalization of Taylor’s theorem and Newton’s method via a new family of determinantal interpolation formulas and its applications, J. Comput. Appl. Math., 126, 287-318, (2000) · Zbl 0971.65040 · doi:10.1016/S0377-0427(99)00360-X |
| [18] | Luan, VT; Ostermann, A., Parallel exponential Rosenbrock methods, Comput. Math. Appl., 71, 1137-1150, (2016) · Zbl 1443.65093 · doi:10.1016/j.camwa.2016.01.020 |
| [19] | Martínez, A.; Bergamaschi, L.; Caliari, M.; Vianello, M., A massively parallel exponential integrator for advection-diffusion models, J. Comput. Appl. Math., 231, 82-91, (2009) · Zbl 1167.65443 · doi:10.1016/j.cam.2009.01.024 |
| [20] | McCurdy, A.: Accurate computation of divided differences. Technical report, University of California—ERL (1980) |
| [21] | McCurdy, A.; Ng, KC; Parlett, BN, Accurate computation of divided differences of the exponential function, Math. Comput., 43, 501-528, (1984) · Zbl 0561.65009 · doi:10.1090/S0025-5718-1984-0758198-0 |
| [22] | Moret, I.; Novati, P., An interpolatory approximation of the matrix exponential based on Faber polynomials, J. Comput. Appl. Math., 131, 361-380, (2001) · Zbl 0983.65057 · doi:10.1016/S0377-0427(00)00261-2 |
| [23] | Novati, P., A polynomial method based on Fejèr points for the computation of functions of unsymmetric matrices, Appl. Numer. Math., 44, 201-224, (2003) · Zbl 1016.65023 · doi:10.1016/S0168-9274(02)00139-3 |
| [24] | Opitz, VG, Steigungsmatrizen, Z. Angew. Math. Mech., 44, t52-t54, (1964) · Zbl 0196.48801 |
| [25] | Reichel, L., Newton interpolation at Leja points, BIT, 30, 332-346, (1990) · Zbl 0702.65012 · doi:10.1007/BF02017352 |
| [26] | Schaefer, MJ, A polynomial based iterative method for linear parabolic equations, J. Comput. Appl. Math., 29, 35-50, (1990) · Zbl 0686.65083 · doi:10.1016/0377-0427(90)90193-4 |
| [27] | Stetekluh, J.: http://stetekluh.com/NewtonPoly.html. Accessed 4 Oct 2017 |
| [28] | Tal-Ezer, H., High degree polynomial interpolation in Newton form, SIAM J. Sci. Stat. Comput., 12, 648-667, (1991) · Zbl 0728.65009 · doi:10.1137/0912034 |
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.
