1
$\begingroup$

I have two huge sparse matrices, and I am interested in dot multiplication them. But I have a memory issue so a notebook is a shutdown. I am using the 11.3 version. Any suggestion on how to avoid memory issues.

Edit:

n = 30000;
m = 22000000;
mat = SparseArray[
   RandomInteger[{1, n}, {m, 2}] -> RandomReal[{0, 1}, m], {n, n}];
mat2 = SparseArray[
   mat["NonzeroPositions"] -> 
    RandomReal[{0, 1}, Length@mat["NonzeroPositions"]], 
   Dimensions[mat]];
$\endgroup$
12
  • 2
    $\begingroup$ Should the actual matrices be too large, one has to avoid matrix-matrix multiplication to to rephrase everything into matrix-vector mutiplications. For example, u being a vector, instead of res.u, you should use mat.(mat.u). This might bring also a considerable speed-improvement, if only few of results of the form res.u are needed. I gets more complicated when res has to enter a linear system which you want to solve. But if you cannot build res, then you cannot solve the system with direct methods anyways. So you would have to switch to (preconditoned!) iterative methods. $\endgroup$ Commented Sep 3, 2018 at 21:04
  • 1
    $\begingroup$ ... and for these iterative methods (e.g. GMRES), you need only matrix-vector multiplication. So also in that case, you can go with mat.(mat.u). $\endgroup$ Commented Sep 3, 2018 at 21:05
  • 2
    $\begingroup$ Are you sure that both matrices that you dot-multiply, are sparse? If one is dense, then the product will be coerced to a sense matrix. If the dense matrix is of size $k \times n$ and the sparse matrix is of size $n \times m$ with $k n \ll n m$, then the product will be a dense $k \times m$ matrix and may not fit into memory although each factor fits. $\endgroup$ Commented Sep 3, 2018 at 21:20
  • 4
    $\begingroup$ If Mathematica is repeatedly crashing, it might be worth restarting your computer. $\endgroup$
    – mikado
    Commented Sep 3, 2018 at 21:47
  • 2
    $\begingroup$ Dot products of two sparse matrices (unless they are very sparse) will result in a SparseArray representation of a dense matrix (this will cause a memory issue). Division on the other hand has a divide by 0 issue, but should not have a memory issue. $\endgroup$
    – Carl Woll
    Commented Sep 5, 2018 at 17:06

1 Answer 1

1
$\begingroup$

More an extended comment than an answer.

Many of us are used to obtain a quite sparse matrix from the matrix product of two sparse matrices. That's is maybe because we are used to obtain sparse arrays as the system matrices of differential equations where each degree of freedom interacts with only few other degrees of freedoms or as adjacency matrices of more or less random graphs. But actually, it suffices to have one degree of freedom in the system (or a vertex that is connected to all other vertices in the graph) in order to obtain a completely dense matrix from a multiplication of a matrix with itself as the following example shows:

n = 10000;
A = SparseArray[{}, {n, n}];
A[[1, All]] = 1;
A[[All, 1]] = 1;
A["Density"]
B = A.A;
B["Density"]

0.00019999

1.

$\endgroup$
1
  • 3
    $\begingroup$ This is in part because no sparsification is done along the way, e.g. To see if a different background value might work. But your point remains valid, and random values would force a dense matrix there. For many purposes, it can be better to defer matrix-times-matrix altogether, and instead iterate matrix-times-vector. $\endgroup$ Commented Sep 5, 2018 at 19:48

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.