Karim Belabas on Sat, 15 Sep 2012 12:20:19 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: relative saturation? |
* 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] `