论文标题
稀疏快速矩阵乘法算法的操作员
Sparsifying the Operators of Fast Matrix Multiplication Algorithms
论文作者
论文摘要
只要在实践中，快速矩阵乘法算法可能是好的。特别是，其算术复杂性的领先系数必须很小。许多亚基算法具有较大的领先系数，使其不切实际。 Karstadt和Schwartz（Spaa'17，Jacm'20）演示了如何通过稀疏算法的双线性操作员来减少这些系数。不幸的是，找到最佳稀疏度的问题是NP- hard。 我们为此获得了三种新方法，并将它们应用于现有的快速矩阵乘法算法，从而改善其领先系数。这些方法具有指数级的最差运行时间，但是在实践中快速运行并提高了许多快速矩阵乘法算法的性能。保证其中两种方法可产生领先的系数，在某些假设下，这些系数是最佳的。
Fast matrix multiplication algorithms may be useful, provided that their running time is good in practice. Particularly, the leading coefficient of their arithmetic complexity needs to be small. Many sub-cubic algorithms have large leading coefficients, rendering them impractical. Karstadt and Schwartz (SPAA'17, JACM'20) demonstrated how to reduce these coefficients by sparsifying an algorithm's bilinear operator. Unfortunately, the problem of finding optimal sparsifications is NP-Hard. We obtain three new methods to this end, and apply them to existing fast matrix multiplication algorithms, thus improving their leading coefficients. These methods have an exponential worst case running time, but run fast in practice and improve the performance of many fast matrix multiplication algorithms. Two of the methods are guaranteed to produce leading coefficients that, under some assumptions, are optimal.
