[SciPy-User] solving large sparse linear system with Laplacian matrix

Pauli Virtanen pav+sp@iki...
Fri Oct 30 04:50:59 CDT 2009


Fri, 30 Oct 2009 04:43:23 -0400, David Warde-Farley wrote:
> On 30-Oct-09, at 4:25 AM, josef.pktd@gmail.com wrote:
>> I don't know about memory consumption but I think
>> scipy.sparse.linalg.factorized(A)
>> should be more efficient if you need to solve for several right hand
>> sides.
> 
> You may be right but the factorized matrices may be an awful lot denser
> which could impact her memory requirements.
> 
> You may have some luck with lgmres and/or bicg, as far as I know neither
> imposes conditions on positive definiteness.

I remember there's also a block-version of LGMRES that's expected to be 
somehow more efficient with multiple right-hand sides. The implementation 
in scipy is for the plain version, however, and IIRC handles only one rhs 
at a time.

I guess you can already do something similar:

	outer_v = []
	r = zeros_like(B)
	for j, b in enumerate(B.T):
	    r[j] = scipy.sparse.linalg.lgmres(A, b, inner_m=6, tol=1e-6,
	                                      inner_m=10, outer_k=6,
	                                      outer_v=outer_v)

Ie. store part of the old solution subspace, to accelerate solution of 
the next linear systems. This might (I'm not really sure) help if the 
right-hand side vectors are in some sense "similar" to each other.

In addition to scipy.sparse.linalg.lgmres, you can also try plain GMRES 
(scipy.sparse.linalg.gmres) -- if it converges, it might be faster, since 
the linear algebra part of current LGMRES implementation in Scipy is not 
fully optimized and may become slow if you choose to use huge inner 
subspaces.

-- 
Pauli Virtanen



More information about the SciPy-User mailing list