For over fifty years, the Paterson–Stockmeyer method has been considered the benchmark for efficient matrix polynomial evaluation. In our recent open access article, we provide a summary of recent advances in this area and present a constructive scheme that evaluates a degree‑20 matrix polynomial using only 5 matrix multiplications—two fewer than Paterson–Stockmeyer.
We also show how the coefficients of this scheme can be derived from the solutions of a single equation involving one coefficient, and we include the full process in our supplementary materials.
Publication Details
- Title: Beyond Paterson–Stockmeyer: Advancing Matrix Polynomial Computation
- Authors: J. Sastre, J. Ibáñez, J. M. Alonso, E. Defez
- Journal: WSEAS Transactions on Mathematics, Vol. 24, pp. 684–693, 2025
- Conference: 5th Int. Conf. on Applied Mathematics, Computational Science and Systems Engineering (AMCSE), Paris, France, April 14–16, 2025
- Open Access: https://doi.org/10.37394/23206.2025.24.68
- Supplementary Material:
- Article erratum
coeffspol_m20.m(MATLAB code implementing the scheme)coeffspol_m20.txt(full derivation and output)
Main Contributions
- Survey of recent advances in matrix polynomial evaluation.
- Constructive result: A method to compute a degree‑20 matrix polynomial with just 5 matrix multiplications, improving efficiency over Paterson–Stockmeyer (needing 7 matrix products).
- Coefficient derivation: All coefficients can be obtained by solving an equation in one unknown, documented step by step in the
.txtfile. - Generalization: We propose a framework for evaluation formulas of the type , see with available variables, and set two conjectures for future research.
Why This Matters
Reducing matrix multiplications significantly lowers computational cost, which is crucial for:
- Large-scale scientific computing
- Numerical linear algebra
- AI and machine learning models involving matrix functions
Access and Resources
- Read the full paper (Open Access): https://doi.org/10.37394/23206.2025.24.68 (See Article erratum)
- Download the code:
coeffspol_m20.m - Explore the process:
coeffspol_m20.txt
Next Steps
If you work with matrix functions or large-scale computations:
- Try the 5-multiplication scheme for degree‑20 polynomials.
- Benchmark against Paterson–Stockmeyer.
- Explore adapting the rational-coefficient approach to other degrees.
We welcome collaboration on proving the conjectures and extending these ideas to broader polynomial families.