Optimality of the Paterson-Stockmeyer method for evaluating matrix polynomials and rational matrix functions. (English) Zbl 1431.65062
Summary: Many state-of-the-art algorithms reduce the computation of transcendental matrix functions to the evaluation of polynomial or rational approximants at a matrix argument. This task can be accomplished efficiently by resorting to the Paterson-Stockmeyer method, an evaluation scheme originally developed for polynomials of matrices that extends quite naturally to rational functions. An important feature of this technique is that the number of matrix multiplications required to evaluate an approximant of order \(n\) grows slower than \(n\) itself, with the result that different approximants yield the same asymptotic computational cost. We analyze the number of matrix multiplications required by the Paterson-Stockmeyer method and by two widely used generalizations, one for evaluating diagonal Padé approximants of general functions and one specifically tailored to those of the exponential. In all the three cases, we identify the approximants of maximum order for any given computational cost.
MSC:
| 65F60 | Numerical computation of matrix exponential and similar matrix functions |
| 15A16 | Matrix exponential and similar functions of matrices |
Keywords:
Paterson-Stockmeyer method; polynomial evaluation; matrix polynomial; matrix rational function; matrix functionReferences:
| [1] | Al-Mohy, A. H.; Higham, N. J., A new scaling and squaring algorithm for the matrix exponential, SIAM J. Matrix Anal. Appl., 31, 970-989 (2009) · Zbl 1194.15021 |
| [2] | Al-Mohy, A. H.; Higham, N. J., Improved inverse scaling and squaring algorithms for the matrix logarithm, SIAM J. Sci. Comput., 34, C153-C169 (2012) · Zbl 1252.15027 |
| [3] | Al-Mohy, A. H.; Higham, N. J.; Relton, S. D., New algorithms for computing the matrix sine and cosine separately or simultaneously, SIAM J. Sci. Comput., 37, A456-A487 (2015) · Zbl 1315.65045 |
| [4] | Alonso, P.; Ibáñez, J.; Sastre, J.; Peinado, J.; Defez, E., Efficient and accurate algorithms for computing matrix trigonometric functions, J. Comput. Appl. Math., 309, 325-332 (2017) · Zbl 1416.65126 |
| [5] | Aprahamian, M.; Higham, N. J., Matrix inverse trigonometric and inverse hyperbolic functions: theory and algorithms, SIAM J. Matrix Anal. Appl., 37, 1453-1477 (2016) · Zbl 1388.15012 |
| [6] | Caliari, M.; Zivcovich, F., On-the-fly backward error estimate for matrix exponential approximation by Taylor algorithm, J. Comput. Appl. Math., 346, 532-548 (2019) · Zbl 1452.65082 |
| [7] | Cheng, S. H.; Higham, N. J.; Kenney, C. S.; Laub, A. J., Approximating the logarithm of a matrix to specified accuracy, SIAM J. Matrix Anal. Appl., 22, 1112-1125 (2001) · Zbl 0989.65057 |
| [8] | Defez, E.; Ibáñez, J.; Sastre, J.; Peinado, J.; Alonso, P., A new efficient and accurate spline algorithm for the matrix exponential computation, J. Comput. Appl. Math., 337, 354-365 (2018) · Zbl 1398.65091 |
| [9] | Fasi, M.; Higham, N. J., An Arbitrary Precision Scaling and Squaring Algorithm for the Matrix Exponential (2018), Manchester Institute for Mathematical Sciences, The University of Manchester: Manchester Institute for Mathematical Sciences, The University of Manchester UK, MIMS EPrint 2018.36 |
| [10] | Fasi, M.; Higham, N. J., Multiprecision algorithms for computing the matrix logarithm, SIAM J. Matrix Anal. Appl., 39, 472-491 (2018) · Zbl 1390.15073 |
| [11] | Güttel, S.; Nakatsukasa, Y., Scaled and squared subdiagonal Padé approximation for the matrix exponential, SIAM J. Matrix Anal. Appl., 37, 145-170 (2016) · Zbl 1382.65125 |
| [12] | Hargreaves, G., Topics in Matrix Computations: Stability and Efficiency of Algorithms (2005), University of Manchester: University of Manchester Manchester, England, PhD thesis |
| [13] | Higham, N. J., The scaling and squaring method for the matrix exponential revisited, SIAM J. Matrix Anal. Appl., 26, 1179-1193 (2005) · Zbl 1081.65037 |
| [14] | Higham, N. J., Functions of Matrices: Theory and Computation (2008), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1167.15001 |
| [15] | Hoffman, N.; Schwartz, O.; Toledo, S., Efficient evaluation of matrix polynomials, Lect. Notes Comput. Sci., 24-35 (2018) |
| [16] | Kressner, D.; Luce, R., Fast computation of the matrix exponential for a Toeplitz matrix, SIAM J. Matrix Anal. Appl., 39, 23-47 (2018) · Zbl 1386.65131 |
| [17] | Paterson, M. S.; Stockmeyer, L. J., On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput., 2, 60-66 (1973) · Zbl 0262.65033 |
| [18] | Sastre, J., Efficient evaluation of matrix polynomials, Linear Algebra Appl., 539, 229-250 (2018) · Zbl 1432.65029 |
| [19] | Sastre, J.; Ibáñez, J.; Alonso, P.; Peinado, J.; Defez, E., Two algorithms for computing the matrix cosine function, J. Comput. Appl. Math., 312, 66-77 (2017) · Zbl 1426.65059 |
| [20] | Sastre, J.; Ibáñez, J.; Defez, E., Boosting the computation of the matrix exponential, Appl. Math. Comput., 340, 206-220 (2019) · Zbl 1429.65093 |
| [21] | Sastre, J.; Ibáñez, J.; Defez, E.; Ruiz, P., New scaling-squaring Taylor algorithms for computing the matrix exponential, SIAM J. Matrix Anal. Appl., 37, A439-A455 (2015) · Zbl 1315.65046 |
| [22] | Van Loan, C., A note on the evaluation of matrix polynomials, IEEE Trans. Automat. Control, 24, 320-321 (1979) · Zbl 0401.65027 |
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.
