Beyond Paterson–Stockmeyer: Advancing Matrix Polynomial Computation

Since 1973, the Paterson–Stockmeyer method has been considered the most efficient approach for evaluating general matrix polynomials. In this paper, we challenge this long-standing belief by demonstrating that newly developed methods surpass its efficiency. We summarize the state of the art and present new results. Additionally, for decades, rational approximations have been deemed superior to polynomial approximations in terms of computational efficiency. However, we reveal that polynomial approximations can achieve a higher order of accuracy than state-of-the-art rational methods at the same computational cost. Through theoretical insights and practical examples, we illustrate the implications of these findings for advanced matrix computations, with potential applications in scientific computing, numerical analysis, and artificial intelligence.