Re: Smith Form

[Jordi Gutiérrez Hermoso]

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.