摘要 Abstract
考虑计算形如$p(X)$的矩阵多项式问题,其中$X$为大矩阵,并且尽量减少矩阵-矩阵乘法的数量。具体而言,令$\Pi_{2^{m}}^*$表示可以通过$m$次矩阵-矩阵乘法(但允许任意数量的矩阵加法和缩放操作)计算的多项式集合。我们通过表格参数化来刻画该集合。通过对表格表示进行等价变换,我们建立了新的方法来构造$\Pi_{2^{m}}^*$中的元素并确定该集合的一般性质。这些变换允许我们消去变量,并证明其维数被$m^2$所界。数值模拟表明该界可能是尖锐的。因此,我们找到了一种参数化方法,据我们所知,这是首个最小参数化方法。此外,我们利用代数几何中的计算工具研究了使得所有该次数的多项式属于$\Pi_{2^{m}}^*$或其闭包的最大次数$d$。在许多情况下,计算设置是构造性的,即也可以用于确定给定多项式的特定评估方案。
We consider the problem of computing matrix polynomials $p(X)$, where $X$ is a large 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, which, to our knowledge, is the first minimal parameterization. Furthermore, we 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.