Faster Complex Matrix Multiplication via Split-Complex Numbers

Here is a nice application of split-complex numbers. Let $Z_1 = A + i B$ and $Z_2 = C + i D$ be complex matrices. Their product is defined as

$Z_1 Z_2 = (A + i B) (C + iD) = (A C - B D) + i(AD + BC)$

which requires 4 real matrix multiplications. Here I will show that we can do this with 3 real matrix multiplications by using split-complex numbers.

First, by taking split-complex matrices $W_1 = A + j B$ and $W_2 = C + j D$ and rewriting them in basis $\{\iota, \iota^*\}$ as follows

$\begin{align*}W_1 & = (A+B) \iota + (A-B) \iota^* \\W_2 &= (C+D) \iota + (C-D) \iota^*\end{align*}$

we have

$W_1 W_2 = (A+B)(C+D) \iota + (A-B)(C-D) \iota^*$

which requires only 2 real matrix multiplications. This all follows from my previous post.

Let us now define

$\begin{align*}X & := \frac{1}{2} (A + B) (C + D) \\ Y & := \frac{1}{2} (A - B) (C - D).\end{align*}$

We have

$W_1 W_2 = (X + Y ) + j (X - Y).$

But now, since

$W_1 W_2 = (AC + BD) + j (AD + BC)$

then by comparison $AC + BD = X + Y$ and $AD + BC = X - Y$ .

Finally, from this and the fact $AC - BD = X + Y - 2 BD$ we have

$Z_1 Z_2 = (X + Y - 2 BD) + i(X - Y)$

which requires only 3 real matrix multiplications, namely $(A+B)(C+D)$ , $(A-B)(C-D)$ and $BD$ .

EDIT: A simple implementation of this approach can be found here.

The Hitchhiker's Guide to Computable Mathematics