# Complexity: Number of MAC operations on a DSP

Suppose a complex $(N \times N)$ matrix $\mathbf{T}$, multiplying a complex vector $\mathbf{x}$ with length $N$.

On a given application that I'm studying, which is irrelevant for this discussion, I can get the same results of $\mathbf{Tx}$ by the following operation:

\begin{align} \mathbf{W_1} \Re\{ \mathbf{y} \} + \mathbf{W_2} \Im\{ \mathbf{y} \} \end{align} where are $\mathbf{W_1}$ and $\mathbf{W_2}$ are complex $(\frac{N}{2} \times \frac{N}{2})$ matrices, $\mathbf{y}$ is a complex vector of length $\frac{N}{2}$, $\Re$ denote the real part and $\Im$ the imaginary part.

I'm trying to asses which one requires more operations in a real implementation.

My analysis is that the first ($\mathbf{Tx}$) requires $N^2$ MACs, while the second requires

$2(\frac{N}{2})^2 = \frac{N^2}{2}$ MACs, plus $\frac{N}{2}$ sums.

I'm getting a completely different answer. I get the same answer for the number of total scalar operations, but the number of scalar complex operations is not the same as the number of scalar real operations.

Let's look at how much work it takes to do a complex scalar multiplication and complex scalar addition.

Given two complex scalars $z_0 = \langle x_0, y_0 \rangle$ and $z_1 = \langle x_1, y_1 \rangle$ then $z_0 z_1 = \langle x_0 x_1 - y_0 y_1, x_0 y_1 + x_1 y_0\rangle$, so 4 real multiplications and 2 real additions. $z_0 + z_1 = \langle x_0+x_1, y_0+y_1 \rangle$, so 2 scalar additions. The computation $\mathbf{Tx}$ requires a total of $N^2$ complex scalar multiplications and $N (N-1) = N^2-N$ complex scalar additions, so $4N^2$ real multiplications and $4N^2 - 2N$ scalar additions ($2N^2$ from the complex multiplications and $2N^2-2N$ from the sums for the dot products).

In the other case you seem to have some magical way of transforming to two much smaller complex matrices (perhaps your original matrix $\mathbf{T}$ was very sparse?), and your vectors are pure real (or pure imaginary) so a scalar multiplication only takes two real multiplications. $z_0 x_1 = \langle x_0 x_1, y_0 x_1\rangle$. So $\mathbf{W_1} \Re\{ \mathbf{y} \}$ requires $\frac{N^2}{4}$ complex times real multiplications, so $\frac{N^2}{2}$ total real multiplies, and $\frac{N}{2}(\frac{N}{2}-1)$ complex additions, so $\frac{N^2}{2}-N$ real additions. $\mathbf{W_2}\Im\{y\}$ has the same cost, and then you need to do a final sum of the two products at a cost of $\frac{N}{2}$ complex additions, so $N$ real additions. So your second technique takes a total of $N^2$ real multiplies and $N^2 - N$ real additions. So your second technique should take about $\frac{1}{4}$th the work of the original technique.

• Perfect math, thank you. It is indeed approximately 4x faster when analyzed with tic/toc on matlab. Jun 27, 2013 at 18:25

It appears to me that your analysis is basically correct, except that in the second case there are $\frac{N}{2}$ sums, not $N$ sums.

I'm not sure what you are looking for when you ask "how a DSP deals with complex numbers", but generally they are represented in one of two ways: as separate real and imaginary values, or as a "complex" entity (structure/object/whatever- depends on the language) that contains real and imaginary members.

• Thanks for the correction, it is indeed $\frac{N}{2}$. I mean, for example, that I don't know whether the operation of taking the Real and Imaginary part of $\mathbf{y}$ adds complexity or not. Also, I'm not sure if the calculation of $\mathbf{Tx}$ is acomplished by $\mathbf{T}\Re{\mathbf{x}} + j\mathbf{T}\Im{\mathbf{x}}$ or a different way. Jun 25, 2013 at 16:45
• It sounds like what you really want to know is "which one is faster". If so, we can make educated guesses but modern computers are complex enough that the only way to really know is try it both ways and see which one is faster. Jun 25, 2013 at 17:15
• That's right. Is "tic; toc;" on MATLAB sufficient for this? I tried and, for large $N$, the second approach ($\mathbf{W_1} \Re\{ \mathbf{y} \} + \mathbf{W_2} \Im\{ \mathbf{y} \}$) is being faster. Jun 25, 2013 at 17:24
• Yes, as long as the resolution is such that you aren't getting answers like "0" and "1", then tic/toc is fine. Jun 25, 2013 at 17:26