1
$\begingroup$

A sparse matrix $\mathbf{L}$ is formed by $\mathbf{L} = \mathbf{DKG}$.

  • $\mathbf{D}$ is a sparse matrix of size $m \times n$.
  • $\mathbf{G}$ is a sparse matrix of size $n \times m$.
  • $\mathbf{K}$ is a diagonal matrix of size $n \times n$.

$\mathbf{L}$ needs to be formed many times based on the updated diagonal entries of $\mathbf{K}$. Both $\mathbf{D}$ and $\mathbf{G}$ never change.

Is there a faster way to form $\mathbf{L}$ without preforming two full sparse matrix multiplications?

$\endgroup$

1 Answer 1

4
$\begingroup$

Each entry $K_{i,i}$ on the diagonal of $K$ is multiplied by the outer product of column $i$ of $D$ and row $i$ of $G$. You can write the product as

$DKG=\sum_{i=1}^{n} K_{i,i}(D_{:,i}G_{i,:})$

If you precompute and store the sparse outer products $D_{:,i}G_{i,:}$, then you can quickly multiply these by $K_{i,i}$ and add those terms into your product. Since the product matrix sparsity pattern doesn't change, you can preallocate a data structure with the sparsity pattern of the product and reuse it each time you update $K$.

In doing this, you can save time by precomputing where in the sparse product matrix each entry of $D_{:,i}G_{i,:}$ belongs. e.g. if there is an entry in $D_{:,1}G_{1,:}$ at position (3,4), and you know that position (3,4) is stored in the 33rd entry of the DKG product matrix, then record the fact that this is the 33rd entry in the product matrix rather than recording (3,4).

$\endgroup$
1
  • $\begingroup$ By the way, this doesn't depend at all on $K$ being a diagonal matrix. The same approach works with any sparse $K$. $\endgroup$ Commented Dec 9, 2017 at 4:27

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.