2
$\begingroup$

I have a vector $\mathbf{x}$ of size $m\cdot n$ of zeros and ones, i.e., $\mathbf{x}\in\{0,1\}^{m\cdot n}$ and a matrix $\mathbf{A}$ of size $\left(m\cdot n+m+n+1\right)\times\left(m\cdot n\right)$ of reals, i.e., $\mathbf{A}\in\mathbb{R}^{\left(m\cdot n+m+n+1\right)\times\left(m\cdot n\right)}$.

The vector $\mathbf{x}$ has $O(m\cdot n)$ zeros and the matrix $\mathbf{A}$ has $O(m^2\cdot n+n^2\cdot m)$ zeros.

I would like to know the complexity of multiplying $\mathbf{A}$ by $\mathbf{x}$. Using a naive analysis, the complexity would be of the order of $O(m^2\cdot n^2)$ but I think that we can give a more rigorous analysis given that $\mathbf{x}$ and $\mathbf{A}$ have a lot of zeros elements.

Can you please give me some ideas, references?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

The problem is essentially equivalent to asking for the complexity of calculating the vector $$ \mathcal{V} := \{ \mathcal{A}_0\cap \mathcal{x}, \mathcal{A}_1\cap \mathcal{x},\ ...,\ \mathcal{A}_{mn+m+n}\cap\mathcal{x} \}$$ where the $\mathcal{A}_i$ are the sets of indices corresponding to the non-zero entries of the $i$-th row of $A$ and analogously, $\mathcal{x}$ corresponds to the non-zero entries of $x$.

The number required multiplications in the general case (i.e. if that the entries of $x$ are not restricted to $0$ and $1$), is then $$\sum_{i=0}^{mn+m+n} \mathcal{card}(\mathcal{A}_i\cap\mathcal{x}) $$ whereas an upper bound for the number of additions (the complexity you are interested in) is $$\left(\sum_{i=0}^{mn+m+n} \mathcal{card}(\mathcal{A}_i\cap\mathcal{x})\right)\ -\ (mn+m+n+1) $$

$$ $$ The complexity of the problem depends however also on further assumptions, e.g.

  • is the representation of $A$ and $x$ given or, can it be defined?

  • is $A$ reused in further multiplications with other vectors (e.g. the column-vectors of a sparse matrix $B$?

  • are there memory restrictions (i.e. try to avoid generating 0-elements of the result-vector)?

The final question would be, if you are also interested in algorithms and datastructures.

$\endgroup$

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.