Re: relative saturation?

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Daniel Allcock [2012-09-15 01:55]:
> I have a basis for a saturated subgroup L of Z^n

Just to be sure: I guess that by "saturated subgroup L", you mean that 

  (L \otimes_Z Q) \cap Z^n = L

and "saturation of M" means (M \otimes_Z Q) \cap Z^n ? 
[ given by matrixqz(.,-2) in GP terms ]

>, and one extra vector V in Z^n but not in L.  I'd like to find an element of Z^n which together with L generates the saturation of the span of L and V.  I think of this as the "saturation of <L,V> relative to L".
> 
> I can't find any ready-made function that lends itself to an easy
> implementation of this.  The best I can think of right now is to find
> a basis for the saturation of <L,V>, express it in terms of V and my
> basis for L, look at the V-components, and follow Euclid's algorithm
> to find a Z-linear comb whose V-component is smallest possible.

This looks good. Presumably all the time will be spent computing the
saturation of <L,V> (which I don't see how to avoid).

> This looks icky and I am probably missing something more obvious.  

Why icky ?

> I'd appreciate any tips.  (I'm using library mode, so hacks using it
> are welcome too).

What's the order of magnitude of n ? matrixqz() will probably break
around n = 50 or so.

The only trick I can think of right now is to perform the saturation of
L and <L,V> at the same time (if L was not originally satured, and you
needed to reduce to this case first); requires adapting code from
alglin2.c:QM_imZ_hnf_aux(). Not pretty.

Cheers,

    K.B.
-- 
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`