0
$\begingroup$

I have a real matrix $Z$ which is following the form as following:

$Z = \begin{bmatrix} x_1& 0& 0& 0& 0& 0& 0& 0\\ 0& x_2& 0& 0& 0 & 0& 0& -x_4\\ 0& 0& x_3& 0& 0& 0& -x_3& 0\\ 0& 0& 0& x_4& 0& -x_2& 0&0 \\ 0& 0& 0& 0& -x_1& 0& 0& 0\\ 0& 0& 0& -x_2& 0& -x_4& 0& 0\\ 0& 0& -x_3& 0& 0& 0 & -x_3& 0\\ 0& -x_4& 0& 0& 0& 0& 0& -x_2 \end{bmatrix}$

If the above matrix is multiplied with a real vector $x$, what will be the complexity in function of real multiplications and real addition?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I believe your question fits better in the Computational Science StackExchange (scicomp.stackexchange.com) or the Computer Science StackExchange (cs.stackexchange.com) [I believe the fist is a better match though]. $\endgroup$
    – ZaellixA
    Commented Jul 3, 2022 at 10:02
  • 2
    $\begingroup$ What keeps you from counting the number of multiplications and additions yourself? $\endgroup$
    – Matt L.
    Commented Jul 3, 2022 at 10:56
  • $\begingroup$ @MattL. I mean will the similarity of elements reduce the required real operations? That is what I am looking for. For example $x_2$ has been repeated for four times. On the other hand, yes I agree with you that counting the number of multiplications and additions can be done straightforwardly. $\endgroup$
    – Gze
    Commented Jul 3, 2022 at 11:04

1 Answer 1

Reset to default
3
$\begingroup$

If you multiply an $M \times N$ matrix with an $N \times 1$ vector you get a vector of size $M \times 1$

For the generic case you will need $M \cdot N$ multiplications and $M \cdot (N-1)$ additions.

For a sparse matrix the number of multiplications can be reduced to the number of non-zero elements and the number of additions is somewhat less, depending on the exact strucure of the sparsity. In your case that would be 14 multiplications and 6 additions.

I mean will the similarity of elements reduce the required real operations?

Not, if this is single multiply and you don't apply any constraints on the vector data. You can theoretically eliminate multiplications if you have identical elements in a column, but that's not the case here.

There could be reduction of complexity if you need to apply the same matrix multiplication repeatedly on a stream of data, but that depends on the details.

Improve this answer
$\endgroup$
6
  • $\begingroup$ you mean $(N-2)$ addition, but what's about the 16? I think it should be 14 which is $(2(N-1))$ as two columns have only one non-zeros value. Am I correct ? $\endgroup$
    – Gze
    Commented Jul 3, 2022 at 13:45
  • $\begingroup$ Yep, 14, not 16, fixed. And I do mean $M \times (N-1)$ for the generic case, if that's what you mean. For the spares case it's the sum over all rows of "non-zero-elements -1", not $N-2$. In your case this is just coincidence. $\endgroup$
    – Hilmar
    Commented Jul 3, 2022 at 14:40
  • $\begingroup$ what about if we multiplied $[Z , -Z]$ with a real vector with length $2N$? will the complexity be doubled also ? $\endgroup$
    – Gze
    Commented Jul 4, 2022 at 3:08
  • $\begingroup$ What exactly does does $[Z,-Z]$ mean ? $\endgroup$
    – Hilmar
    Commented Jul 4, 2022 at 16:26
  • $\begingroup$ $[Z, -Z]$ is just a matrix which collect the matrix $Z$ with its negative version. for example if it's of size $2 \times 2$, the new matrix will be $2 \times 4$. $\endgroup$
    – Gze
    Commented Jul 5, 2022 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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