EUVIMEDEUVIMED entdecken
Crossref

The Polynomial Set Associated with a Fixed Number of Matrix-Matrix Multiplications

Elias Jarlebring, Gustaf Lorentzon

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →