The multiplication of two complex matrices may be written as \[ \begin{aligned} (A+iB)(C+iD) &= (AC-BD) + i(AD+BC) \tag{1}\\ &= [(A-B)D + A(C-D)] + i[(A-B)D+B(C+D)] \tag{2}\\ &= E+iF \end{aligned} \] where \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) are \(N \times N\) matrices with real valued elements. The desired result is the complex matrix \(E+iF\). The standard method (1) requires four real matrix multiplications, which can be reduced to three by simply rewriting (1) as (2).
This paper develops a new algorithm to increase the computational efficiency of the complex matrix multiplication by utilizing a surrogate matrix. This surroga te is a matrix of simple form which, when squared, results in the negative of the identity matrix \(I\). The number of real matrix multiplications required can be reduced from four to two for \(N\) even, and to \(2+1/N^ 2\) for \(N\) odd. An additional matrix multiplication is required for \(N\) odd. However, this multiplication will not be of full rank, so that for large \(N\) the number of real matrix multiplications approaches two. The disadvantage of the new algorithm is the imposition of a requirement on the structure of one of the two complex matrix for either of the matrix pairs \(A\) and \(B\), or \(C\) and \(D\) to commute with the surrogate matrix.
The \(2 \times 2\) case of the algorithm can be adapted to computing Givens rotations, resulting in a 17 percent in real matrix multiplications over previous fast algorithms requiring three multiplications.