Lek-Heng Lim : Fast(est) Algorithms for Structured Matrices via Tensor Decompositions
It is well-known that the asymptotic complexity of matrix-matrix product and matrix inversion is given by the rank of a 3-tensor, recently shown to be at most O(n^2.3728639) by Le Gall. This approach is attractive as a rank decomposition of that 3-tensor gives an explicit algorithm that is guaranteed to be fastest possible and its tensor nuclear norm quantifies the optimal numerical stability. There is also an alternative approach due to Cohn and Umans that relies on embedding matrices into group algebras. We will see that the tensor decomposition and group algebra approaches, when combined, allow one to systematically discover fast(est) algorithms. We will determine the exact (as opposed to asymptotic) tensor ranks, and correspondingly the fastest algorithms, for products of Circulant, Toeplitz, Hankel, and other structured matrices. This is joint work with Ke Ye (Chicago).
- Category: Applied Math and Analysis
- Duration: 01:34:49
- Date: April 13, 2015 at 4:25 PM
- Tags: seminar, Applied Math And Analysis Seminar