Matrix Computations and Scientific Computing Seminar: Fastest algorithms for structured matrices via algebra

Seminar | January 18 | 11:10 a.m.-12 p.m. | 380 Soda Hall

 Lek-Heng Lim, University of Chicago

 Department of Mathematics

We show that in many instances, at the heart of a problem in numerical computation sits a special 3-tensor, the structure tensor of the problem that uniquely determines its underlying algebraic structure. For example, the Grothendieck constant, which plays an important role in unique games conjecture and SDP relaxations of NP-hard problems, arises as the spectral norm of such a structure tensor. In matrix computations, a decomposition of the structure tensor into rank-1 terms gives an explicit algorithm for solving the problem, its tensor rank gives the speed of the fastest possible algorithm, and its nuclear norm gives the numerical stability of the stablest algorithm. We will determine the fastest algorithms for the basic operation underlying Krylov subspace methods — the structured matrix-vector products for sparse, banded, triangular, symmetric, circulant, Toeplitz, Hankel, Toeplitz-plus-Hankel, BTTB matrices — by analyzing their structure tensors. Our method may be viewed as a vast generalization of the Cohn–Umans method, allowing for arbitrary bilinear operations in place of matrix-matrix product, and arbitrary algebras (particularly coordinate rings of schemes, cohomology rings of manifolds, PI algebras) in place of group algebras. The second part is joint work with Ke Ye.