2025/04/02 by Jarlebring, Elias, Lorentzon, Gustaf · 1 citation
#14M99 #65F60 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2504.01500
We consider the problem of computing matrix polynomials p(X), where X is a large dense matrix, with as few matrix-matrix multiplications as possible. More precisely, let Π2m^* represent the set of polynomials computable with m 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 Π2m^* and determine general properties of the set. The transformations allow us to eliminate variables and prove that the dimension is bounded by m2, which is subsequently proven to be sharp, i.e., dim(Π2m^*)=m2. 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 d such that all polynomials of that degree belong to Π2m^*, 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.