Efficient evaluation of matrix polynomials.

*(English)*Zbl 1432.65029Summary: This paper presents a new family of methods for evaluating matrix polynomials more efficiently than the state-of-the-art Paterson-Stockmeyer method. Examples of the application of the methods to the Taylor polynomial approximation of matrix functions like the matrix exponential and matrix cosine are given. Their efficiency is compared with that of the best existing evaluation schemes for general polynomial and rational approximations, and also with a recent method based on mixed rational and polynomial approximants.

For many years, the Paterson-Stockmeyer method has been considered the most efficient general method for the evaluation of matrix polynomials. In this paper we show that this statement is no longer true. Moreover, for many years rational approximations have been considered more efficient than polynomial approximations, although recently it has been shown that often this is not the case in the computation of the matrix exponential and matrix cosine. In this paper we show that in fact polynomial approximations provide a higher order of approximation than the state-of-the-art computational methods for rational approximations for the same cost in terms of matrix products.

For many years, the Paterson-Stockmeyer method has been considered the most efficient general method for the evaluation of matrix polynomials. In this paper we show that this statement is no longer true. Moreover, for many years rational approximations have been considered more efficient than polynomial approximations, although recently it has been shown that often this is not the case in the computation of the matrix exponential and matrix cosine. In this paper we show that in fact polynomial approximations provide a higher order of approximation than the state-of-the-art computational methods for rational approximations for the same cost in terms of matrix products.

##### MSC:

65D99 | Numerical approximation and computational geometry (primarily algorithms) |

15A99 | Basic linear algebra |

65Y05 | Parallel numerical computation |

##### Keywords:

matrix; polynomial; rational; mixed rational and polynomial; approximation; computation; matrix function
Full Text:
DOI

##### References:

[1] | Paterson, M. S.; Stockmeyer, L. J., On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput., 2, 1, 60-66, (1973) · Zbl 0262.65033 |

[2] | Higham, N. J., Functions of matrices: theory and computation, (2008), Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1167.15001 |

[3] | Golub, G. H.; Loan, C. V., Matrix computations, Johns Hopkins Stud. Math. Sci., (1996), The Johns Hopkins University Press |

[4] | Moler, C. B.; Loan, C. V., Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45, 3-49, (2003) · Zbl 1030.65029 |

[5] | 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) · Zbl 1194.15021 |

[6] | Ruiz, P.; Sastre, J.; Ibáñez, J.; Defez, E., High performance computing of the matrix exponential, J. Comput. Appl. Math., 291, 370-379, (2016) · Zbl 1329.65092 |

[7] | Al-Mohy, A. H.; Higham, N. J.; Relton, S., New algorithms for computing the matrix sine and cosine separately or simultaneously, SIAM J. Sci. Comput., 37, 1, A456-A487, (2015) · Zbl 1315.65045 |

[8] | Sastre, J.; Ibáñez, J.; Alonso, P.; Peinado, J.; Defez, E., Two algorithms for computing the matrix cosine function, Appl. Math. Comput., 312, 66-77, (2017) · Zbl 1426.65059 |

[9] | Sastre, J., Efficient mixed rational and polynomial approximation of matrix functions, Appl. Math. Comput., 218, 24, 11938-11946, (2012) · Zbl 1283.65047 |

[10] | Blackford, S.; Dongarra, J., Installation guide for LAPACK, (1999), Department of Computer Science University of Tennessee, LAPACK Working Note 41 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.