My goal is to efficiently compute a particular matrix-vector product, say, $\bf{Ax}$, where $\bf{A}$ is a matrix and $\bf{x}$ is a vector. I don't know whether or not $\bf{A}$ is sparse, but I want to find that out, given the information below.

As it turns out, I know that $\bf{A} = \bf{DB}$, where the matrix $\bf{D}$ is sparse, but the matrix $\bf{B}$ is not. $\bf{D}$ and $\bf{B}$ are of the same size, and are both known.

I know that if the required matrix-vector product had been $\bf{Dx}$, my life would have been easier, because $\bf{D}$ is sparse, and I can compute $\bf{Dx}$ efficiently.

But, I'm worried that multiplying $\bf{D}$ with $\bf{B}$ will ruin its sparsity, and thus the efficiency of the matrix-vector product. Are there any conditions under which $\bf{A}$ will also be sparse? Or is it the case that nothing general can be said without further information?


  • 2
    $\begingroup$ The unit matrix is sparse. If you multiply it with a dense matrix then you obviously get a dense matrix. $\endgroup$
    – md2perpe
    Commented Sep 23, 2017 at 20:03
  • $\begingroup$ Another example is letting $\mathbf X$ be a $2n \times 2n$ matrix with $1$ in every position and $\mathbf Y$ also be a $2n \times 2n$ matrix having $1$ in all positions in $n$ rows and $-1$ in all positions in the other half of the rows. Then $\mathbf X$ and $\mathbf Y$ are both dense, but $\mathbf X \mathbf Y = \mathbf 0$ is sparse. $\endgroup$
    – md2perpe
    Commented Sep 23, 2017 at 20:09
  • $\begingroup$ Thus, nothing can be said. $\endgroup$
    – md2perpe
    Commented Sep 23, 2017 at 20:09
  • $\begingroup$ For starters, even the product of two sparse matrices is not sparse in general. $\endgroup$
    – Clement C.
    Commented Sep 23, 2017 at 20:09
  • $\begingroup$ Good points; thank you. $\endgroup$
    – josh_eime
    Commented Sep 23, 2017 at 20:23


You must log in to answer this question.

Browse other questions tagged .