标题： 使用截断分解进行矩阵乘法的有效近似 显示英文标题

标题： Efficient approximations of matrix multiplication using truncated decompositions

摘要： 我们利用截断奇异值分解和最近提出的循环分解，以实现对大型密集矩阵乘法的有效一阶近似。 将每个矩阵分解为一个具有相对较少主要条目的稀疏矩阵和一个密集余数的和，也可以使用上述方法，并且我们提出了使用傅里叶分解和基于循环分解的稀疏化进行乘法的方法。 所提出的方法在算术运算中的复杂度为$\mathcal{O}(n^2 \log n)$，对于$n \times n$矩阵，在相对误差$\sim$为 1% 的可接受容差下有效。 请注意，在乘积$AB$中，矩阵$A$和$B$可以使用不同的分解方法，通过高效的先验评估来选择合适的分解，以进一步提高此处展示的误差容限。 显示英文摘要

摘要： We exploit the truncated singular value decomposition and the recently proposed circulant decomposition for an efficient first-order approximation of the multiplication of large dense matrices. A decomposition of each matrix into a sum of a sparse matrix with relatively few dominant entries and a dense residue can also use the above approach, and we present methods for multiplication using a Fourier decomposition and a cycle decomposition-based sparsifications. The proposed methods scale as $\mathcal{O}(n^2 \log n)$ in arithmetic operations for $n \times n$ matrices for usable tolerances in relative error $\sim$ 1\%. Note that different decompositions for the two matrices $A$ and $B$ in the product $AB$ are also possible in this approach, using efficient a priori evaluations for suitability, to improve further on the error tolerances demonstrated here.