Abstract. 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.
Jarlebring et al. (Wed,) studied this question.