The Polynomial Set Associated with a Fixed Number of Matrix-Matrix Multiplications
SIAM Journal on Applied Algebra and Geometry · 30.09.2026 · 10 (3) · 549-581
DOI: 10.1137/25m1779036 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Applied Algebra and Geometry, online erschienen am 22.07.2026. Verfasst von Elias Jarlebring und 1 weiteren Autor:innen. Die Arbeit nennt 35 Literaturangaben.
Abstract (Originalsprache)
We consider the problem of computing matrix polynomials [Formula: see text], where [Formula: see text] is a large dense matrix, with as few matrix-matrix multiplications as possible. More precisely, let [Formula: see text] represent the set of polynomials computable with [Formula: see text] matrix-matrix multiplications, but with an arbitrary number of matrix additions and scaling operations. We characterize this set through a tabular parameterization. By deriving equivalence transformations of the tabular representation, we establish new methods that can be used to construct elements of [Formula: see text] and determine general properties of the set. The transformations allow us to eliminate variables and prove that the dimension is bounded by [Formula: see text], which is subsequently proven to be sharp, i.e., [Formula: see text]. Consequently, we have identified a parameterization that, to the best of our knowledge, is the first minimal parameterization. We also conduct a study using computational tools from algebraic geometry to determine the largest degree [Formula: see text] such that all polynomials of that degree belong to [Formula: see text] or its closure. In many cases, the computational setup is constructive in the sense that it can also be used to determine a specific evaluation scheme for a given polynomial.
Zitieren
APA
Jarlebring, E., & Lorentzon, G. (2026). The Polynomial Set Associated with a Fixed Number of Matrix-Matrix Multiplications. SIAM Journal on Applied Algebra and Geometry, 10(3), 549-581. https://doi.org/10.1137/25m1779036
Vancouver
Jarlebring E, Lorentzon G. The Polynomial Set Associated with a Fixed Number of Matrix-Matrix Multiplications. SIAM Journal on Applied Algebra and Geometry. 2026;10(3):549-581. doi:10.1137/25m1779036
BibTeX
@article{Jarlebring2026,
author = {Jarlebring, Elias and Lorentzon, Gustaf},
title = {The Polynomial Set Associated with a Fixed Number of Matrix-Matrix Multiplications},
journal = {SIAM Journal on Applied Algebra and Geometry},
year = {2026},
volume = {10},
number = {3},
pages = {549--581},
doi = {10.1137/25m1779036}
}
EUVIMED