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. As an explicit example, we 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 is a generalization of the Cohn--Umans method, allowing for arbitrary bilinear operations in place of matrix-matrix product, and arbitrary algebras (e.g., coordinate rings of schemes, cohomology rings of manifolds, PI algebras) in place of group algebras. The second part is joint work with Ke Ye.

Presentation by: Lek-Heng Lim. University of Chicago, USA