number of complex multiplications in quadratic form

Question

I want to find the number of complex multiplication and additions in $\textbf{Y}^H \textbf{D} \textbf{B}\textbf{D}^H\textbf{Y}$ where $\textbf{Y}$ is $N\times 1$ vector, $\textbf{D}$ is $N\times N $ diagonal matrix and $\textbf{B}$ is a full $N\times N$ matrix and all elements are complex. I am getting it to be $2N^2+N$ multiplications and $N^2-1$ additions. But the answer is $N^2+3N$ multiplications and $N^2-N$ additions. Can anyone help me with this?

Answer 1

The answer very much depends on the algorithm you use to perform the calculation. In particular, noting that $$(Y^HD)^H = D^HY$$ allows you to perform $N$ multiplications where a naive approach would require $2N$.

However, if we ignore this and use the naive approach of starting on the right and moving left, we get:

1. $D^HY$: $N$ multiplications, as each diagonal element of $D^H$ multiplies just one element of $Y$.
2. $B(\dots)$ : For each row of $B$, multiplying by the vector involves $N$ multiplications and $N - 1$ additions. Since $B$ has $N$ rows, this involves $N\times N = N^2$ multiplications and $N \times (N - 1) = N^2 - N$ additions.
3. $D(\dots)$ : as with the first diagonal multiplication, this involves $N$ multiplications with no additions needed.
4. $Y^H(\dots)$ : An additional $N$ multiplications and $N - 1$ additions.

So adding it all together, there are $$N + N^2 + N + N = N^2 + 3N$$ multiplications and $$0 + (N^2 - N) + 0 + (N - 1) = N^2 - 1$$ additions.

So I agree with your answer key about multiplications, but with you for additions. And as I noted, working a little smarter reduces the number of multiplications to $N^2 + 2N$.