Georgia Institute of Technology College of Sciences

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. 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 is a vast generalization of the Cohn--Umans method, allowing for arbitrary bilinear operations in place of matrix-matrix product, and arbitrary algebras in place of group algebras. This talk contains joint work with Ke Ye and joint work Shmuel Friedland.