 Bilinear algorithm

A bilinear algorithm computes a bilinear map $b:U\times V\to W$ by multiplying linear expressions in the two inputs and linearly combining the results. A length-$r$ algorithm has the formwith ${\alpha }_j\in U^{\ast }$, ${\beta }_j\in V^{\ast }$ and $w_j\in W$. Its multiplication count is the number of products between input-dependent expressions; additions and multiplication by fixed constants are accounted for separately. The smallest possible length is the tensor rank of the associated tensor in $U^{\ast }\otimes V^{\ast }\otimes W$.^[ref]

For multiplication of complex numbers over the real numbers, the usual formulas use four real products. Instead compute $p=ac$, $q=bd$ and $r=(a+b)(c+d)$. ThenOnly three real products are needed. This saves a multiplication by sharing intermediate information between the two outputs.

The coefficient field and cost model matter. Allowing divisions by expressions depending on the input is outside this bilinear model. Border rank also allows limits of algorithms and can be smaller than the minimum length of an exact bilinear algorithm.