标题： 有限域上的规范乘积分解的新结果 显示英文标题

标题： New results in canonical polyadic decomposition over finite fields

摘要： 标准分解（CPD）是快速矩阵乘法的核心，这是一个在计算机科学中多个看似不相关的问题上具有广泛影响的计算问题。 最近在该领域取得的进展通常使用随机启发式搜索来寻找新的CPD，通常是在有限域上进行的。 然而，如果这些技术无法找到足够低秩的CPD，它们就无法证明不存在这样的CPD。 因此，这些方法无法解决某些长期存在的问题，例如对应于$3\times 3$矩阵乘法的张量的秩是否小于23。 为了在这些问题上取得进展，我们开发了一种新算法，该算法保持精确性，即它们可以肯定地验证给定的张量是否具有指定的秩。 与暴力搜索相比，在有限域$\mathbb{F}$上搜索形状为$n_0\times\dots\times n_{D-1}$的张量的秩为$R$的CPD时，其中$n_0\ge \dots\ge n_{D-1}$，我们的算法节省了大约$|\mathbb{F}|^{R(n_0-1)+n_0(\sum_{d\ge 1} n_d)}$的乘法因子。 此外，我们的算法运行时间是多项式的。 我们还发现了一种新的算法来搜索边界CPD，这是一种在快速矩阵乘法中同样重要的CPD变体。 最后，我们研究了最大秩问题，并给出了新的上下界，适用于张量形状的族和特定形状。 尽管我们的CPD搜索算法仍然太慢，无法解决$3\times 3$矩阵乘法的秩，但我们能够通过添加不影响精确性或增加渐近运行时间的额外搜索剪枝来利用它们。 显示英文摘要

摘要： Canonical polyadic decomposition (CPD) is at the core of fast matrix multiplication, a computational problem with widespread implications across several seemingly unrelated problems in computer science. Much recent progress in this field has used randomized heuristic search to find new CPDs, often over a finite field. However, if these techniques fail to find a CPD with low enough rank, they cannot prove that no such CPD exists. Consequently, these methods fail to resolve certain long-standing questions, such as whether the tensor corresponding to $3\times 3$ matrix multiplication has rank less than 23. To make progress on these problems, we develop a novel algorithm that preserves exactness, i.e. they can provably verify whether or not a given tensor has a specified rank. Compared to brute force, when searching for a rank-$R$ CPD of a $n_0\times\dots\times n_{D-1}$-shaped tensor over a finite field $\mathbb{F}$, where $n_0\ge \dots\ge n_{D-1}$, our algorithm saves a multiplicative factor of roughly $|\mathbb{F}|^{R(n_0-1)+n_0(\sum_{d\ge 1} n_d)}$. Additionally, our algorithm runs in polynomial time. We also find a novel algorithm to search border CPDs, a variant of CPDs that is also important in fast matrix multiplication. Finally, we study the maximum rank problem and give new upper and lower bounds, both for families of tensor shapes and specific shapes. Although our CPD search algorithms are still too slow to resolve the rank of $3\times 3$ matrix multiplication, we are able to utilize them in this problem by adding extra search pruners that do not affect exactness or increase asymptotic running time.