Smith Normal Form of a very large sparse integer matrix

[oliver]

Hello,

I am trying to calculate the Smith Normal Form of a very large sparse
integer matrix. Can anyone tell me the commandline parameters to get
the Smith example program to do it? Or just what SmithForm function I
should invoke.

Thanks,

Oliver

[Jean-Guillaume Dumas]

oliver a écrit :

Dear Oliver, the right algorithm for Smith form depends a lot on the
actual size/shape/structure of the matrix.
Anyway you can try the following "./smith adaptive 600 600
/tmp/ch5-5.b3.sms sparse"
here with my 600x600 matrix in the /tmp/ch5-5.b3.sms file.
on my laptop it takes 35 seconds.
We also have some specific methods for much larger matrices (up to
billions of non-zero entries), with special properties discovered at
runtime (well conditioned or small min poly or ...) but not currently
available in the distribution, and often architecture specific code.
With some more details on the matrix we could provide you with a generic
beta code, or if you can give me some matrices I would be happy to try
to compute their Smith forms on some large cluster for which we have
developed specialized code.
Best,

--
Jean-Guillaume Dumas.
____________________________________________________________________
Jean-Guill...@imag.fr Tél.: +33 476 514 866
Université Joseph Fourier, Grenoble I. Fax.: +33 476 631 263
Laboratoire Jean Kuntzmann, Mathématiques Appliquées et Informatique
51, avenue des Mathématiques. LJK/IMAG - BP53. 38041 Grenoble FRANCE
http://ljk.imag.fr/membres/Jean-Guillaume.Dumas
____________________________________________________________________

[oliver]

Hello,

I wasn't able to find that exact matrix, but I tried some of the
sparse matrices that were included in linbox and the program seemed to
run ok. My matrix is 9873 x 9621360, but it is nearly completely 0s
except for a few 1s and -1s. I uploaded it to:

http://www.math.utk.edu/~oliver/oliver.matrix

I tried running the smith program on it with parameters corresponding
to the ones you just mentioned but I got a bad_alloc error, which I
assume means the smith program is trying to store it in dense form.
I'd greatly appreciate it if you could tell me the Smith form of it,
and give me the code to compute it if possible.

Thanks!

Oliver

On Aug 18, 3:49 am, Jean-Guillaume Dumas <Jean-

> Jean-Guillaume.Du...@imag.fr                   Tél.: +33 476 514 866

[Jean-Guillaume Dumas]

oliver a écrit :
> Hello,
>

> I wasn't able to find that exact matrix, but I tried some of the
> sparse matrices that were included in linbox and the program seemed to
> run ok. My matrix is 9873 x 9621360, but it is nearly completely 0s
> except for a few 1s and -1s. I uploaded it to:
>
> http://www.math.utk.edu/~oliver/oliver.matrix
>
> I tried running the smith program on it with parameters corresponding
> to the ones you just mentioned but I got a bad_alloc error, which I
> assume means the smith program is trying to store it in dense form.
> I'd greatly appreciate it if you could tell me the Smith form of it,
> and give me the code to compute it if possible.
>
> Thanks!
>
> Oliver
>

Dear Oliver, I used the Vlaence algorithm to compute the Smith form:
first compute the valence (last non zero coefficient of the integer
minimal polynomial of A \times A^T) with the valence example in linbox
it gives after about an hour on my laptop:
V=-9607284045760261311733845921584686200111841745128900976912773427689099698114131496757682589859604510385160522606536197255410087594868642637108486780447081361408
of which I could factor out 2^12, 443, 664537 and a composite number
with large factors:
C=7967421447513083242420239820495012443631021669683829564876584281623342514790684116767467742429859819535216583624083668970342135208426627687175964053

All the non 1 coefficients of the Smith form must divide the Valence.

Thus the number of non-zero coefficients in the integer Smith form is
the rank modulo any prime not dividing the valence,
"sparseelimrank" in the example directory gives me 9777 modulo 3.
Then the rank modulo 2, 443, 664537 gives me 9777 also
and the a slight modification of "sparseelimrank" to work with an
arbitrary precision modular field "GivaroZpz<Integer>" instead of
"Modular<double>" gives me 9777 mod C also.

The computation of one of these five ranks lasted between 1.2 and 8.5
seconds on my laptop.
Then the intger Smith form of your matrix consists of only 9777 ones.
Best regards,

--
Jean-Guillaume Dumas.
____________________________________________________________________
Jean-Guill...@imag.fr Tél.: +33 476 514 866

[oliver]

Thanks!

That was exactly what I was expecting it to be. In case you're
wondering what the matrix is, its a "smooshed" boundary matrix from a
simplicial complex.

Oliver

On Aug 19, 7:18 am, Jean-Guillaume Dumas <Jean-

> Jean-Guillaume.Du...@imag.fr                   Tél.: +33 476 514 866