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?



Complexity of sparse matrix-vector multiplication?
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. 


