On 18/10/2007, Laurent Decreusefond <address@hidden>
wrote:
Because I didn't think of it (all algebraic topology books I have
read (I am new at it) use Smith form)
That's because they're not numerical analysts. :-)
and I guess the general
algorithm for matrices of float in Matlab (which I should confess,
I don't know) must behave slowlier than the specific algorithm for
integer valued matrices (i.e. the Smith form).
It uses the matrix's SVD decomposition, which can indeed be a little
slow if the matrix is of size 1500x1500 or thereabouts. How big are
your matrices?
I'm estimating that the Smithification algorithm is about the same
big-Oh as Gaussian elimination, since it's basically a double Gaussian
elimination with a few twists, modulo taking some gcd's that shouldn't
affect the big-Oh running time.
On my machine with Octave 2.9.13,
octave2.9:1> A = rand(1000);
octave2.9:2> tic, rank(A); toc
Elapsed time is 3.896004 seconds.
octave2.9:3> tic, rref(A); toc
Elapsed time is 42.748375 seconds.
so my guess is that you're better off with SVD than with the Smith
factorisation.
- Jordi G. H.