2
$\begingroup$

I have a (right) sub-stochastic CSC sparse matrix $Q$ of dimension 5 million, with 200 million nonzero entries, which is a nonzero percentage of 0.0008%, so it is indeed extremely sparse. It is not banded, nor does it have any other obvious sparsity pattern.

I'm trying to solve the linear system,

$$(I-Q)x={\bf 1}$$

I've been working in Julia with 64GB of RAM, and I've tried the following command,

SparseArrays.UMFPACK.ldiv!(x, SparseArrays.UMFPACK.lu(I-Q), ones(size(Q,1)))

where $x$ is the dummy vector of zeros to which the solution will be assigned.

Unfortunately, this causes an OutOfMemoryError(), and so I'm not entirely sure how to proceed. I don't have too much intuition for deciding what algorithm to use when solving large sparse linear systems, given its size, should I perhaps try an iterative approach?

$\endgroup$

1 Answer 1

5
$\begingroup$

Yea, iterative solvers are often more effective for sparse problems, as long as the condition number isn't too large. IterativeSolvers.jl provides several common methods.

The general recommendation is usually to use Conjugate Gradient for symmetric, positive definite problems and to use GMRES or BiCGSTAB for everything else. Choosing the best parameters is a bit of an art form, and depends on your matrix. I'd suggest starting with the default values and experimenting if they don't work well enough. (For example, in GMRES using a larger restart can give faster and more robust convergence but costs more per iteration and increasing the memory requirement.)

Using a preconditioner can help improve convergence, by reducing the condition number of your matrix. Loosely, you can think of the preconditioner as a really cheap approximation of the inverse. IterativeSolvers.jl recomends several Julia packages for preconditioners. I'd probably suggest starting with either no preconditioner or an incomplete LU and seeing if that works well enough for your application.

$\endgroup$

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.