  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.
