2
$\begingroup$

I have a system of fairly large set of linear equations (approximately 30K equations). I am using scipy.sparse.spsolve to solve these equations. Initially, I tried with 10K equations, but my program got killed due to memory issue. In general, I would like to know the memory and time requirements of the spsolve algorithm and exactly how the algorithm solves the system of equations. Is it based on factorization? Anyone can help me?

NB* - system of equations does not have a predefined structure like symmetricity etc, only thing is it is very sparse.

$\endgroup$
  • 1
    $\begingroup$ I have solved systems with ~ 10M systems of equations in a laptop with 8 GB of RAM. $\endgroup$ – nicoguaro Dec 28 '18 at 17:33
  • $\begingroup$ @nicoguaro using numpy/scipy ? I am very much surprised. I find it difficult to run mine with 10K equations on a server with 32GB RAM. You care to give some tips ? $\endgroup$ – Shew Dec 30 '18 at 11:42
  • 1
    $\begingroup$ My matrices come from finite elements and I use COOrdinate list (COO) for the assembly and turn it into Compressed Sparse Row (CSR) for the solution phase. $\endgroup$ – nicoguaro Dec 30 '18 at 15:12
4
$\begingroup$

First of all, you need to make sure that you construct & store your original matrix already in a sparse format. Otherwise, your problems can start already at this stage, since storing such a large matrix in dense format and only then converting it to sparse can easily blow up the memory.

According to scipy.sparse.linalg.spsolve documentation, by default it uses UMFPACK, which would be multifrontal LU factorization. This answer will give you some insight on what may actually happen in your case (fill-ins). In short, there is a chance that even though your non-factorized matrix is sparse, its structure (and reorderings used in the factorization algorithm) result in a lot of fill-ins, resulting in a much denser factorized matrix.

In general, it's quite hard to give time&memory estimates for sparse matrix factorization since a lot depends on the structure of the matrix, used algorithms, and strategies to reduce fill-ins.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.