Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans Method
Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans Method
复制标题
DOI：
10.1007/s10208-016-9332-x
复制
发表时间：
2016-01
影响因子：
3
通讯作者：
Ke Ye;Lek-Heng Lim
中科院分区：
文献类型：
--
作者：
Ke Ye;Lek-Heng Lim
我们讨论了Cohn-umans方法的推广，Cohn-umans方法是一种通过将矩阵嵌入到适当的群代数中来研究矩阵乘法的双线性复杂性的有效方法。我们研究了Cohn-umans方法如何用于双线性运算，而不是矩阵乘法，并将其与Strassen张量秩法联系起来，Strassen张量秩法是研究双线性复杂性的传统框架。为了证明广义方法的实用性，我们将其应用于构造结构化矩阵-向量积的最快算法，这是结构化矩阵迭代算法的基本运算。我们研究的结构包括Toeplitz、Hankel、循环、对称、斜对称、f-循环、块Toeplitz-Toeplitz块、三角Toeplitz矩阵、Toeplitz-Plus-Hankel、稀疏/带状/三角形。除了有上界的反对称矩阵外，在所有其他情况下，用广义Cohn-umans方法导出的算法在具有最小双线性复杂度的意义下都是最快的。我们还将该框架应用于其他一些双线性运算，包括矩阵-矩阵、交换子、同时矩阵乘积，并简要讨论了张量核范数与数值稳定性之间的关系。
We discuss a generalization of the Cohn–Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn–Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen’s tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix–vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric,f-circulant, block Toeplitz–Toeplitz block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn–Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix–matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability.