Karim BELABAS on Thu, 29 May 2003 23:06:41 +0200 (MEST)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: matsnf segfaults


On Thu, 29 May 2003, Karim BELABAS wrote:

> On Thu, 29 May 2003, Alexander Shumakovitch wrote:
> > I've just got bitten by a nasty bug in matsnf. If one tries to apply it
> > to the matrix attached, one gets:
> >   (15:02) gp > m = read("crash_snf");
> >   time = 10 ms.
> >   (15:02) gp > matsnf(m)
> >     ***   bug in GP (Segmentation Fault), please report
> >   (15:03) gp >
> >
> > This happens on 2.4.1, 2.2.5 and CVS versions.
[...]
> P.S: Note that the algorithm used is spectacularly inefficient in medium to
> large dimensions (it was written to be used for 10 x 10 matrices...), so I
> doubt the computation will ever finish.
>
> Done by hand as a sequence of mathnfmod() and transpositions, it requires
> less than one minute.

[ above timing included typing ]

Having fiddled some more with the routine, I committed another patch to
matsnf to allow arbitrary rectangular matrices [ for integer matrices only ],
as a preliminary cleanup for the introduction a modular algorithm.

When the matrix is singular, modular HNF reductions are done to reduce to
that case. This already reduces your example to a trivial form (dealt with
in half a second).

It's quite straightforward to make the resulting algorithm modular
[ provided one doesn't ask for transformation matrices ], but I'd like to
know first whether the above works as expected !

Cheers,

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425   Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://www.parigp-home.de/  [PARI/GP]