A Systematic Framework for Stable and Cost-Efficient Matrix Polynomial Evaluation
This work addresses stability issues in computational linear algebra for applications like matrix exponentials, but it is incremental as it builds on existing optimization methods.
The paper tackles the problem of numerical instability in optimized matrix polynomial evaluation methods that save one matrix product, by developing a systematic framework to identify stable coefficient sets for degrees 8, 10, 12, and above, achieving the cost reduction while maintaining accuracy comparable to the Paterson–Stockmeyer method.
A method for evaluating matrix polynomials have recently been developed that require one fewer matrix product ($1M$) than the Paterson--Stockmeyer (PS) method. Since the computational cost for large-scale matrices is asymptotically determined by the number of matrix products, this reduction directly affects the total execution time. However, the coefficients in these optimized formulas emerge as solutions to systems of nonlinear polynomial equations, resulting in multiple potential solution sets. An inappropriate selection of these coefficients can lead to numerical instability in floating-point arithmetic. This paper presents a systematic framework and a MATLAB implementation, MatrixPolEval1, used to obtain and validate stable coefficient sets for matrix polynomials of degrees $m \in \{8, 10, 12\}$ and above. The framework introduces structural variants to maintain stability even when the original configuration fails to yield a robust solution. The provided tool identifies stable coefficient sets using variable precision arithmetic (VPA) and provides a reliability indicator for expected accuracy. Numerical experiments on polynomials arising in applications, including the matrix exponential and geometric series, show that the framework achieves the $1M$ saving while maintaining numerical accuracy comparable to the PS method.