An Extension and Efficient Calculation of the Horner’s Rule for Matrices

We propose an efficient method for calculating “matrix polynomials” by extending the Horner’s rule for univariate polynomials. We extend the Horner’s rule by partitioning it by a given degree to reduce the number of matrix-matrix multiplications. By this extension, we show that we can calculate matrix polynomials more efficiently than by using naive Horner’s rule. An implementation of our algorithm is available on the computer algebra system Risa/Asir, and our experiments have demonstrated that, at suitable degree of partitioning, our new algorithm needs significantly shorter computing time as well as much smaller amount of memory, compared to naive Horner’s rule. Furthermore, we show that our new algorithm is effective for matrix polynomials not only over multiple-precision integers, but also over fixed-precision (IEEE standard) floating-point numbers by experiments.