= Bilinear algorithm
{title2=$b(u,v)=\sum_{j=1}^r\alpha_j(u)\beta_j(v)w_j$}
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 form
$$
b(u,v)=\sum_{j=1}^r\alpha_j(u)\beta_j(v)w_j,
$$
with $\alpha_j\in U^*$, $\beta_j\in V^*$ 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^*\otimes V^*\otimes W$.<Geometry and complexity theory by J. M. Landsberg>[section 1.1, bilinear maps and multiplication complexity]{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)$. Then
$$
(a+ib)(c+id)=(p-q)+i(r-p-q).
$$
Only 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>.
Back to article page
