0
$\begingroup$

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 not completely sure about this, neither about how a DSP deals with complex numbers. Am I making any mistake?

I'd appreciate your help.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perfect math, thank you. It is indeed approximately 4x faster when analyzed with tic/toc on matlab. $\endgroup$ – igorauad Jun 27 '13 at 18:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – igorauad Jun 25 '13 at 16:45
  • $\begingroup$ 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. $\endgroup$ – Jim Clay Jun 25 '13 at 17:15
  • $\begingroup$ 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. $\endgroup$ – igorauad Jun 25 '13 at 17:24
  • $\begingroup$ Yes, as long as the resolution is such that you aren't getting answers like "0" and "1", then tic/toc is fine. $\endgroup$ – Jim Clay Jun 25 '13 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.