Re: Is A\b using a sparse solver if A is sparse?

[David Bateman]

LUK ShunTim wrote:

> David Bateman wrote:
> > LUK ShunTim wrote:
> >
> >> Hello,
> >>
> >> If A is sparse, will A\b automatically use the sparse variant of the
> >> linear equation solver?
> >>
> >> Regards,
> >> ST
> >> --
> >>
> > Yes.. In fact in 2.9.x it uses a polymorphic solver that has a 
> selection
> > tree
> >
>
> [snipped]
>
> Thanks very much.
>
> I got this rather strange result on octave 2.1.72 + octave-forge in
> debian/sid.
>
> <diary>
> octave:2> A=sprand(2500,2500,0.03);
> octave:3> b=eye(2500,1);
> octave:4> r=A*b;
> octave:8> fullA=full(A);
> octave:9> tic;A\r;toc
> ans = 19.277
> octave:10> tic;A\r;toc
> ans = 19.073
> octave:11> tic;A\r;toc
> ans = 19.340
> octave:12> tic;fullA\r;toc
> ans = 5.2551
> octave:13> tic;fullA\r;toc
> ans = 5.0916
> octave:14> tic;fullA\r;toc
> ans = 5.1038
> </diary>
>
> The full version appears to be *faster* than the sparse version (!),
> which seems to be counter-intuitive. What have I missed?
>
> Regards,
> ST
> --
What you missed is that the LU factorization of a random sparse matrix 
is full. Therefore as you observed this means that the solution of a 
linear equation involving such a matrix will be slower than the full 
version. The sparse solver needs to have some structure in the sparse 
matrix that it can profit from to reduce the amount of fill-in during 
the factorization.

Also for 2.1.72 the sparse code is in octave-forge and is not as 
advanced as in 2.9.x. If you intend to use octave for sparse matrices, I 
strong suggest using the 2.9.x series even if they are still marked as 
testing.

D.

--
David Bateman                                address@hidden
Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob) 
91193 Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax) 

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------