标题： 与固定数量的矩阵-矩阵乘法相关的多项式集 显示英文标题

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

摘要： 我们研究了计算矩阵多项式$p(X)$的问题，其中$X$是一个大型稠密矩阵，并且尽量减少矩阵-矩阵乘法的次数。 更具体地说，设$\Pi_{2^{m}}^*$表示可以用$m$次矩阵-矩阵乘法计算的多项式集合，但可以有任意数量的矩阵加法和缩放操作。 我们通过表格参数化来刻画这个集合。 通过对表格表示进行等价变换，我们建立了新的方法，可用于构造$\Pi_{2^{m}}^*$中的元素并确定该集合的一般性质。 这些变换允许我们消去变量并证明其维数由$m^2$界定。 数值模拟表明这是一个尖锐的界。 因此，我们找到了一种参数化方法，据我们所知，这是第一个最小参数化方法。 我们还利用代数几何中的计算工具开展了一项研究，以确定最大的次数 $d$，使得所有该次数的多项式都属于 $\Pi_{2^{m}}^*$ 或其闭包。 在许多情况下，计算设置具有构造性，这意味着它还可以用于为给定的多项式确定特定的评估方案。 显示英文摘要

摘要： 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 $\Pi_{2^{m}}^*$ 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 $\Pi_{2^{m}}^*$ and determine general properties of the set. The transformations allow us to eliminate variables and prove that the dimension is bounded by $m^2$. Numerical simulations suggest that this is a sharp bound. 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 $\Pi_{2^{m}}^*$, 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.