Preprocessing Bilinear Algorithms

\gdef\vec#1{\mathbf#1} \gdef\mat#1{\mathrm#1} \gdef\setn#1{\mathcal#1} \gdef\p#1{\left({#1}\right)}

Giver vector spaces u,V,T over R, any bilinear map U × V → T can be uniquely represented using a rank-3 tensor over R where

b(\vec u, \vec v) = \sum_{ijk} u_i ⋅ v_j ⋅ t_{ijk} ⋅ \vec e_k

provided a basis for all three spaces.

Examples of bilinear maps are plentiful: dot products, polynomial multiplication, convolutions, matrix multiplication, etc.

Often we want to minimize the number of non-constant multiplications needed to compute a bilinear map. We can make the required number explicit using the bilinear algorithms:

b(\vec a, \vec b) = \mat C ⋅ \left( (\mat A ⋅ \vec a) ⊙ (\mat B ⋅ \vec b) \right)

For example for dot products A, B are identity matrices and C is a row vector of all ones, i.e. for a 2-dimensional dot product:

\vec a ⋅ \vec b = \begin{bmatrix} 1 & 1 \end{bmatrix} ⋅ \p{ \p{ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} ⋅ \vec a } ⊙ \p{\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} ⋅ \vec b}} This shows that two multiplications are required. But we can actually do this in one multiplication! We just need to precompute some values depending only on \vec a or \vec b:

a_0 ⋅ b_0 + a_1 ⋅ b_1 = (a_0 + b_1) ⋅ (a_1 + b_0) - a_0 ⋅ a_1 - b_0 ⋅ b_1

This is useful, but it can not be captured in the format of bilinear algorithms. So we generalize it by allowing intra-input products:

\mat C ⋅ \p{ \p { \mat A ⋅ \begin{bmatrix} \vec a \\ \vec b \end{bmatrix} } ⊙ \p{ \mat B ⋅ \begin{bmatrix} \vec a \\ \vec b \end{bmatrix} } }

By sorting the rows we can create the form

\begin{bmatrix} \mat C_a & \mat C_b & \mat C_{ab} \end{bmatrix} ⋅ \p{ \p { \begin{bmatrix} \begin{matrix} \mat A_a & 0 \\ 0 & \mat A_b \\ \end{matrix} \\\hline \mat A_{ab} \end{bmatrix} ⋅ \begin{bmatrix} \vec a \\ \vec b \end{bmatrix} } ⊙ \p{ \begin{bmatrix} \begin{matrix} \mat B_a & 0 \\ 0 & \mat B_b \\ \end{matrix} \\\hline \mat B_{ab} \end{bmatrix} ⋅ \begin{bmatrix} \vec a \\ \vec b \end{bmatrix} } }

Where the matrix dimensions are \begin{aligned} \mat A_a, \mat B_a &: r_a × n_a & \mat C_a &: n_c × r_a \\ \mat A_b, \mat B_b &: r_b × n_b & \mat C_b &: n_c × r_b \\ \mat A_{ab}, \mat B_{ab} &: r_{ab} × (n_a + n_b) & \mat C_{ab} &: n_c × r_{ab} \end{aligned}

We can precompute the two vectors (using r_a and r_b multiplications):

\vec c_a = \mat C_a ⋅ \p{ (\mat A_a ⋅ \vec a) ⊙ (\mat B_a ⋅ \vec a) } \\ \vec c_b = \mat C_b ⋅ \p{ (\mat A_b ⋅ \vec b) ⊙ (\mat B_b ⋅ \vec b) }

and then the bilinear map is computed with r_{ab} multiplications:

b(\vec a, \vec b) = \vec c_a + \vec c_b + \mat C_{ab} ⋅ \p{ \p { \mat A_{ab} ⋅ \begin{bmatrix} \vec a \\ \vec b \end{bmatrix} } ⊙ \p{ \mat B_{ab} ⋅ \begin{bmatrix} \vec a \\ \vec b \end{bmatrix} } }

The motivating example above has r_a = r_b = r_{ab} = 1:

\begin{bmatrix} -1 & -1 & 1 \end{bmatrix} ⋅ \p{ \p { \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ \end{bmatrix} ⋅ \begin{bmatrix} a_0 \\ a_1 \\ b_0 \\ b_1 \end{bmatrix} } ⊙ \p{ \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \end{bmatrix} ⋅ \begin{bmatrix} a_0 \\ a_1 \\ b_0 \\ b_1 \end{bmatrix} } }

This formalism is more generic than bilinear maps, it can also include quadratic forms of the input vectors. To restrict it to bilinear maps we need some further constraints on the matrices.

Question. Which constraints? We can collect coefficients of a_i⋅a_j and b_i⋅b_j and require that they sum to zero.

Square algorithms

Every Bilinear Algorithm of rank r can be turned into one requiring only 2⋅r squarings if 2 is invertible:

2 ⋅ a ⋅ b = (a + b)^2 - (a - b)^2