A MATLAB Tool for the Stable Generation of Matrix Polynomial Evaluation Schemes with Two-Product Savings - Group of High Performance Scientific Computing (HiPerSC)

The efficient evaluation of high-degree matrix polynomials is central to the numerical approximation of matrix functions. For decades, the Paterson–Stockmeyer (PS) method has provided the standard benchmark for reducing the number of matrix–matrix multiplications required by these computations. Recent theoretical advances, however, have shown that further savings are possible through evaluation schemes that eliminate two matrix products (2M) relative to the classical approach. Despite this progress, numerically stable implementations of such schemes have remained largely restricted to a few specific polynomial degrees and applications.

Javier Ibáñez, Jorge Sastre, José M. Alonso, and Emilio Defez address this limitation by developing a software-assisted procedure that extends the 2M reduction to polynomials of degrees $m \in {18, 21, 24, 26, 27, 28}$ and to every degree $m \geq 30$ , provided that the leading coefficient is nonzero. The main numerical challenge lies in determining the coefficients that define the evaluation schemes. These coefficients are obtained by solving systems of nonlinear equations, whose solutions may differ substantially in their numerical stability. The authors therefore introduce an automated verification procedure to identify and validate coefficient sets suitable for floating-point computations.

The central contribution is a MATLAB implementation that combines symbolic computation with variable-precision arithmetic to construct the reduced nonlinear systems, identify suitable solutions, assess their numerical stability, and estimate the precision required for reliable evaluation. Beyond the 2M cases, the framework also identifies polynomial degrees for which a one-product reduction is attainable, thereby extending the range of available evaluation strategies.

Numerical experiments involving several matrix functions show that the resulting schemes maintain accuracy comparable to that of the classical Paterson–Stockmeyer method and, in some cases, improve upon it, while consistently achieving the predicted reduction of two matrix–matrix multiplications. These results demonstrate that the proposed software provides a practical route from theoretical evaluation formulas to numerically reliable implementations, making the computational savings accessible to a substantially broader class of matrix polynomials.

Publication details

Title: A MATLAB Tool for the Stable Generation of Matrix Polynomial Evaluation Schemes with Two-Product Savings
Authors: Javier Ibáñez, Jorge Sastre, José M. Alonso, Emilio Defez
Preprint: arXiv:2607.28286 (v4, September 23 of 2026)
Enlace: https://arxiv.org/abs/2607.28286
Preprint (ResearchGate): https://www.researchgate.net/publication/411032433

Main Contributions

Software procedure extending the two-matrix-product reduction to a broad range of polynomial degrees.
Automated verification routine for selecting numerically stable coefficient sets.
MATLAB implementation using variable-precision arithmetic and numerical validation on matrix functions.

Why This Matters

The reduction of two matrix–matrix multiplications represents both a theoretical and a practical improvement in the computational cost of evaluating high-degree polynomials. The developed tool makes this reduction reliably accessible across a broad range of polynomial degrees, potentially benefiting matrix function algorithms that rely on polynomial approximations.