1 /* Copyright (C) 2000 The PARI group.
2
3 This file is part of the PARI/GP package.
4
5 PARI/GP is free software; you can redistribute it and/or modify it under the
6 terms of the GNU General Public License as published by the Free Software
7 Foundation; either version 2 of the License, or (at your option) any later
8 version. It is distributed in the hope that it will be useful, but WITHOUT
9 ANY WARRANTY WHATSOEVER.
10
11 Check the License for details. You should have received a copy of it, along
12 with the package; see the file 'COPYING'. If not, write to the Free Software
13 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
14
15 #include "pari.h"
16 #include "paripriv.h"
17 /**************************************************************/
18 /** **/
19 /** HERMITE NORMAL FORM REDUCTION **/
20 /** **/
21 /**************************************************************/
22 static GEN ZV_hnfgcdext(GEN A);
23 static GEN
hnfallgen(GEN x)24 hnfallgen(GEN x)
25 {
26 GEN z = cgetg(3, t_VEC);
27 gel(z,1) = RgM_hnfall(x, (GEN*)(z+2), 1);
28 return z;
29 }
30 GEN
mathnf0(GEN x,long flag)31 mathnf0(GEN x, long flag)
32 {
33 switch(typ(x))
34 {
35 case t_VEC:
36 if (RgV_is_ZV(x))
37 switch (flag)
38 {
39 case 0:
40 if (lg(x) == 1) return cgetg(1, t_MAT);
41 retmkmat(mkcol(ZV_content(x)));
42 case 1:
43 case 4:
44 return ZV_hnfgcdext(x);
45 }
46 x = gtomat(x); break;
47 case t_MAT: break;
48 default: pari_err_TYPE("mathnf0",x);
49 }
50
51 switch(flag)
52 {
53 case 0: case 2: return RgM_is_ZM(x)? ZM_hnf(x): RgM_hnfall(x,NULL,1);
54 case 1: case 3: return RgM_is_ZM(x)? hnfall(x): hnfallgen(x);
55 case 4: RgM_check_ZM(x, "mathnf0"); return hnflll(x);
56 case 5: RgM_check_ZM(x, "mathnf0"); return hnfperm(x);
57 default: pari_err_FLAG("mathnf");
58 }
59 return NULL; /* LCOV_EXCL_LINE */
60 }
61
62 /*******************************************************************/
63 /* */
64 /* SPECIAL HNF (FOR INTERNAL USE !!!) */
65 /* */
66 /*******************************************************************/
67 static int
count(GEN mat,long row,long len,long * firstnonzero)68 count(GEN mat, long row, long len, long *firstnonzero)
69 {
70 long j, n = 0;
71
72 for (j=1; j<=len; j++)
73 {
74 long p = mael(mat,j,row);
75 if (p)
76 {
77 if (labs(p)!=1) return -1;
78 n++; *firstnonzero=j;
79 }
80 }
81 return n;
82 }
83
84 static int
count2(GEN mat,long row,long len)85 count2(GEN mat, long row, long len)
86 {
87 long j;
88 for (j=len; j; j--)
89 if (labs(mael(mat,j,row)) == 1) return j;
90 return 0;
91 }
92
93 static GEN
hnffinal(GEN matgen,GEN perm,GEN * ptdep,GEN * ptB,GEN * ptC)94 hnffinal(GEN matgen,GEN perm,GEN* ptdep,GEN* ptB,GEN* ptC)
95 {
96 GEN p1,p2,U,H,Hnew,Bnew,Cnew,diagH1;
97 GEN B = *ptB, C = *ptC, dep = *ptdep, depnew;
98 pari_sp av;
99 long i,j,k,s,i1,j1,zc;
100 long co = lg(C);
101 long col = lg(matgen)-1;
102 long lnz, nlze, lig;
103
104 if (col == 0) return matgen;
105 lnz = nbrows(matgen); /* was called lnz-1 - nr in hnfspec */
106 nlze = nbrows(dep);
107 lig = nlze + lnz;
108 /* H: lnz x lnz [disregarding initial 0 cols], U: col x col */
109 H = ZM_hnflll(matgen, &U, 0);
110 H += (lg(H)-1 - lnz); H[0] = evaltyp(t_MAT) | evallg(lnz+1);
111 /* Only keep the part above the H (above the 0s is 0 since the dep rows
112 * are dependent from the ones in matgen) */
113 zc = col - lnz; /* # of 0 columns, correspond to units */
114 if (nlze) { dep = ZM_mul(dep,U); dep += zc; }
115
116 diagH1 = new_chunk(lnz+1); /* diagH1[i] = 0 iff H[i,i] != 1 (set later) */
117
118 av = avma;
119 Cnew = cgetg(co, typ(C));
120 setlg(C, col+1); p1 = gmul(C,U);
121 for (j=1; j<=col; j++) gel(Cnew,j) = gel(p1,j);
122 for ( ; j<co ; j++) gel(Cnew,j) = gel(C,j);
123
124 /* Clean up B using new H */
125 for (s=0,i=lnz; i; i--)
126 {
127 GEN Di = gel(dep,i), Hi = gel(H,i);
128 GEN h = gel(Hi,i); /* H[i,i] */
129 if ( (diagH1[i] = is_pm1(h)) ) { h = NULL; s++; }
130 for (j=col+1; j<co; j++)
131 {
132 GEN z = gel(B,j-col);
133 p1 = gel(z,i+nlze);
134 if (h) p1 = truedivii(p1,h);
135 if (!signe(p1)) continue;
136 for (k=1; k<=nlze; k++) gel(z,k) = subii(gel(z,k), mulii(p1, gel(Di,k)));
137 for ( ; k<=lig; k++) gel(z,k) = subii(gel(z,k), mulii(p1, gel(Hi,k-nlze)));
138 gel(Cnew,j) = gsub(gel(Cnew,j), gmul(p1, gel(Cnew,i+zc)));
139 }
140 if (gc_needed(av,2))
141 {
142 if(DEBUGMEM>1) pari_warn(warnmem,"hnffinal, i = %ld",i);
143 gerepileall(av, 2, &Cnew, &B);
144 }
145 }
146 p1 = cgetg(lnz+1,t_VEC); p2 = perm + nlze;
147 for (i1=0, j1=lnz-s, i=1; i<=lnz; i++) /* push the 1 rows down */
148 if (diagH1[i])
149 gel(p1,++j1) = gel(p2,i);
150 else
151 gel(p2,++i1) = gel(p2,i);
152 for (i=i1+1; i<=lnz; i++) gel(p2,i) = gel(p1,i);
153
154 /* s = # extra redundant generators taken from H
155 * zc col-s co zc = col - lnz
156 * [ 0 |dep | ] i = nlze + lnz - s = lig - s
157 * nlze [--------| B' ]
158 * [ 0 | H' | ] H' = H minus the s rows with a 1 on diagonal
159 * i [--------|-----] lig-s (= "1-rows")
160 * [ 0 | Id ]
161 * [ | ] li */
162 lig -= s; col -= s; lnz -= s;
163 Hnew = cgetg(lnz+1,t_MAT);
164 depnew = cgetg(lnz+1,t_MAT); /* only used if nlze > 0 */
165 Bnew = cgetg(co-col,t_MAT);
166 C = shallowcopy(Cnew);
167 for (j=1,i1=j1=0; j<=lnz+s; j++)
168 {
169 GEN z = gel(H,j);
170 if (diagH1[j])
171 { /* hit exactly s times */
172 i1++; C[i1+col] = Cnew[j+zc];
173 p1 = cgetg(lig+1,t_COL); gel(Bnew,i1) = p1;
174 for (i=1; i<=nlze; i++) gel(p1,i) = gcoeff(dep,i,j);
175 p1 += nlze;
176 }
177 else
178 {
179 j1++; C[j1+zc] = Cnew[j+zc];
180 p1 = cgetg(lnz+1,t_COL); gel(Hnew,j1) = p1;
181 depnew[j1] = dep[j];
182 }
183 for (i=k=1; k<=lnz; i++)
184 if (!diagH1[i]) p1[k++] = z[i];
185 }
186 for (j=s+1; j<co-col; j++)
187 {
188 GEN z = gel(B,j-s);
189 p1 = cgetg(lig+1,t_COL); gel(Bnew,j) = p1;
190 for (i=1; i<=nlze; i++) gel(p1,i) = gel(z,i);
191 z += nlze; p1 += nlze;
192 for (i=k=1; k<=lnz; i++)
193 if (!diagH1[i]) gel(p1,k++) = gel(z,i);
194 }
195 *ptdep = depnew;
196 *ptC = C;
197 *ptB = Bnew; return Hnew;
198 }
199
200 /* for debugging */
201 static void
p_mat(GEN mat,GEN perm,long k)202 p_mat(GEN mat, GEN perm, long k)
203 {
204 pari_sp av = avma;
205 perm = vecslice(perm, k+1, lg(perm)-1);
206 err_printf("Permutation: %Ps\n",perm);
207 if (DEBUGLEVEL > 6)
208 err_printf("matgen = %Ps\n", zm_to_ZM( rowpermute(mat, perm) ));
209 set_avma(av);
210 }
211
212 static GEN
col_dup(long l,GEN col)213 col_dup(long l, GEN col)
214 {
215 GEN c = new_chunk(l);
216 memcpy(c,col,l * sizeof(long)); return c;
217 }
218
219 /* permutation giving imagecompl(x') | image(x'), x' = transpose of x */
220 static GEN
ZM_rowrankprofile(GEN x,long * nlze)221 ZM_rowrankprofile(GEN x, long *nlze)
222 {
223 pari_sp av = avma;
224 GEN d, y;
225 long i, j, k, l, r;
226
227 x = shallowtrans(x); l = lg(x);
228 (void)new_chunk(l); /* HACK */
229 d = ZM_pivots(x,&r); set_avma(av);
230 *nlze = r;
231 if (!d) return identity_perm(l-1);
232 y = cgetg(l,t_VECSMALL);
233 for (i = j = 1, k = r+1; i<l; i++)
234 if (d[i]) y[k++] = i; else y[j++] = i;
235 return y;
236 }
237
238 /* HNF reduce a relation matrix (column operations + row permutation)
239 ** Input:
240 ** mat = (li-1) x (co-1) matrix of long
241 ** C = r x (co-1) matrix of GEN
242 ** perm= permutation vector (length li-1), indexing the rows of mat: easier
243 ** to maintain perm than to copy rows. For columns we can do it directly
244 ** using e.g. swap(mat[i], mat[j])
245 ** k0 = integer. The k0 first lines of mat are dense, the others are sparse.
246 ** Output: cf ASCII art in the function body
247 **
248 ** row permutations applied to perm
249 ** column operations applied to C. IN PLACE
250 **/
251 GEN
hnfspec_i(GEN mat0,GEN perm,GEN * ptdep,GEN * ptB,GEN * ptC,long k0)252 hnfspec_i(GEN mat0, GEN perm, GEN* ptdep, GEN* ptB, GEN* ptC, long k0)
253 {
254 pari_sp av;
255 long co, n, s, nlze, lnz, nr, i, j, k, lk0, col, lig, *p;
256 GEN mat;
257 GEN p1, p2, matb, matbnew, vmax, matt, T, extramat, B, C, H, dep, permpro;
258 const long li = lg(perm); /* = lgcols(mat0) */
259 const long CO = lg(mat0);
260
261 n = 0; /* -Wall */
262
263 C = *ptC; co = CO;
264 if (co > 300 && co > 1.5 * li)
265 { /* treat the rest at the end */
266 co = (long)(1.2 * li);
267 setlg(C, co);
268 }
269
270 if (DEBUGLEVEL>5)
271 {
272 err_printf("Entering hnfspec\n");
273 p_mat(mat0,perm,0);
274 }
275 matt = cgetg(co, t_MAT); /* dense part of mat (top) */
276 mat = cgetg(co, t_MAT);
277 for (j = 1; j < co; j++)
278 {
279 GEN matj = col_dup(li, gel(mat0,j));
280 p1 = cgetg(k0+1,t_COL); gel(matt,j) = p1; gel(mat,j) = matj;
281 for (i=1; i<=k0; i++) gel(p1,i) = stoi(matj[perm[i]]);
282 }
283 av = avma;
284
285 i = lig = li-1; col = co-1; lk0 = k0;
286 T = (k0 || (lg(C) > 1 && lgcols(C) > 1))? matid(col): NULL;
287 /* Look for lines with a single nonzero entry, equal to 1 in absolute value */
288 while (i > lk0 && col)
289 switch( count(mat,perm[i],col,&n) )
290 {
291 case 0: /* move zero lines between k0+1 and lk0 */
292 lk0++; lswap(perm[i], perm[lk0]);
293 i = lig; continue;
294
295 case 1: /* move trivial generator between lig+1 and li */
296 lswap(perm[i], perm[lig]);
297 if (T) swap(gel(T,n), gel(T,col));
298 swap(gel(mat,n), gel(mat,col)); p = gel(mat,col);
299 if (p[perm[lig]] < 0) /* = -1 */
300 { /* convert relation -g = 0 to g = 0 */
301 for (i=lk0+1; i<lig; i++) p[perm[i]] = -p[perm[i]];
302 if (T)
303 {
304 p1 = gel(T,col);
305 for (i=1; ; i++) /* T = permuted identity: single nonzero entry */
306 if (signe(gel(p1,i))) { togglesign_safe(&gel(p1,i)); break; }
307 }
308 }
309 lig--; col--; i = lig; continue;
310
311 default: i--;
312 }
313 if (DEBUGLEVEL>5) { err_printf(" after phase1:\n"); p_mat(mat,perm,0); }
314
315 #define absmax(s,z) {long _z; _z = labs(z); if (_z > s) s = _z;}
316 /* Get rid of all lines containing only 0 and +/- 1, keeping track of column
317 * operations in T. Leave the rows 1..lk0 alone [up to k0, coefficient
318 * explosion, between k0+1 and lk0, row is 0] */
319 s = 0;
320 while (lig > lk0 && col && s < (long)(HIGHBIT>>1))
321 {
322 for (i=lig; i>lk0; i--)
323 if (count(mat,perm[i],col,&n) > 0) break;
324 if (i == lk0) break;
325
326 /* only 0, +/- 1 entries, at least 2 of them nonzero */
327 lswap(perm[i], perm[lig]);
328 swap(gel(mat,n), gel(mat,col)); p = gel(mat,col);
329 if (T) swap(gel(T,n), gel(T,col));
330 if (p[perm[lig]] < 0)
331 {
332 for (i=lk0+1; i<=lig; i++) p[perm[i]] = -p[perm[i]];
333 if (T) ZV_togglesign(gel(T,col));
334 }
335 for (j=1; j<col; j++)
336 {
337 GEN matj = gel(mat,j);
338 long t;
339 if (! (t = matj[perm[lig]]) ) continue;
340 if (t == 1) {
341 for (i=lk0+1; i<=lig; i++) absmax(s, matj[perm[i]] -= p[perm[i]]);
342 }
343 else { /* t = -1 */
344 for (i=lk0+1; i<=lig; i++) absmax(s, matj[perm[i]] += p[perm[i]]);
345 }
346 if (T) ZC_lincomb1_inplace(gel(T,j), gel(T,col), stoi(-t));
347 }
348 lig--; col--;
349 if (gc_needed(av,3))
350 {
351 if(DEBUGMEM>1) pari_warn(warnmem,"hnfspec[1]");
352 if (T) T = gerepilecopy(av, T); else set_avma(av);
353 }
354 }
355 /* As above with lines containing a +/- 1 (no other assumption).
356 * Stop when single precision becomes dangerous */
357 vmax = cgetg(co,t_VECSMALL);
358 for (j=1; j<=col; j++)
359 {
360 GEN matj = gel(mat,j);
361 for (s=0, i=lk0+1; i<=lig; i++) absmax(s, matj[i]);
362 vmax[j] = s;
363 }
364 while (lig > lk0 && col)
365 {
366 for (i=lig; i>lk0; i--)
367 if ( (n = count2(mat,perm[i],col)) ) break;
368 if (i == lk0) break;
369
370 lswap(vmax[n], vmax[col]);
371 lswap(perm[i], perm[lig]);
372 swap(gel(mat,n), gel(mat,col)); p = gel(mat,col);
373 if (T) swap(gel(T,n), gel(T,col));
374 if (p[perm[lig]] < 0)
375 {
376 for (i=lk0+1; i<=lig; i++) p[perm[i]] = -p[perm[i]];
377 if (T) ZV_togglesign(gel(T,col));
378 }
379 for (j=1; j<col; j++)
380 {
381 GEN matj = gel(mat,j);
382 long t;
383 if (! (t = matj[perm[lig]]) ) continue;
384 if (vmax[col] && (ulong)labs(t) >= (HIGHBIT-vmax[j]) / vmax[col])
385 goto END2;
386
387 for (s=0, i=lk0+1; i<=lig; i++) absmax(s, matj[perm[i]] -= t*p[perm[i]]);
388 vmax[j] = s;
389 if (T) ZC_lincomb1_inplace(gel(T,j), gel(T,col), stoi(-t));
390 }
391 lig--; col--;
392 if (gc_needed(av,3))
393 {
394 if(DEBUGMEM>1) pari_warn(warnmem,"hnfspec[2]");
395 gerepileall(av, T? 2: 1, &vmax, &T);
396 }
397 }
398
399 END2: /* clean up mat: remove everything to the right of the 1s on diagonal */
400 /* go multiprecision first */
401 matb = cgetg(co,t_MAT); /* bottom part (complement of matt) */
402 for (j=1; j<co; j++)
403 {
404 GEN matj = gel(mat,j);
405 p1 = cgetg(li-k0,t_COL); gel(matb,j) = p1;
406 p1 -= k0;
407 for (i=k0+1; i<li; i++) gel(p1,i) = stoi(matj[perm[i]]);
408 }
409 if (DEBUGLEVEL>5)
410 {
411 err_printf(" after phase2:\n");
412 p_mat(mat,perm,lk0);
413 }
414 for (i=li-2; i>lig; i--)
415 {
416 long h, i0 = i - k0, k = i + co-li;
417 GEN Bk = gel(matb,k);
418 for (j=k+1; j<co; j++)
419 {
420 GEN Bj = gel(matb,j), v = gel(Bj,i0);
421 s = signe(v); if (!s) continue;
422
423 gel(Bj,i0) = gen_0;
424 if (is_pm1(v))
425 {
426 if (s > 0) /* v = 1 */
427 { for (h=1; h<i0; h++) gel(Bj,h) = subii(gel(Bj,h), gel(Bk,h)); }
428 else /* v = -1 */
429 { for (h=1; h<i0; h++) gel(Bj,h) = addii(gel(Bj,h), gel(Bk,h)); }
430 }
431 else {
432 for (h=1; h<i0; h++) gel(Bj,h) = subii(gel(Bj,h), mulii(v,gel(Bk,h)));
433 }
434 if (T) ZC_lincomb1_inplace(gel(T,j), gel(T,k), negi(v));
435 }
436 if (gc_needed(av,2))
437 {
438 if(DEBUGMEM>1) pari_warn(warnmem,"hnfspec[3], i = %ld", i);
439 for (h=1; h<co; h++) setlg(matb[h], i0+1); /* bottom can be forgotten */
440 gerepileall(av, T? 2: 1, &matb, &T);
441 }
442 }
443 for (j=1; j<co; j++) setlg(matb[j], lig-k0+1); /* bottom can be forgotten */
444 gerepileall(av, T? 2: 1, &matb, &T);
445 if (DEBUGLEVEL>5) err_printf(" matb cleaned up (using Id block)\n");
446
447 nlze = lk0 - k0; /* # of 0 rows */
448 lnz = lig-nlze+1; /* 1 + # of nonzero rows (!= 0...0 1 0 ... 0) */
449 if (T) matt = ZM_mul(matt,T); /* update top rows */
450 extramat = cgetg(col+1,t_MAT); /* = new C minus the 0 rows */
451 for (j=1; j<=col; j++)
452 {
453 GEN z = gel(matt,j);
454 GEN t = (gel(matb,j)) + nlze - k0;
455 p2=cgetg(lnz,t_COL); gel(extramat,j) = p2;
456 for (i=1; i<=k0; i++) gel(p2,i) = gel(z,i); /* top k0 rows */
457 for ( ; i<lnz; i++) gel(p2,i) = gel(t,i); /* other nonzero rows */
458 }
459 if (!col) {
460 permpro = identity_perm(lnz);
461 nr = lnz;
462 }
463 else
464 permpro = ZM_rowrankprofile(extramat, &nr);
465 /* lnz = lg(permpro) */
466 if (nlze)
467 { /* put the nlze 0 rows (trivial generators) at the top */
468 p1 = new_chunk(lk0+1);
469 for (i=1; i<=nlze; i++) p1[i] = perm[i + k0];
470 for ( ; i<=lk0; i++) p1[i] = perm[i - nlze];
471 for (i=1; i<=lk0; i++) perm[i] = p1[i];
472 }
473 /* sort other rows according to permpro (nr redundant generators first) */
474 p1 = new_chunk(lnz); p2 = perm + nlze;
475 for (i=1; i<lnz; i++) p1[i] = p2[permpro[i]];
476 for (i=1; i<lnz; i++) p2[i] = p1[i];
477 /* perm indexes the rows of mat
478 * |_0__|__redund__|__dense__|__too big__|_____done______|
479 * 0 nlze lig li
480 * \___nr___/ \___k0__/
481 * \____________lnz ______________/
482 *
483 * col co
484 * [dep | ]
485 * i0 [--------| B ] (i0 = nlze + nr)
486 * [matbnew | ] matbnew has maximal rank = lnz-1 - nr
487 * mat = [--------|-----] lig
488 * [ 0 | Id ]
489 * [ | ] li */
490
491 matbnew = cgetg(col+1,t_MAT); /* dense+toobig, maximal rank. For hnffinal */
492 dep = cgetg(col+1,t_MAT); /* rows dependent from the ones in matbnew */
493 for (j=1; j<=col; j++)
494 {
495 GEN z = gel(extramat,j);
496 p1 = cgetg(nlze+nr+1,t_COL); gel(dep,j) = p1;
497 p2 = cgetg(lnz-nr,t_COL); gel(matbnew,j) = p2;
498 for (i=1; i<=nlze; i++) gel(p1,i) = gen_0;
499 p1 += nlze; for (i=1; i<=nr; i++) p1[i] = z[permpro[i]];
500 p2 -= nr; for ( ; i<lnz; i++) p2[i] = z[permpro[i]];
501 }
502
503 /* redundant generators in terms of the genuine generators
504 * (x_i) = - (g_i) B */
505 B = cgetg(co-col,t_MAT);
506 for (j=col+1; j<co; j++)
507 {
508 GEN y = gel(matt,j);
509 GEN z = gel(matb,j);
510 p1=cgetg(lig+1,t_COL); gel(B,j-col) = p1;
511 for (i=1; i<=nlze; i++) gel(p1,i) = gel(z,i);
512 p1 += nlze; z += nlze-k0;
513 for (k=1; k<lnz; k++)
514 {
515 i = permpro[k];
516 gel(p1,k) = (i <= k0)? gel(y,i): gel(z,i);
517 }
518 }
519 if (T) C = typ(C)==t_MAT? RgM_ZM_mul(C,T): RgV_RgM_mul(C,T);
520 gerepileall(av, 4, &matbnew, &B, &dep, &C);
521 *ptdep = dep;
522 *ptB = B;
523 H = hnffinal(matbnew, perm, ptdep, ptB, &C);
524 if (CO > co)
525 { /* treat the rest, N cols at a time (hnflll slow otherwise) */
526 const long N = 300;
527 long a, L = CO - co, l = minss(L, N); /* L columns to add */
528 GEN CC = *ptC, m0 = mat0;
529 setlg(CC, CO); /* restore */
530 CC += co-1;
531 m0 += co-1;
532 for (a = l;;)
533 {
534 GEN MAT, emb;
535 gerepileall(av, 4, &H,&C,ptB,ptdep);
536 MAT = cgetg(l + 1, t_MAT);
537 emb = cgetg(l + 1, typ(C));
538 for (j = 1 ; j <= l; j++)
539 {
540 gel(MAT,j) = gel(m0,j);
541 emb[j] = CC[j];
542 }
543 H = hnfadd_i(H, perm, ptdep, ptB, &C, MAT, emb);
544 if (a == L) break;
545 CC += l;
546 m0 += l;
547 a += l; if (a > L) { l = L - (a - l); a = L; }
548 }
549 }
550 *ptC = C; return H;
551 }
552
553 GEN
hnfspec(GEN mat,GEN perm,GEN * ptdep,GEN * ptB,GEN * ptC,long k0)554 hnfspec(GEN mat, GEN perm, GEN* ptdep, GEN* ptB, GEN* ptC, long k0)
555 {
556 pari_sp av = avma;
557 GEN H = hnfspec_i(mat, perm, ptdep, ptB, ptC, k0);
558 gerepileall(av, 4, ptC, ptdep, ptB, &H); return H;
559 }
560
561 /* HNF reduce x, apply same transforms to C */
562 GEN
mathnfspec(GEN x,GEN * pperm,GEN * pdep,GEN * pB,GEN * pC)563 mathnfspec(GEN x, GEN *pperm, GEN *pdep, GEN *pB, GEN *pC)
564 {
565 long i, j, k, l, n, ly, lx = lg(x);
566 GEN z, v1, perm;
567 if (lx == 1) return cgetg(1, t_MAT);
568 ly = lgcols(x);
569 *pperm = perm = identity_perm(ly-1);
570 z = cgetg(lx,t_MAT);
571 for (i=1; i<lx; i++)
572 {
573 GEN C = cgetg(ly,t_COL), D = gel(x,i);
574 gel(z,i) = C;
575 for (j=1; j<ly; j++)
576 {
577 GEN d = gel(D,j);
578 if (is_bigint(d)) goto TOOLARGE;
579 C[j] = itos(d);
580 }
581 }
582 /* [ dep | ]
583 * [-----| B ]
584 * [ H | ]
585 * [-----|-----]
586 * [ 0 | Id ] */
587 return hnfspec(z,perm, pdep, pB, pC, 0);
588
589 TOOLARGE:
590 if (lg(*pC) > 1 && lgcols(*pC) > 1)
591 pari_err_IMPL("mathnfspec with large entries");
592 x = ZM_hnf(x); lx = lg(x);
593 v1 = cgetg(ly, t_VECSMALL);
594 n = lx - ly;
595 for (i = k = l = 1; i < ly; i++)
596 if (equali1(gcoeff(x,i,i + n))) v1[l++] = i; else perm[k++] = i;
597 setlg(perm, k);
598 setlg(v1, l);
599 x = rowpermute(x, perm); /* upper part */
600 *pperm = vecsmall_concat(perm, v1);
601 *pB = vecslice(x, k+n, lx-1);
602 setlg(x, k);
603 *pdep = rowslice(x, 1, n);
604 return n? rowslice(x, n+1, k-1): x; /* H */
605 }
606
607 /* add new relations to a matrix treated by hnfspec (extramat / extraC) */
608 GEN
hnfadd_i(GEN H,GEN perm,GEN * ptdep,GEN * ptB,GEN * ptC,GEN extramat,GEN extraC)609 hnfadd_i(GEN H, GEN perm, GEN* ptdep, GEN* ptB, GEN* ptC, /* cf hnfspec */
610 GEN extramat,GEN extraC)
611 {
612 GEN matb, extratop, Cnew, permpro, B = *ptB, C = *ptC, dep = *ptdep;
613 long i, lH, lB, li, lig, co, col, nlze;
614
615 if (lg(extramat) == 1) return H;
616 co = lg(C)-1;
617 lH = lg(H)-1;
618 lB = lg(B)-1;
619 li = lg(perm)-1;
620 lig = li - lB;
621 col = co - lB;
622 nlze = lig - lH;
623
624 /* col co
625 * [ 0 |dep | ]
626 * nlze [--------| B ]
627 * [ 0 | H | ]
628 * [--------|-----] lig
629 * [ 0 | Id ]
630 * [ | ] li */
631 extratop = zm_to_ZM( rowslicepermute(extramat, perm, 1, lig) );
632 if (li != lig)
633 { /* zero out bottom part, using the Id block */
634 GEN A = vecslice(C, col+1, co);
635 GEN c = rowslicepermute(extramat, perm, lig+1, li);
636 extraC = gsub(extraC, typ(A)==t_MAT? RgM_zm_mul(A, c): RgV_zm_mul(A,c));
637 extratop = ZM_sub(extratop, ZM_zm_mul(B, c));
638 }
639
640 extramat = shallowconcat(extratop, vconcat(dep, H));
641 Cnew = shallowconcat(extraC, vecslice(C, col-lH+1, co));
642 if (DEBUGLEVEL>5) err_printf(" 1st phase done\n");
643 permpro = ZM_rowrankprofile(extramat, &nlze);
644 extramat = rowpermute(extramat, permpro);
645 *ptB = rowpermute(B, permpro);
646 permpro = vecsmallpermute(perm, permpro);
647 for (i=1; i<=lig; i++) perm[i] = permpro[i]; /* perm o= permpro */
648
649 *ptdep = rowslice(extramat, 1, nlze);
650 matb = rowslice(extramat, nlze+1, lig);
651 if (DEBUGLEVEL>5) err_printf(" 2nd phase done\n");
652 H = hnffinal(matb,perm,ptdep,ptB,&Cnew);
653 *ptC = shallowconcat(vecslice(C, 1, col-lH), Cnew);
654 return H;
655 }
656
657 GEN
hnfadd(GEN H,GEN perm,GEN * ptdep,GEN * ptB,GEN * ptC,GEN extramat,GEN extraC)658 hnfadd(GEN H, GEN perm, GEN* ptdep, GEN* ptB, GEN* ptC, /* cf hnfspec */
659 GEN extramat,GEN extraC)
660 {
661 pari_sp av = avma;
662 H = hnfadd_i(H, perm, ptdep, ptB, ptC, ZM_to_zm(extramat), extraC);
663 gerepileall(av, 4, ptC, ptdep, ptB, &H); return H;
664 }
665
666 /* zero aj = Aij (!= 0) using ak = Aik (maybe 0), via linear combination of
667 * A[j] and A[k] of determinant 1. If U != NULL, likewise update its columns */
668 static void
ZC_elem(GEN aj,GEN ak,GEN A,GEN U,long j,long k)669 ZC_elem(GEN aj, GEN ak, GEN A, GEN U, long j, long k)
670 {
671 GEN p1,u,v,d;
672
673 if (!signe(ak)) {
674 swap(gel(A,j), gel(A,k));
675 if (U) swap(gel(U,j), gel(U,k));
676 return;
677 }
678 d = bezout(aj,ak,&u,&v);
679 /* frequent special case (u,v) = (1,0) or (0,1) */
680 if (!signe(u))
681 { /* ak | aj */
682 p1 = diviiexact(aj,ak); togglesign(p1);
683 ZC_lincomb1_inplace(gel(A,j), gel(A,k), p1);
684 if (U)
685 ZC_lincomb1_inplace(gel(U,j), gel(U,k), p1);
686 return;
687 }
688 if (!signe(v))
689 { /* aj | ak */
690 p1 = diviiexact(ak,aj); togglesign(p1);
691 ZC_lincomb1_inplace(gel(A,k), gel(A,j), p1);
692 swap(gel(A,j), gel(A,k));
693 if (U) {
694 ZC_lincomb1_inplace(gel(U,k), gel(U,j), p1);
695 swap(gel(U,j), gel(U,k));
696 }
697 return;
698 }
699
700 if (!is_pm1(d)) { aj = diviiexact(aj, d); ak = diviiexact(ak, d); }
701 p1 = gel(A,k); aj = negi(aj); /* NOT togglesign */
702 gel(A,k) = ZC_lincomb(u,v, gel(A,j),p1);
703 gel(A,j) = ZC_lincomb(aj,ak, p1,gel(A,j));
704 if (U)
705 {
706 p1 = gel(U,k);
707 gel(U,k) = ZC_lincomb(u,v, gel(U,j),p1);
708 gel(U,j) = ZC_lincomb(aj,ak, p1,gel(U,j));
709 }
710 }
711
712 INLINE int
is_RgX(GEN a,long v)713 is_RgX(GEN a, long v) { return typ(a) == t_POL && varn(a)==v; }
714 /* set u,v such that au + bv = gcd(a,b), divide a,b by the gcd */
715 static GEN
gbezout_step(GEN * pa,GEN * pb,GEN * pu,GEN * pv,long vx)716 gbezout_step(GEN *pa, GEN *pb, GEN *pu, GEN *pv, long vx)
717 {
718 GEN a = *pa, b = *pb, d;
719 if (gequal0(a))
720 {
721 *pa = gen_0; *pu = gen_0;
722 *pb = gen_1; *pv = gen_1; return b;
723 }
724 a = is_RgX(a,vx)? RgX_renormalize(a): scalarpol(a, vx);
725 b = is_RgX(b,vx)? RgX_renormalize(b): scalarpol(b, vx);
726 d = RgX_extgcd(a,b, pu,pv);
727 if (degpol(d)) { a = RgX_div(a, d); b = RgX_div(b, d); }
728 else if (typ(gel(d,2)) == t_REAL && lg(gel(d,2)) <= 3)
729 #if 1
730 { /* possible accuracy problem */
731 GEN D = RgX_gcd_simple(a,b);
732 if (degpol(D)) {
733 D = RgX_normalize(D);
734 a = RgX_div(a, D);
735 b = RgX_div(b, D);
736 d = RgX_extgcd(a,b, pu,pv); /* retry now */
737 d = RgX_mul(d, D);
738 }
739 }
740 #else
741 { /* less stable */
742 d = RgX_extgcd_simple(a,b, pu,pv);
743 if (degpol(d)) { a = RgX_div(a, d); b = RgX_div(b, d); }
744 }
745 #endif
746 *pa = a;
747 *pb = b; return d;
748 }
749 static GEN
col_mul(GEN x,GEN c)750 col_mul(GEN x, GEN c)
751 {
752 if (typ(x) == t_INT)
753 {
754 long s = signe(x);
755 if (!s) return NULL;
756 if (is_pm1(x)) return (s > 0)? c: RgC_neg(c);
757 }
758 return RgC_Rg_mul(c, x);
759 }
760 static void
do_zero(GEN x)761 do_zero(GEN x)
762 {
763 long i, lx = lg(x);
764 for (i=1; i<lx; i++) gel(x,i) = gen_0;
765 }
766
767 /* (c1, c2) *= [u,-b; v,a] */
768 static void
update(GEN u,GEN v,GEN a,GEN b,GEN * c1,GEN * c2)769 update(GEN u, GEN v, GEN a, GEN b, GEN *c1, GEN *c2)
770 {
771 GEN p1,p2;
772
773 u = col_mul(u,*c1);
774 v = col_mul(v,*c2);
775 if (u) p1 = v? gadd(u,v): u;
776 else p1 = v? v: NULL;
777
778 a = col_mul(a,*c2);
779 b = col_mul(gneg_i(b),*c1);
780 if (a) p2 = b? RgC_add(a,b): a;
781 else p2 = b? b: NULL;
782
783 if (!p1) do_zero(*c1); else *c1 = p1;
784 if (!p2) do_zero(*c2); else *c2 = p2;
785 }
786
787 /* zero aj = Aij (!= 0) using ak = Aik (maybe 0), via linear combination of
788 * A[j] and A[k] of determinant 1. If U != NULL, likewise update its columns */
789 static void
RgC_elem(GEN aj,GEN ak,GEN A,GEN V,long j,long k,long li,long vx)790 RgC_elem(GEN aj, GEN ak, GEN A, GEN V, long j, long k, long li, long vx)
791 {
792 GEN u,v, d = gbezout_step(&aj, &ak, &u, &v, vx);
793 long l;
794 /* (A[,k], A[,j]) *= [v, -aj; u, ak ] */
795 for (l = 1; l < li; l++)
796 {
797 GEN t = gadd(gmul(u,gcoeff(A,l,j)), gmul(v,gcoeff(A,l,k)));
798 gcoeff(A,l,j) = gsub(gmul(ak,gcoeff(A,l,j)), gmul(aj,gcoeff(A,l,k)));
799 gcoeff(A,l,k) = t;
800 }
801 gcoeff(A,li,j) = gen_0;
802 gcoeff(A,li,k) = d;
803 if (V) update(v,u,ak,aj,(GEN*)(V+k),(GEN*)(V+j));
804 }
805
806 /* reduce A[i,j] mod A[i,j0] for j=j0+1... via column operations */
807 static void
ZM_reduce(GEN A,GEN U,long i,long j0)808 ZM_reduce(GEN A, GEN U, long i, long j0)
809 {
810 long j, lA = lg(A);
811 GEN d = gcoeff(A,i,j0);
812 if (signe(d) < 0)
813 {
814 ZV_neg_inplace(gel(A,j0));
815 if (U) ZV_togglesign(gel(U,j0));
816 d = gcoeff(A,i,j0);
817 }
818 for (j=j0+1; j<lA; j++)
819 {
820 GEN q = truedivii(gcoeff(A,i,j), d);
821 if (!signe(q)) continue;
822
823 togglesign(q);
824 ZC_lincomb1_inplace(gel(A,j), gel(A,j0), q);
825 if (U) ZC_lincomb1_inplace(gel(U,j), gel(U,j0), q);
826 }
827 }
828
829 /* normalize T as if it were a t_POL in variable v */
830 static GEN
normalize_as_RgX(GEN T,long v,GEN * pd)831 normalize_as_RgX(GEN T, long v, GEN *pd)
832 {
833 GEN d;
834 if (!is_RgX(T,v)) { *pd = T; return gen_1; }
835 d = leading_coeff(T);
836 while (gequal0(d) || (typ(d) == t_REAL && lg(d) == 3
837 && gexpo(T) - expo(d) > (long)BITS_IN_LONG)) {
838 T = normalizepol_lg(T, lg(T)-1);
839 if (!signe(T)) { *pd = gen_1; return T; }
840 d = leading_coeff(T);
841 }
842 if (degpol(T)) T = RgX_Rg_div(T,d); else { d = gel(T,2); T = gen_1; }
843 *pd = d; return T;
844 }
845 /* reduce A[i,j] mod A[i,j0] for j=j0+1... via column operations */
846 static void
RgM_reduce(GEN A,GEN U,long i,long j0,long vx)847 RgM_reduce(GEN A, GEN U, long i, long j0, long vx)
848 {
849 long j, lA = lg(A);
850 GEN d, T = normalize_as_RgX(gcoeff(A,i,j0), vx, &d);
851 if (U && !gequal1(d)) gel(U,j0) = RgC_Rg_div(gel(U,j0), d);
852 gcoeff(A,i,j0) = T;
853
854 for (j=j0+1; j<lA; j++)
855 {
856 GEN t = gcoeff(A,i,j), q;
857 if (gequal0(t)) continue;
858 if (T == gen_1)
859 q = t;
860 else if (is_RgX(t,vx))
861 q = RgX_div(t, T);
862 else continue;
863
864 if (gequal0(q)) continue;
865 gel(A,j) = RgC_sub(gel(A,j), RgC_Rg_mul(gel(A,j0), q));
866 if (U) gel(U,j) = RgC_sub(gel(U,j), RgC_Rg_mul(gel(U,j0), q));
867 }
868 }
869
870 /* A,B square integral in upper HNF, of the same dimension > 0. Return Au
871 * in Z^n (v in Z^n not computed), such that Au + Bv = [1, 0, ..., 0] */
872 GEN
hnfmerge_get_1(GEN A,GEN B)873 hnfmerge_get_1(GEN A, GEN B)
874 {
875 pari_sp av = avma;
876 long j, k, l = lg(A), lb;
877 GEN b, U = cgetg(l + 1, t_MAT), C = cgetg(l + 1, t_VEC);
878
879 b = gcoeff(B,1,1); lb = lgefint(b);
880 for (j = 1; j < l; j++)
881 {
882 GEN t;
883 long c = j+1;
884 gel(U,j) = col_ei(l-1, j);
885 gel(U,c) = zerocol(l-1); /* dummy */
886 gel(C,j) = vecslice(gel(A,j), 1,j);
887 gel(C,c) = vecslice(gel(B,j), 1,j);
888 for (k = j; k > 0; k--)
889 {
890 t = gcoeff(C,k,c);
891 if (gequal0(t)) continue;
892 setlg(C[c], k+1);
893 ZC_elem(t, gcoeff(C,k,k), C, U, c, k);
894 if (lgefint(gcoeff(C,k,k)) > lb) gel(C,k) = FpC_red(gel(C,k), b);
895 if (j > 4)
896 {
897 GEN u = gel(U,k);
898 long h;
899 for (h=1; h<l; h++)
900 if (lgefint(gel(u,h)) > lb) gel(u,h) = remii(gel(u,h), b);
901 }
902 }
903 if (j == 1)
904 t = gcoeff(C,1,1);
905 else
906 {
907 GEN u;
908 t = bezout(gcoeff(C,1,1), b, &u, NULL); /* >= 0 */
909 if (signe(u) && !equali1(u)) gel(U,1) = ZC_Z_mul(gel(U,1), u);
910 gcoeff(C,1,1) = t;
911 }
912 if (equali1(t)) break;
913 }
914 if (j >= l) return NULL;
915 b = lcmii(gcoeff(A,1,1),b);
916 A = FpC_red(ZM_ZC_mul(A,gel(U,1)), b);
917 return gerepileupto(av, FpC_center(A, b, shifti(b,-1)));
918 }
919
920 /* remove the first r columns */
921 static void
remove_0cols(long r,GEN * pA,GEN * pB,long remove)922 remove_0cols(long r, GEN *pA, GEN *pB, long remove)
923 {
924 GEN A = *pA, B = *pB;
925 long l = lg(A);
926 A += r; A[0] = evaltyp(t_MAT) | evallg(l-r);
927 if (B && remove == 2) { B += r; B[0] = A[0]; }
928 *pA = A; *pB = B;
929 }
930
931 /* Inefficient compared to hnfall. 'remove' = throw away lin.dep columns */
932 static GEN
hnf_i(GEN A,int remove)933 hnf_i(GEN A, int remove)
934 {
935 pari_sp av0 = avma, av;
936 long s, n, m, j, k, li, def, ldef;
937
938 RgM_dimensions(A, &m, &n);
939 if (!n) return cgetg(1,t_MAT);
940 av = avma;
941 A = RgM_shallowcopy(A);
942 def = n; ldef = (m>n)? m-n: 0;
943 for (li=m; li>ldef; li--)
944 {
945 for (j=def-1; j; j--)
946 {
947 GEN a = gcoeff(A,li,j);
948 if (!signe(a)) continue;
949
950 /* zero a = Aij using b = Aik */
951 k = (j==1)? def: j-1;
952 ZC_elem(a,gcoeff(A,li,k), A,NULL, j,k);
953 if (gc_needed(av,1))
954 {
955 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnf[1]. li=%ld",li);
956 A = gerepilecopy(av, A);
957 }
958 }
959 s = signe(gcoeff(A,li,def));
960 if (s)
961 {
962 if (s < 0) ZV_neg_inplace(gel(A,def));
963 ZM_reduce(A, NULL, li,def);
964 def--;
965 }
966 else
967 if (ldef) ldef--;
968 if (gc_needed(av,1))
969 {
970 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnf[2]. li=%ld",li);
971 A = gerepilecopy(av, A);
972 }
973 }
974 /* rank A = n - def */
975 if (remove) { GEN B = NULL; remove_0cols(def, &A, &B, remove); }
976 return gerepileupto(av0, ZM_copy(A));
977 }
978
979 GEN
ZM_hnf(GEN x)980 ZM_hnf(GEN x) { return lg(x) > 8? ZM_hnfall(x, NULL, 1): hnf_i(x, 1); }
981
982 /* u*z[1..k] mod p, in place */
983 static void
FpV_Fp_mul_part_ip(GEN z,GEN u,GEN p,long k)984 FpV_Fp_mul_part_ip(GEN z, GEN u, GEN p, long k)
985 {
986 long i;
987 if (is_pm1(u)) {
988 if (signe(u) > 0) {
989 for (i = 1; i <= k; i++)
990 if (signe(gel(z,i))) gel(z,i) = modii(gel(z,i), p);
991 } else {
992 for (i = 1; i <= k; i++)
993 if (signe(gel(z,i))) gel(z,i) = modii(negi(gel(z,i)), p);
994 }
995 }
996 else {
997 for (i = 1; i <= k; i++)
998 if (signe(gel(z,i))) gel(z,i) = Fp_mul(u,gel(z,i), p);
999 }
1000 }
1001 static void
FpV_red_part_ipvec(GEN z,GEN p,long k)1002 FpV_red_part_ipvec(GEN z, GEN p, long k)
1003 {
1004 long i;
1005 for (i = 1; i <= k; i++) gel(z,i) = modii(gel(z,i), gel(p,i));
1006 }
1007
1008 /* return x * U, in echelon form (mod p^m), where (det(U),p) = 1.
1009 * If early_abort is set, return NULL as soon as one pivot is 0 (mod p^m) */
1010 GEN
ZpM_echelon(GEN x,long early_abort,GEN p,GEN pm)1011 ZpM_echelon(GEN x, long early_abort, GEN p, GEN pm)
1012 {
1013 pari_sp av0 = avma, av;
1014 long m, li, co, i, j, k, def, ldef;
1015
1016 co = lg(x); if (co == 1) return cgetg(1,t_MAT);
1017 li = lgcols(x);
1018 av = avma;
1019 x = RgM_shallowcopy(x);
1020 m = Z_pval(pm, p);
1021
1022 ldef = (li > co)? li - co: 0;
1023 for (def = co-1,i = li-1; i > ldef; i--)
1024 {
1025 long vmin = LONG_MAX, kmin = 0;
1026 GEN umin = gen_0, pvmin, q;
1027 for (k = 1; k <= def; k++)
1028 {
1029 GEN u = gcoeff(x,i,k);
1030 long v;
1031 if (!signe(u)) continue;
1032 v = Z_pvalrem(u, p, &u);
1033 if (v >= m) gcoeff(x,i,k) = gen_0;
1034 else if (v < vmin) {
1035 vmin = v; kmin = k; umin = u;
1036 if (!vmin) break;
1037 }
1038 }
1039 if (!kmin)
1040 {
1041 if (early_abort) return NULL;
1042 gcoeff(x,i,def) = gen_0;
1043 ldef--;
1044 if (ldef < 0) ldef = 0;
1045 continue;
1046 }
1047 if (kmin != def) swap(gel(x,def), gel(x,kmin));
1048 q = vmin? powiu(p, m-vmin): pm;
1049 /* pivot has valuation vmin */
1050 umin = modii(umin, q);
1051 if (!equali1(umin))
1052 FpV_Fp_mul_part_ip(gel(x,def), Fp_inv(umin,q), pm, i-1);
1053 gcoeff(x, i, def) = pvmin = powiu(p, vmin);
1054 for (j = def-1; j; j--)
1055 { /* zero x[i, 1..def-1] using x[i,def] = pvmin */
1056 GEN t, a = gcoeff(x,i,j) = modii(gcoeff(x,i,j), pm);
1057 if (!signe(a)) continue;
1058
1059 t = diviiexact(a, pvmin); togglesign(t);
1060 ZC_lincomb1_inplace(gel(x,j), gel(x,def), t);
1061 if (gc_needed(av,1))
1062 {
1063 if (DEBUGMEM>1) pari_warn(warnmem,"ZpM_echelon. i=%ld",i);
1064 x = gerepilecopy(av, x); pvmin = gcoeff(x,i,def);
1065 }
1066 }
1067 def--;
1068 }
1069 if (co > li)
1070 {
1071 x += co - li;
1072 x[0] = evaltyp(t_MAT) | evallg(li);
1073 }
1074 return gerepilecopy(av0, x);
1075 }
1076 GEN
zlm_echelon(GEN x,long early_abort,ulong p,ulong pm)1077 zlm_echelon(GEN x, long early_abort, ulong p, ulong pm)
1078 {
1079 pari_sp av0 = avma;
1080 long li, co, i, j, k, def, ldef;
1081 ulong m;
1082
1083 co = lg(x); if (co == 1) return cgetg(1,t_MAT);
1084 li = lgcols(x);
1085 x = Flm_copy(x);
1086 m = u_lval(pm, p);
1087
1088 ldef = (li > co)? li - co: 0;
1089 for (def = co-1,i = li-1; i > ldef; i--)
1090 {
1091 long vmin = LONG_MAX, kmin = 0;
1092 ulong umin = 0, pvmin, q;
1093 for (k = 1; k <= def; k++)
1094 {
1095 ulong u = ucoeff(x,i,k);
1096 long v;
1097 if (!u) continue;
1098 v = u_lvalrem(u, p, &u);
1099 if (v >= (long) m) ucoeff(x,i,k) = 0;
1100 else if (v < vmin) {
1101 vmin = v; kmin = k; umin = u;
1102 if (!vmin) break;
1103 }
1104 }
1105 if (!kmin)
1106 {
1107 if (early_abort) return NULL;
1108 ucoeff(x,i,def) = 0;
1109 ldef--;
1110 if (ldef < 0) ldef = 0;
1111 continue;
1112 }
1113 if (kmin != def) swap(gel(x,def), gel(x,kmin));
1114 q = vmin? upowuu(p, m-vmin): pm;
1115 /* pivot has valuation vmin */
1116 umin %= q;
1117 if (umin != 1)
1118 Flv_Fl_mul_part_inplace(gel(x,def), Fl_inv(umin,q), pm, i-1);
1119 ucoeff(x, i, def) = pvmin = upowuu(p, vmin);
1120 for (j = def-1; j; j--)
1121 { /* zero x[i, 1..def-1] using x[i,def] = pvmin */
1122 ulong t, a = ucoeff(x,i,j);
1123 if (!a) continue;
1124
1125 t = Fl_neg(a / pvmin, q);
1126 Flc_lincomb1_inplace(gel(x,j), gel(x,def), t, pm);
1127 }
1128 def--;
1129 }
1130 if (co > li)
1131 {
1132 x += co - li;
1133 x[0] = evaltyp(t_MAT) | evallg(li);
1134 }
1135 return gerepilecopy(av0, x);
1136 }
1137
1138 static int
ZV_allequal(GEN v)1139 ZV_allequal(GEN v)
1140 {
1141 long i, l = lg(v);
1142 if (l > 1)
1143 {
1144 GEN x = gel(v,1);
1145 for (i = 2; i < l; i++) if (!equalii(x,gel(v,i))) return 0;
1146 }
1147 return 1;
1148 }
1149 /* compute optimal D for hnfmod: x upper triangular */
1150 static GEN
optimal_D(GEN x,GEN D)1151 optimal_D(GEN x, GEN D)
1152 {
1153 long i, n = nbrows(x);
1154 GEN C = shallowcopy(D);
1155 gel(C,1) = gcoeff(x,1,1);
1156 for (i = 2; i < n; i++)
1157 {
1158 GEN c = mulii(gel(C,i-1), gcoeff(x,i,i));
1159 if (signe(c) < 0) togglesign(c);
1160 if (cmpii(c, gel(D,i)) >= 0) break;
1161 gel(C,i) = c;
1162 }
1163 return C;
1164 }
1165
1166 /* D = multiple of det x (usually detint(x)) or vector of positive moduli
1167 * (compute hnf(x | D))
1168 * flag & hnf_MODID: reduce mod D * matid [ otherwise as above ].
1169 * flag & hnf_PART: don't reduce once diagonal is known
1170 * flag & hnf_CENTER: centermod HNF (2|x[i,j]| <] x[i,i]) */
1171 GEN
ZM_hnfmodall_i(GEN x,GEN D,long flag)1172 ZM_hnfmodall_i(GEN x, GEN D, long flag)
1173 {
1174 pari_sp av;
1175 const long center = (flag & hnf_CENTER);
1176 long moddiag, modsame, nli, li, co, i, j, k, def, ldef;
1177 GEN u, LDM;
1178
1179 co = lg(x);
1180 if (co == 1)
1181 {
1182 if (typ(D) == t_INT || lg(D) == 1) return cgetg(1,t_MAT);
1183 x = diagonal_shallow(D); /* handle flags properly */
1184 co = lg(x);
1185 }
1186 li = lgcols(x);
1187 if (li == 1)
1188 {
1189 if (typ(D) != t_INT && lg(D) != li) pari_err_DIM("ZM_hnfmod");
1190 return cgetg(1,t_MAT);
1191 }
1192 nli = li - 1;
1193 modsame = typ(D)==t_INT;
1194 if (!modsame)
1195 {
1196 if (lg(D) != li) pari_err_DIM("ZM_hnfmod");
1197 if (ZV_allequal(D)) { modsame = 1; D = gel(D,1); }
1198 }
1199 moddiag = (flag & hnf_MODID) || !modsame;
1200 /* modsame: triangularize mod fixed d*Id;
1201 * moddiag: modulo diagonal matrix, else modulo multiple of determinant */
1202
1203 if (modsame)
1204 {
1205 LDM = const_vecsmall(nli, 2*lgefint(D)-2);
1206 D = const_vec(nli,D);
1207 }
1208 else
1209 {
1210 LDM = cgetg(li, t_VECSMALL);
1211 for (i=1; i<li; i++) LDM[i] = lgefint(gel(D,i));
1212 }
1213 av = avma;
1214 x = RgM_shallowcopy(x);
1215
1216 ldef = 0;
1217 if (li > co)
1218 {
1219 ldef = li - co;
1220 if (!moddiag)
1221 pari_err_DOMAIN("ZM_hnfmod","nb lines",">", strtoGENstr("nb columns"), x);
1222 }
1223 for (def = co-1,i = nli; i > ldef; i--,def--)
1224 {
1225 GEN d = gel(D,i);
1226 long add_N = modsame;
1227 for (j = 1; j < def; j++)
1228 {
1229 GEN p1, p2, b, a = gcoeff(x,i,j) = remii(gcoeff(x,i,j), d);
1230 if (!signe(a)) continue;
1231
1232 k = j+1;
1233 b = gcoeff(x,i,k) = remii(gcoeff(x,i,k), d);
1234 if (!signe(b)) { swap(gel(x,j), gel(x,k)); continue; }
1235 if (add_N)
1236 { /* ensure the moving pivot on row i divides d from now on */
1237 add_N = 0;
1238 if (!equali1(a))
1239 { /* x[j] *= u; after this, a = x[i,j] | d */
1240 GEN u = Fp_invgen(a, d, &a);
1241 long t;
1242 p1 = gel(x,j);
1243 for (t = 1; t < i; t++) gel(p1,t) = mulii(gel(p1,t), u);
1244 FpV_red_part_ipvec(p1, D, i-1);
1245 gel(p1,i) = a;
1246 if (2*lg(a) < lg(b))
1247 { /* reduce x[i,k] mod x[i,j]: helps ZC_elem */
1248 GEN r, q = dvmdii(b, a, &r);
1249 togglesign(q);
1250 ZC_lincomb1_inplace_i(gel(x,k), gel(x,j), q, i-1);
1251 FpV_red_part_ipvec(gel(x,k), D, i-1);
1252 gcoeff(x,i,k) = b = r;
1253 }
1254 }
1255 }
1256 ZC_elem(a,b, x, NULL, j,k);
1257 p1 = gel(x,j);
1258 p2 = gel(x,k);
1259 /* prevent coeffs explosion */
1260 for (k = 1; k < i; k++)
1261 {
1262 if (lgefint(gel(p1,k)) > LDM[k]) gel(p1,k) = remii(gel(p1,k),gel(D,k));
1263 if (lgefint(gel(p2,k)) > LDM[k]) gel(p2,k) = remii(gel(p2,k),gel(D,k));
1264 }
1265 }
1266 if (gc_needed(av,2))
1267 {
1268 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnfmod[1]. i=%ld",i);
1269 x = gerepilecopy(av, x);
1270 }
1271 if (moddiag && !signe(gcoeff(x,i,def)))
1272 { /* missing pivot on line i, insert column */
1273 GEN a = cgetg(co + 1, t_MAT);
1274 for (k = 1; k <= def; k++) gel(a,k) = gel(x,k);
1275 gel(a,k++) = Rg_col_ei(gel(D,i), nli, i);
1276 for ( ; k <= co; k++) gel(a,k) = gel(x,k-1);
1277 ldef--; if (ldef < 0) ldef = 0;
1278 co++; def++; x = a;
1279 }
1280 }
1281 if (co < li)
1282 { /* implies moddiag, add missing diag(D) components */
1283 GEN a = cgetg(li+1, t_MAT);
1284 for (k = 1; k <= li-co; k++) gel(a,k) = Rg_col_ei(gel(D,k), nli, k);
1285 for (i = 1; i < co; i++) gel(a,k-1+i) = gel(x,i);
1286 gel(a,li) = zerocol(nli); x = a;
1287 }
1288 else
1289 {
1290 x += co - li;
1291 x[0] = evaltyp(t_MAT) | evallg(li); /* kill 0 columns */
1292 if (moddiag) x = shallowconcat(x, zerocol(nli));
1293 }
1294 if (moddiag)
1295 { /* x[li]: extra column, an accumulator discarded at the end */
1296 GEN D2;
1297 gcoeff(x,1,1) = gcdii(gcoeff(x,1,1), gel(D,1));
1298 D2 = optimal_D(x,D);
1299 /* add up missing diag(D) components */
1300 for (i = nli; i > 0; i--)
1301 {
1302 gcoeff(x, i, li) = gel(D,i);
1303 for (j = i; j > 0; j--)
1304 {
1305 GEN a = gcoeff(x, j, li);
1306 if (!signe(a)) continue;
1307 ZC_elem(a, gcoeff(x,j,j), x, NULL, li,j);
1308 FpV_red_part_ipvec(gel(x,li), D, j-1);
1309 FpV_red_part_ipvec(gel(x,j), D, j-1);
1310 }
1311 if (gc_needed(av,1))
1312 {
1313 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnfmod[2]. i=%ld", i);
1314 gerepileall(av, 2, &x, &D2);
1315 }
1316 }
1317 D = D2;
1318 }
1319 else
1320 {
1321 GEN b = gel(D,1);
1322 for (i = nli; i > 0; i--)
1323 {
1324 GEN d = bezout(gcoeff(x,i,i),b, &u,NULL);
1325 gcoeff(x,i,i) = d;
1326 FpV_Fp_mul_part_ip(gel(x,i), u, b, i-1);
1327 if (i > 1) b = diviiexact(b,d);
1328 }
1329 D = optimal_D(x,D);
1330 }
1331 x[0] = evaltyp(t_MAT) | evallg(li); /* kill 0 columns / discard accumulator */
1332 if (flag & hnf_PART) return x;
1333
1334 for (i = nli; i > 0; i--)
1335 {
1336 GEN diag = gcoeff(x,i,i);
1337 if (signe(diag) < 0) { gel(x,i) = ZC_neg(gel(x,i)); diag = gcoeff(x,i,i); }
1338 if (i != nli)
1339 for (j = 1; j < i; j++) gcoeff(x,j,i) = remii(gcoeff(x,j,i), gel(D,j));
1340 for (j = i+1; j < li; j++)
1341 {
1342 GEN b = gcoeff(x,i,j) = remii(gcoeff(x,i,j), gel(D,i));
1343 GEN r, q = truedvmdii(b, diag, &r);
1344 /* ensure -diag/2 <= r < diag/2 */
1345 if (center && signe(r) && abscmpii(shifti(r,1),diag) >= 0)
1346 { r = subii(r,diag); q = addiu(q,1); }
1347 if (!signe(q)) continue;
1348 togglesign(q);
1349 ZC_lincomb1_inplace_i(gel(x,j), gel(x,i), q, i-1);
1350 gcoeff(x,i,j) = r;
1351 }
1352 if (gc_needed(av,1))
1353 {
1354 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnfmod[3]. i=%ld", i);
1355 gerepileall(av, 2, &x, &D);
1356 }
1357 }
1358 return x;
1359 }
1360 GEN
ZM_hnfmodall(GEN x,GEN dm,long flag)1361 ZM_hnfmodall(GEN x, GEN dm, long flag)
1362 {
1363 pari_sp av = avma;
1364 return gerepilecopy(av, ZM_hnfmodall_i(x, dm, flag));
1365 }
1366 GEN
ZM_hnfmod(GEN x,GEN d)1367 ZM_hnfmod(GEN x, GEN d) { return ZM_hnfmodall(x,d,0); }
1368 GEN
ZM_hnfmodid(GEN x,GEN d)1369 ZM_hnfmodid(GEN x, GEN d)
1370 { return ZM_hnfmodall(x,d,hnf_MODID); }
1371 /* return the column echelon form of x with 1's as pivots,
1372 * P contains the row indices containing the pivots in increasing order */
1373 static GEN
FpM_echelon(GEN x,GEN * pP,GEN p)1374 FpM_echelon(GEN x, GEN *pP, GEN p)
1375 {
1376 pari_sp av;
1377 long iP, li, co, i, j, k, def, ldef;
1378 GEN P;
1379
1380 co = lg(x); if (co == 1) { *pP = cgetg(1,t_VECSMALL); return cgetg(1,t_MAT); }
1381 li = lgcols(x);
1382 iP = 1;
1383 *pP = P = cgetg(li, t_VECSMALL);
1384 av = avma;
1385 x = FpM_red(x, p);
1386
1387 ldef = (li > co)? li - co: 0;
1388 for (def = co-1,i = li-1; i > ldef; i--)
1389 {
1390 GEN u = NULL;
1391 for (k = def; k; k--)
1392 {
1393 u = gcoeff(x,i,k);
1394 if (signe(u)) break;
1395 }
1396 if (!k)
1397 {
1398 if (--ldef < 0) ldef = 0;
1399 continue;
1400 }
1401 P[iP++] = i;
1402 if (k != def) swap(gel(x,def), gel(x,k));
1403 if (!equali1(u))
1404 FpV_Fp_mul_part_ip(gel(x,def), Fp_inv(u,p), p, i-1);
1405 gcoeff(x, i, def) = gen_1;
1406 for (j = def-1; j; j--)
1407 { /* zero x[i, 1..def-1] using x[i,def] = 1*/
1408 GEN xj = gel(x,j), u = gel(xj,i);
1409 if (!signe(u)) continue;
1410
1411 ZC_lincomb1_inplace(xj, gel(x,def), negi(u));
1412 for (k = 1; k < i; k++) gel(xj,k) = modii(gel(xj,k), p);
1413 }
1414 if (gc_needed(av,2))
1415 {
1416 if (DEBUGMEM>1) pari_warn(warnmem,"FpM_echelon. i=%ld",i);
1417 x = gerepilecopy(av, x);
1418 }
1419 def--;
1420 }
1421 /* rank = iP - 1 */
1422 setlg(P, iP); vecsmall_sort(P);
1423 if (co > iP) x += co - iP;
1424 x[0] = evaltyp(t_MAT) | evallg(iP);
1425 return x;
1426 }
1427 /* given x square of maximal rank with 1 or p on diagonal from hnfmodid
1428 * (=> a column containing p has its other entries at 0 ), return the HNF */
1429 static GEN
FpM_hnfend(pari_sp av,GEN x,GEN p)1430 FpM_hnfend(pari_sp av, GEN x, GEN p)
1431 {
1432 long i, l = lgcols(x);
1433 for (i = l-1; i > 0; i--)
1434 {
1435 GEN diag = gcoeff(x,i,i);
1436 long j;
1437 if (is_pm1(diag))
1438 for (j = i+1; j < l; j++)
1439 {
1440 GEN xj = gel(x,j), b = gel(xj,i);
1441 long k;
1442 if (!signe(b)) continue;
1443 ZC_lincomb1_inplace(xj, gel(x,i), negi(b));
1444 for (k=1; k<i; k++)
1445 if (lgefint(gel(xj,k)) > 3) gel(xj,k) = remii(gel(xj,k), p);
1446 }
1447 else
1448 for (j = i+1; j < l; j++) gcoeff(x,i,j) = modii(gcoeff(x,i,j), p);
1449 if (gc_needed(av,2))
1450 {
1451 if (DEBUGMEM>1) pari_warn(warnmem,"FpM_hnfend. i=%ld",i);
1452 x = gerepilecopy(av, x);
1453 }
1454 }
1455 return x;
1456 }
1457 GEN
ZM_hnfmodprime(GEN x,GEN p)1458 ZM_hnfmodprime(GEN x, GEN p)
1459 {
1460 pari_sp av = avma;
1461 GEN P, y;
1462 long l, lP, i;
1463 if (lg(x) == 1) return cgetg(1, t_MAT);
1464 l = lgcols(x);
1465 x = FpM_echelon(x, &P, p);
1466 lP = lg(P); /* rank = lP-1 */
1467 if (lP == l) { set_avma(av); return matid(l-1); }
1468 y = scalarmat_shallow(p, l-1);
1469 for (i = 1; i < lP; i++) gel(y,P[i]) = gel(x,i);
1470 return gerepilecopy(av, FpM_hnfend(av,y,p));
1471 }
1472
1473 static GEN
allhnfmod(GEN x,GEN dm,int flag)1474 allhnfmod(GEN x, GEN dm, int flag)
1475 {
1476 if (typ(x)!=t_MAT) pari_err_TYPE("allhnfmod",x);
1477 RgM_check_ZM(x, "allhnfmod");
1478 if (isintzero(dm)) return ZM_hnf(x);
1479 return ZM_hnfmodall(x, dm, flag);
1480 }
1481 GEN
hnfmod(GEN x,GEN d)1482 hnfmod(GEN x, GEN d)
1483 {
1484 if (typ(d) != t_INT) pari_err_TYPE("mathnfmod",d);
1485 return allhnfmod(x, d, 0);
1486 }
1487 GEN
hnfmodid(GEN x,GEN d)1488 hnfmodid(GEN x, GEN d)
1489 {
1490 switch(typ(d))
1491 {
1492 case t_INT: break;
1493 case t_VEC: case t_COL:
1494 if (RgV_is_ZV(d)) break;
1495 default: pari_err_TYPE("mathnfmodid",d);
1496 }
1497 return allhnfmod(x, d, hnf_MODID);
1498 }
1499
1500 /* M a ZM in HNF. Normalize with *centered* residues */
1501 GEN
ZM_hnfcenter(GEN M)1502 ZM_hnfcenter(GEN M)
1503 {
1504 long i, j, k, N = lg(M)-1;
1505 pari_sp av = avma;
1506
1507 for (j=N-1; j>0; j--) /* skip last line */
1508 {
1509 GEN Mj = gel(M,j), a = gel(Mj,j);
1510 for (k = j+1; k <= N; k++)
1511 {
1512 GEN Mk = gel(M,k), q = diviiround(gel(Mk,j), a);
1513 long s = signe(q);
1514 if (!s) continue;
1515 if (is_pm1(q))
1516 {
1517 if (s < 0)
1518 for (i = 1; i <= j; i++) gel(Mk,i) = addii(gel(Mk,i), gel(Mj,i));
1519 else
1520 for (i = 1; i <= j; i++) gel(Mk,i) = subii(gel(Mk,i), gel(Mj,i));
1521 }
1522 else
1523 for (i = 1; i <= j; i++) gel(Mk,i) = subii(gel(Mk,i), mulii(q,gel(Mj,i)));
1524 if (gc_needed(av,1))
1525 {
1526 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnfcenter, j = %ld",j);
1527 M = gerepilecopy(av, M);
1528 }
1529 }
1530 }
1531 return M;
1532 }
1533
1534 /***********************************************************************/
1535 /* */
1536 /* HNFLLL (Havas, Majewski, Mathews) */
1537 /* */
1538 /***********************************************************************/
1539
1540 static void
Minus(long j,GEN lambda)1541 Minus(long j, GEN lambda)
1542 {
1543 long k, n = lg(lambda);
1544
1545 for (k=1 ; k<j; k++) togglesign_safe(&gcoeff(lambda,k,j));
1546 for (k=j+1; k<n; k++) togglesign_safe(&gcoeff(lambda,j,k));
1547 }
1548
1549 /* index of first nonzero entry */
1550 static long
findi(GEN M)1551 findi(GEN M)
1552 {
1553 long i, n = lg(M);
1554 for (i=1; i<n; i++)
1555 if (signe(gel(M,i))) return i;
1556 return 0;
1557 }
1558
1559 static long
findi_normalize(GEN Aj,GEN B,long j,GEN lambda)1560 findi_normalize(GEN Aj, GEN B, long j, GEN lambda)
1561 {
1562 long r = findi(Aj);
1563 if (r && signe(gel(Aj,r)) < 0)
1564 {
1565 ZV_togglesign(Aj); if (B) ZV_togglesign(gel(B,j));
1566 Minus(j,lambda);
1567 }
1568 return r;
1569 }
1570
1571 static void
reduce2(GEN A,GEN B,long k,long j,long * row0,long * row1,GEN lambda,GEN D)1572 reduce2(GEN A, GEN B, long k, long j, long *row0, long *row1, GEN lambda, GEN D)
1573 {
1574 GEN q;
1575 long i;
1576
1577 *row0 = findi_normalize(gel(A,j), B,j,lambda);
1578 *row1 = findi_normalize(gel(A,k), B,k,lambda);
1579 if (*row0)
1580 q = truedivii(gcoeff(A,*row0,k), gcoeff(A,*row0,j));
1581 else if (abscmpii(shifti(gcoeff(lambda,j,k), 1), gel(D,j)) > 0)
1582 q = diviiround(gcoeff(lambda,j,k), gel(D,j));
1583 else
1584 return;
1585
1586 if (signe(q))
1587 {
1588 GEN Lk = gel(lambda,k), Lj = gel(lambda,j);
1589 togglesign_safe(&q);
1590 if (*row0) ZC_lincomb1_inplace(gel(A,k),gel(A,j),q);
1591 if (B) ZC_lincomb1_inplace(gel(B,k),gel(B,j),q);
1592 gel(Lk,j) = addmulii(gel(Lk,j), q, gel(D,j));
1593 if (is_pm1(q))
1594 {
1595 if (signe(q) > 0)
1596 {
1597 for (i=1; i<j; i++)
1598 if (signe(gel(Lj,i))) gel(Lk,i) = addii(gel(Lk,i), gel(Lj,i));
1599 }
1600 else
1601 {
1602 for (i=1; i<j; i++)
1603 if (signe(gel(Lj,i))) gel(Lk,i) = subii(gel(Lk,i), gel(Lj,i));
1604 }
1605 }
1606 else
1607 {
1608 for (i=1; i<j; i++)
1609 if (signe(gel(Lj,i))) gel(Lk,i) = addmulii(gel(Lk,i), q, gel(Lj,i));
1610 }
1611 }
1612 }
1613
1614 static void
hnfswap(GEN A,GEN B,long k,GEN lambda,GEN D)1615 hnfswap(GEN A, GEN B, long k, GEN lambda, GEN D)
1616 {
1617 GEN t, p1, p2, Lk = gel(lambda,k);
1618 long i,j,n = lg(A);
1619
1620 swap(gel(A,k), gel(A,k-1));
1621 if (B) swap(gel(B,k), gel(B,k-1));
1622 for (j=k-2; j; j--) swap(gcoeff(lambda,j,k-1), gel(Lk,j));
1623 for (i=k+1; i<n; i++)
1624 {
1625 GEN Li = gel(lambda,i);
1626 p1 = mulii(gel(Li,k-1), gel(D,k));
1627 p2 = mulii(gel(Li,k), gel(Lk,k-1));
1628 t = subii(p1,p2);
1629
1630 p1 = mulii(gel(Li,k), gel(D,k-2));
1631 p2 = mulii(gel(Li,k-1), gel(Lk,k-1));
1632 gel(Li,k-1) = diviiexact(addii(p1,p2), gel(D,k-1));
1633 gel(Li,k) = diviiexact(t, gel(D,k-1));
1634 }
1635 p1 = mulii(gel(D,k-2), gel(D,k));
1636 p2 = sqri(gel(Lk,k-1));
1637 gel(D,k-1) = diviiexact(addii(p1,p2), gel(D,k-1));
1638 }
1639
1640 /* reverse row order in matrix A, IN PLACE */
1641 static GEN
reverse_rows(GEN A)1642 reverse_rows(GEN A)
1643 {
1644 long i, j, h, n = lg(A);
1645 if (n == 1) return A;
1646 h = lgcols(A);
1647 for (j=1; j<n; j++)
1648 {
1649 GEN c = gel(A,j);
1650 /* start at (h-1) >>1 : if h = 2i even, no need to swap c[i] and itself */
1651 for (i=(h-1)>>1; i; i--) swap(gel(c,i), gel(c,h-i));
1652 }
1653 return A;
1654 }
1655 /* decide whether to swap */
1656 static int
must_swap(long k,GEN lambda,GEN D)1657 must_swap(long k, GEN lambda, GEN D)
1658 {
1659 pari_sp av = avma;
1660 GEN z = addii(mulii(gel(D,k-2),gel(D,k)), sqri(gcoeff(lambda,k-1,k)));
1661 return gc_bool(av, cmpii(z, sqri(gel(D,k-1))) < 0);
1662 }
1663
1664 GEN
ZM_hnflll(GEN A,GEN * ptB,int remove)1665 ZM_hnflll(GEN A, GEN *ptB, int remove)
1666 {
1667 pari_sp av = avma;
1668 long n, k, kmax;
1669 GEN B, lambda, D;
1670
1671 n = lg(A);
1672 A = reverse_rows(ZM_copy(A)); /* ZM_copy for in place findi_normalize() */
1673 B = ptB? matid(n-1): NULL;
1674 D = const_vec(n, gen_1) + 1;
1675 lambda = zeromatcopy(n-1,n-1);
1676 k = kmax = 2;
1677 while (k < n)
1678 {
1679 long row0, row1;
1680 int do_swap;
1681 reduce2(A,B,k,k-1,&row0,&row1,lambda,D);
1682 if (row0) do_swap = (!row1 || row0 <= row1);
1683 else if (row1) do_swap = 0;
1684 else do_swap = must_swap(k,lambda,D);
1685 if (do_swap)
1686 {
1687 hnfswap(A,B,k,lambda,D);
1688 if (k > 2) k--;
1689 }
1690 else
1691 {
1692 long i;
1693 for (i=k-2; i; i--)
1694 {
1695 long row0, row1;
1696 reduce2(A,B,k,i,&row0,&row1,lambda,D);
1697 }
1698 if (++k > kmax) kmax = k;
1699 }
1700 if (gc_needed(av,3))
1701 {
1702 GEN b = D-1;
1703 if (DEBUGMEM>1) pari_warn(warnmem,"hnflll, kmax = %ld / %ld",kmax,n-1);
1704 gerepileall(av, B? 4: 3, &A, &lambda, &b, &B);
1705 if (gc_needed(av,1)) paristack_resize(0); /* avoid desperation GC */
1706 D = b+1;
1707 }
1708 }
1709 /* handle trivial case: return negative diag coefficient otherwise */
1710 if (n == 2) (void)findi_normalize(gel(A,1), B,1,lambda);
1711 A = reverse_rows(A);
1712 if (remove)
1713 {
1714 long i;
1715 for (i = 1; i < n; i++)
1716 if (!ZV_equal0(gel(A,i))) break;
1717 remove_0cols(i-1, &A, &B, remove);
1718 }
1719 gerepileall(av, B? 2: 1, &A, &B);
1720 if (B) *ptB = B;
1721 return A;
1722 }
1723
1724 GEN
hnflll(GEN x)1725 hnflll(GEN x)
1726 {
1727 GEN z = cgetg(3, t_VEC);
1728 gel(z,1) = ZM_hnflll(x, &gel(z,2), 1);
1729 return z;
1730 }
1731
1732 /* Variation on HNFLLL: Extended GCD */
1733
1734 static void
reduce1(GEN A,GEN B,long k,long j,GEN lambda,GEN D)1735 reduce1(GEN A, GEN B, long k, long j, GEN lambda, GEN D)
1736 {
1737 GEN q;
1738 long i;
1739
1740 if (signe(gel(A,j)))
1741 q = diviiround(gel(A,k),gel(A,j));
1742 else if (abscmpii(shifti(gcoeff(lambda,j,k), 1), gel(D,j)) > 0)
1743 q = diviiround(gcoeff(lambda,j,k), gel(D,j));
1744 else
1745 return;
1746
1747 if (signe(q))
1748 {
1749 GEN Lk = gel(lambda,k), Lj = gel(lambda,j);
1750 togglesign_safe(&q);
1751 gel(A,k) = addmulii(gel(A,k), q, gel(A,j));
1752 ZC_lincomb1_inplace(gel(B,k),gel(B,j),q);
1753 gel(Lk,j) = addmulii(gel(Lk,j), q, gel(D,j));
1754 for (i=1; i<j; i++)
1755 if (signe(gel(Lj,i))) gel(Lk,i) = addmulii(gel(Lk,i), q, gel(Lj,i));
1756 }
1757 }
1758
1759 static GEN
ZV_gcdext_i(GEN A)1760 ZV_gcdext_i(GEN A)
1761 {
1762 long k, n = lg(A);
1763 GEN B, lambda, D;
1764
1765 if (n == 1) retmkvec2(gen_1, cgetg(1,t_MAT));
1766 A = leafcopy(A);
1767 B = matid(n-1);
1768 lambda = zeromatcopy(n-1,n-1);
1769 D = const_vec(n, gen_1) + 1;
1770 k = 2;
1771 while (k < n)
1772 {
1773 int do_swap;
1774
1775 reduce1(A,B,k,k-1,lambda,D);
1776 if (signe(gel(A,k-1))) do_swap = 1;
1777 else if (signe(gel(A,k))) do_swap = 0;
1778 else do_swap = must_swap(k,lambda,D);
1779 if (do_swap)
1780 {
1781 hnfswap(A,B,k,lambda,D);
1782 if (k > 2) k--;
1783 }
1784 else
1785 {
1786 long i;
1787 for (i=k-2; i; i--) reduce1(A,B,k,i,lambda,D);
1788 k++;
1789 }
1790 }
1791 if (signe(gel(A,n-1)) < 0)
1792 {
1793 gel(A,n-1) = negi(gel(A,n-1));
1794 ZV_togglesign(gel(B,n-1));
1795 }
1796 return mkvec2(gel(A,n-1), B);
1797 }
1798 GEN
ZV_extgcd(GEN A)1799 ZV_extgcd(GEN A)
1800 {
1801 pari_sp av = avma;
1802 return gerepilecopy(av, ZV_gcdext_i(A));
1803 }
1804 /* as ZV_extgcd, transforming the gcd into a t_MAT, for mathnf0 */
1805 static GEN
ZV_hnfgcdext(GEN A)1806 ZV_hnfgcdext(GEN A)
1807 {
1808 pari_sp av = avma;
1809 GEN z;
1810 if (lg(A) == 1) retmkvec2(cgetg(1,t_MAT),cgetg(1,t_MAT));
1811 z = ZV_gcdext_i(A);
1812 gel(z,1) = mkmat(mkcol(gel(z,1)));
1813 return gerepilecopy(av, z);
1814 }
1815
1816 /* HNF with permutation. */
1817 GEN
ZM_hnfperm(GEN A,GEN * ptU,GEN * ptperm)1818 ZM_hnfperm(GEN A, GEN *ptU, GEN *ptperm)
1819 {
1820 GEN U, c, l, perm, d, p, q, b;
1821 pari_sp av = avma, av1;
1822 long r, t, i, j, j1, k, m, n;
1823
1824 n = lg(A)-1;
1825 if (!n)
1826 {
1827 if (ptU) *ptU = cgetg(1,t_MAT);
1828 if (ptperm) *ptperm = cgetg(1,t_VEC);
1829 return cgetg(1, t_MAT);
1830 }
1831 m = nbrows(A);
1832 c = zero_zv(m);
1833 l = zero_zv(n);
1834 perm = cgetg(m+1, t_VECSMALL);
1835 av1 = avma;
1836 A = RgM_shallowcopy(A);
1837 U = ptU? matid(n): NULL;
1838 /* U base change matrix : A0*U = A all along */
1839 for (r=0, k=1; k <= n; k++)
1840 {
1841 for (j=1; j<k; j++)
1842 {
1843 if (!l[j]) continue;
1844 t=l[j]; b=gcoeff(A,t,k);
1845 if (!signe(b)) continue;
1846
1847 ZC_elem(b,gcoeff(A,t,j), A,U,k,j);
1848 d = gcoeff(A,t,j);
1849 if (signe(d) < 0)
1850 {
1851 ZV_neg_inplace(gel(A,j));
1852 if (U) ZV_togglesign(gel(U,j));
1853 d = gcoeff(A,t,j);
1854 }
1855 for (j1=1; j1<j; j1++)
1856 {
1857 if (!l[j1]) continue;
1858 q = truedivii(gcoeff(A,t,j1),d);
1859 if (!signe(q)) continue;
1860
1861 togglesign(q);
1862 ZC_lincomb1_inplace(gel(A,j1), gel(A,j), q);
1863 if (U) ZC_lincomb1_inplace(gel(U,j1), gel(U,j), q);
1864 }
1865 }
1866 t = m; while (t && (c[t] || !signe(gcoeff(A,t,k)))) t--;
1867 if (t)
1868 {
1869 p = gcoeff(A,t,k);
1870 for (i=t-1; i; i--)
1871 {
1872 q = gcoeff(A,i,k);
1873 if (signe(q) && abscmpii(p,q) > 0) { p = q; t = i; }
1874 }
1875 perm[++r] = l[k] = t; c[t] = k;
1876 if (signe(p) < 0)
1877 {
1878 ZV_neg_inplace(gel(A,k));
1879 if (U) ZV_togglesign(gel(U,k));
1880 p = gcoeff(A,t,k);
1881 }
1882 /* p > 0 */
1883 for (j=1; j<k; j++)
1884 {
1885 if (!l[j]) continue;
1886 q = truedivii(gcoeff(A,t,j),p);
1887 if (!signe(q)) continue;
1888
1889 togglesign(q);
1890 ZC_lincomb1_inplace(gel(A,j), gel(A,k), q);
1891 if (U) ZC_lincomb1_inplace(gel(U,j), gel(U,k), q);
1892 }
1893 }
1894 if (gc_needed(av1,1))
1895 {
1896 if (DEBUGMEM>1) pari_warn(warnmem,"hnfperm, k=%ld",k);
1897 gerepileall(av1, U? 2: 1, &A, &U);
1898 }
1899 }
1900 if (r < m)
1901 {
1902 for (i=1,k=r; i<=m; i++)
1903 if (!c[i]) perm[++k] = i;
1904 }
1905
1906 /* We have A0*U=A, U in Gl(n,Z)
1907 * basis for Im(A): columns of A s.t l[j]>0 (r cols)
1908 * basis for Ker(A): columns of U s.t l[j]=0 (n-r cols) */
1909 p = cgetg(r+1,t_MAT);
1910 for (i=1; i<=m/2; i++) lswap(perm[i], perm[m+1-i]);
1911 if (U)
1912 {
1913 GEN u = cgetg(n+1,t_MAT);
1914 for (t=1,k=r,j=1; j<=n; j++)
1915 if (l[j])
1916 {
1917 u[k + n-r] = U[j];
1918 gel(p,k--) = vecpermute(gel(A,j), perm);
1919 }
1920 else
1921 u[t++] = U[j];
1922 *ptU = u;
1923 if (ptperm) *ptperm = perm;
1924 gerepileall(av, ptperm? 3: 2, &p, ptU, ptperm);
1925 }
1926 else
1927 {
1928 for (k=r,j=1; j<=n; j++)
1929 if (l[j]) gel(p,k--) = vecpermute(gel(A,j), perm);
1930 if (ptperm) *ptperm = perm;
1931 gerepileall(av, ptperm? 2: 1, &p, ptperm);
1932 }
1933 return p;
1934 }
1935
1936 GEN
ZM_hnf_knapsack(GEN x)1937 ZM_hnf_knapsack(GEN x)
1938 {
1939 GEN t, perm, H = ZM_hnfperm(x,NULL,&perm);
1940 long i,j, l = lg(H), h = lgcols(H);
1941 for (i=1; i<h; i++)
1942 {
1943 int fl = 0;
1944 for (j=1; j<l; j++)
1945 {
1946 t = gcoeff(H,i,j);
1947 if (signe(t))
1948 {
1949 if (!is_pm1(t) || fl) return NULL;
1950 fl = 1;
1951 }
1952 }
1953 }
1954 return rowpermute(H, perm_inv(perm));
1955 }
1956
1957 GEN
hnfperm(GEN A)1958 hnfperm(GEN A)
1959 {
1960 GEN y = cgetg(4, t_VEC);
1961 gel(y,1) = ZM_hnfperm(A, &gel(y,2), &gel(y,3));
1962 return y;
1963 }
1964
1965 /* Hermite Normal Form, with base change matrix if ptB != NULL.
1966 * If 'remove' = 1, remove 0 columns (do NOT update *ptB accordingly)
1967 * If 'remove' = 2, remove 0 columns and update *ptB accordingly */
1968 GEN
ZM_hnfall_i(GEN A,GEN * ptB,long remove)1969 ZM_hnfall_i(GEN A, GEN *ptB, long remove)
1970 {
1971 pari_sp av;
1972 long m, n, r, i, j, k, li;
1973 GEN B, c, h, a;
1974
1975 RgM_dimensions(A, &m,&n);
1976 if (!n)
1977 {
1978 if (ptB) *ptB = cgetg(1,t_MAT);
1979 return cgetg(1,t_MAT);
1980 }
1981 c = zero_zv(m);
1982 h = const_vecsmall(n, m);
1983 av = avma;
1984 A = RgM_shallowcopy(A);
1985 B = ptB? matid(n): NULL;
1986 r = n+1;
1987 for (li=m; li; li--)
1988 {
1989 for (j=1; j<r; j++)
1990 {
1991 for (i=h[j]; i>li; i--)
1992 {
1993 a = gcoeff(A,i,j);
1994 k = c[i];
1995 /* zero a = Aij using Aik */
1996 if (signe(a)) ZC_elem(a,gcoeff(A,i,k), A,B,j,k);
1997 ZM_reduce(A,B, i,k); /* ensure reduced entries even if a = 0 */
1998 }
1999 if (gc_needed(av,1) && (j & 0x7f) == 0)
2000 {
2001 if (DEBUGMEM>1)
2002 pari_warn(warnmem,"ZM_hnfall[1], li = %ld, j = %ld", li, j);
2003 gerepileall(av, B? 2: 1, &A, &B);
2004 }
2005 if (signe( gcoeff(A,li,j) )) break;
2006 h[j] = li-1;
2007 }
2008 if (j == r) continue;
2009 r--;
2010 if (j < r) /* A[j] != 0 */
2011 {
2012 swap(gel(A,j), gel(A,r));
2013 if (B) swap(gel(B,j), gel(B,r));
2014 h[j] = h[r]; h[r] = li; c[li] = r;
2015 }
2016 if (signe(gcoeff(A,li,r)) < 0)
2017 {
2018 ZV_neg_inplace(gel(A,r));
2019 if (B) ZV_togglesign(gel(B,r));
2020 }
2021 ZM_reduce(A,B, li,r);
2022 if (gc_needed(av,1))
2023 {
2024 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnfall[2], li = %ld", li);
2025 gerepileall(av, B? 2: 1, &A, &B);
2026 }
2027 }
2028
2029 if (DEBUGLEVEL>5) err_printf("\nhnfall, final phase: ");
2030 r--; /* first r cols are in the image the n-r (independent) last ones */
2031 for (j=1; j<=r; j++)
2032 {
2033 for (i=h[j]; i; i--)
2034 {
2035 a = gcoeff(A,i,j);
2036 k = c[i];
2037 if (signe(a)) ZC_elem(a,gcoeff(A,i,k), A,B, j,k);
2038 ZM_reduce(A,B, i,k); /* ensure reduced entries, even if a = 0 */
2039 }
2040 if (gc_needed(av,1) && (j & 0x7f) == 0)
2041 {
2042 if (DEBUGMEM>1) pari_warn(warnmem,"ZM_hnfall[3], j = %ld", j);
2043 gerepileall(av, B? 2: 1, &A, &B);
2044 }
2045 }
2046 if (DEBUGLEVEL>5) err_printf("\n");
2047 if (remove) remove_0cols(r, &A, &B, remove);
2048 if (ptB) *ptB = B;
2049 return A;
2050 }
2051 GEN
ZM_hnfall(GEN A,GEN * ptB,long remove)2052 ZM_hnfall(GEN A, GEN *ptB, long remove)
2053 {
2054 pari_sp av = avma;
2055 A = ZM_hnfall_i(A, ptB, remove);
2056 gerepileall(av, ptB? 2: 1, &A, ptB);
2057 return A;
2058 }
2059
2060 GEN
hnfall(GEN x)2061 hnfall(GEN x)
2062 {
2063 GEN z = cgetg(3, t_VEC);
2064 gel(z,1) = ZM_hnfall(x, (GEN*)(z+2), 1);
2065 return z;
2066 }
2067 GEN
hnf(GEN x)2068 hnf(GEN x) { return mathnf0(x,0); }
2069
2070 /* C = A^(-1)t where A and C are integral, A is upper triangular, t t_INT */
2071 GEN
hnf_invscale(GEN A,GEN t)2072 hnf_invscale(GEN A, GEN t)
2073 {
2074 long n = lg(A)-1, i,j,k;
2075 GEN m, c = cgetg(n+1,t_MAT);
2076
2077 if (!n) return c;
2078 for (k=1; k<=n; k++)
2079 { /* cf hnf_divscale with B = id, thus b = e_k */
2080 GEN u = cgetg(n+1, t_COL);
2081 pari_sp av = avma;
2082 gel(c,k) = u;
2083 gel(u,n) = k == n? gerepileuptoint(av, diviiexact(t, gcoeff(A,n,n))): gen_0;
2084 for (i=n-1; i>0; i--)
2085 {
2086 av = avma; m = i == k? t: gen_0;
2087 for (j=i+1; j<=n; j++) m = subii(m, mulii(gcoeff(A,i,j),gel(u,j)));
2088 gel(u,i) = gerepileuptoint(av, diviiexact(m, gcoeff(A,i,i)));
2089 }
2090 }
2091 return c;
2092 }
2093
2094 /* C = A^(-1)(tB) where A, B, C are integral, A is upper triangular, t t_INT */
2095 GEN
hnf_divscale(GEN A,GEN B,GEN t)2096 hnf_divscale(GEN A, GEN B, GEN t)
2097 {
2098 long n = lg(A)-1, i,j,k;
2099 GEN m, c = cgetg(n+1,t_MAT);
2100
2101 if (!n) return c;
2102 for (k=1; k<=n; k++)
2103 {
2104 GEN u = cgetg(n+1, t_COL), b = gel(B,k);
2105 pari_sp av = avma;
2106 gel(c,k) = u; m = mulii(gel(b,n),t);
2107 gel(u,n) = gerepileuptoint(av, diviiexact(m, gcoeff(A,n,n)));
2108 for (i=n-1; i>0; i--)
2109 {
2110 av = avma; m = mulii(gel(b,i),t);
2111 for (j=i+1; j<=n; j++) m = subii(m, mulii(gcoeff(A,i,j),gel(u,j)));
2112 gel(u,i) = gerepileuptoint(av, diviiexact(m, gcoeff(A,i,i)));
2113 }
2114 }
2115 return c;
2116 }
2117
2118 /* A, B integral upper HNF. A^(-1) B integral ? */
2119 int
hnfdivide(GEN A,GEN B)2120 hnfdivide(GEN A, GEN B)
2121 {
2122 pari_sp av = avma;
2123 long n = lg(A)-1, i,j,k;
2124 GEN u, b, m, r;
2125
2126 if (!n) return 1;
2127 if (lg(B)-1 != n) pari_err_DIM("hnfdivide");
2128 u = cgetg(n+1, t_COL);
2129 for (k=1; k<=n; k++)
2130 {
2131 b = gel(B,k);
2132 m = gel(b,k);
2133 gel(u,k) = dvmdii(m, gcoeff(A,k,k), &r);
2134 if (r != gen_0) return gc_long(av, 0);
2135 for (i=k-1; i>0; i--)
2136 {
2137 m = gel(b,i);
2138 for (j=i+1; j<=k; j++) m = subii(m, mulii(gcoeff(A,i,j),gel(u,j)));
2139 m = dvmdii(m, gcoeff(A,i,i), &r);
2140 if (r != gen_0) return gc_long(av, 0);
2141 gel(u,i) = m;
2142 }
2143 }
2144 return gc_long(av, 1);
2145 }
2146
2147 /* A upper HNF, b integral vector. Return A^(-1) b if integral,
2148 * NULL otherwise. Assume #A[,1] = #b. */
2149 GEN
hnf_invimage(GEN A,GEN b)2150 hnf_invimage(GEN A, GEN b)
2151 {
2152 pari_sp av = avma;
2153 long n = lg(A)-1, m, i, k;
2154 GEN u, r;
2155
2156 if (!n) return lg(b)==1? cgetg(1,t_COL):NULL;
2157 m = nbrows(A); /* m >= n */
2158 u = cgetg(n+1, t_COL);
2159 for (i = n, k = m; k > 0; k--)
2160 {
2161 pari_sp av2 = avma;
2162 long j;
2163 GEN t = gel(b,k), Aki = gcoeff(A,k,i);
2164 if (typ(t) != t_INT) pari_err_TYPE("hnf_invimage",t);
2165 for (j=i+1; j<=n; j++) t = subii(t, mulii(gcoeff(A,k,j),gel(u,j)));
2166 if (!signe(Aki))
2167 {
2168 if (signe(t)) return gc_NULL(av);
2169 set_avma(av2); gel(u,i) = gen_0; continue;
2170 }
2171 t = dvmdii(t, Aki, &r);
2172 if (r != gen_0) return gc_NULL(av);
2173 gel(u,i) = gerepileuptoint(av2, t);
2174 if (--i == 0) break;
2175 }
2176 /* If there is a solution, it must be u. Check remaining equations */
2177 for (; k > 0; k--)
2178 {
2179 pari_sp av2 = avma;
2180 long j;
2181 GEN t = gel(b,k);
2182 if (typ(t) != t_INT) pari_err_TYPE("hnf_invimage",t);
2183 for (j=1; j<=n; j++) t = subii(t, mulii(gcoeff(A,k,j),gel(u,j)));
2184 if (signe(t)) return gc_NULL(av);
2185 set_avma(av2);
2186 }
2187 return u;
2188 }
2189
2190 /* A upper HNF, B integral matrix or column. Return A^(-1) B if integral,
2191 * NULL otherwise */
2192 GEN
hnf_solve(GEN A,GEN B)2193 hnf_solve(GEN A, GEN B)
2194 {
2195 pari_sp av;
2196 long i, l;
2197 GEN C;
2198
2199 if (typ(B) == t_COL) return hnf_invimage(A, B);
2200 av = avma; C = cgetg_copy(B, &l);
2201 for (i = 1; i < l; i++)
2202 {
2203 GEN c = hnf_invimage(A, gel(B,i));
2204 if (!c) return gc_NULL(av);
2205 gel(C,i) = c;
2206 }
2207 return C;
2208 }
2209
2210 /***************************************************************/
2211 /** **/
2212 /** SMITH NORMAL FORM REDUCTION **/
2213 /** **/
2214 /***************************************************************/
2215
2216 static GEN
trivsmith(long all)2217 trivsmith(long all)
2218 {
2219 GEN z;
2220 if (!all) return cgetg(1,t_VEC);
2221 z=cgetg(4,t_VEC);
2222 gel(z,1) = cgetg(1,t_MAT);
2223 gel(z,2) = cgetg(1,t_MAT);
2224 gel(z,3) = cgetg(1,t_MAT); return z;
2225 }
2226
2227 static void
snf_pile1(pari_sp av,GEN * x,GEN * U)2228 snf_pile1(pari_sp av, GEN *x, GEN *U)
2229 {
2230 GEN *gptr[2];
2231 int c = 1; gptr[0]=x;
2232 if (*U) gptr[c++] = U;
2233 gerepilemany(av,gptr,c);
2234 }
2235 static void
snf_pile(pari_sp av,GEN * x,GEN * U,GEN * V)2236 snf_pile(pari_sp av, GEN *x, GEN *U, GEN *V)
2237 {
2238 GEN *gptr[3];
2239 int c = 1; gptr[0]=x;
2240 if (*U) gptr[c++] = U;
2241 if (*V) gptr[c++] = V;
2242 gerepilemany(av,gptr,c);
2243 }
2244
2245 static GEN
bezout_step(GEN * pa,GEN * pb,GEN * pu,GEN * pv)2246 bezout_step(GEN *pa, GEN *pb, GEN *pu, GEN *pv)
2247 {
2248 GEN a = *pa, b = *pb, d;
2249 if (absequalii(a,b))
2250 {
2251 long sa = signe(a), sb = signe(b);
2252 *pv = gen_0;
2253 if (sb == sa) {
2254 *pa = *pb = gen_1;
2255 if (sa > 0) {*pu=gen_1; return a;} else {*pu=gen_m1; return absi(a);}
2256 }
2257 if (sa > 0) { *pa = *pu = gen_1; *pb = gen_m1; return a; }
2258 *pa = *pu = gen_m1; *pb = gen_1; return b;
2259 }
2260 d = bezout(a,b, pu,pv);
2261 *pa = diviiexact(a, d);
2262 *pb = diviiexact(b, d); return d;
2263 }
2264
2265 static int
negcmpii(void * E,GEN x,GEN y)2266 negcmpii(void *E, GEN x, GEN y) { (void)E; return -cmpii(x,y); }
2267
2268 /* x square of maximal rank; does b = x[i,i] divide all entries in
2269 * x[1..i-1, 1..i-1] ? If so, return 0; else the index of a problematic row */
2270 static long
ZM_snf_no_divide(GEN x,long i)2271 ZM_snf_no_divide(GEN x, long i)
2272 {
2273 GEN b = gcoeff(x,i,i);
2274 long j, k;
2275
2276 if (is_pm1(b)) return 0;
2277 for (k = 1; k < i; k++)
2278 for (j = 1; j < i; j++)
2279 if (!dvdii(gcoeff(x,k,j),b)) return k;
2280 return 0;
2281 }
2282
2283 static void
ZM_redpart(GEN x,GEN p,long I)2284 ZM_redpart(GEN x, GEN p, long I)
2285 {
2286 long l = lgefint(p), i, j;
2287 for (i = 1; i <= I; i++)
2288 for (j = 1; j <= I; j++)
2289 {
2290 GEN c = gcoeff(x,i,j);
2291 if (lgefint(c) > l) gcoeff(x,i,j) = remii(c, p);
2292 }
2293 }
2294 static void
ZMrow_divexact_inplace(GEN M,long i,GEN c)2295 ZMrow_divexact_inplace(GEN M, long i, GEN c)
2296 {
2297 long j, l = lg(M);
2298 for (j = 1; j < l; j++) gcoeff(M,i,j) = diviiexact(gcoeff(M,i,j), c);
2299 }
2300
2301 /* Return the SNF D of matrix X. If ptU/ptV non-NULL set them to U/V
2302 * to that D = UXV */
2303 GEN
ZM_snfall_i(GEN x,GEN * ptU,GEN * ptV,long flag)2304 ZM_snfall_i(GEN x, GEN *ptU, GEN *ptV, long flag)
2305 {
2306 pari_sp av0 = avma, av;
2307 const long return_vec = flag & 1;
2308 long i, j, k, m0, m, n0, n;
2309 GEN u, v, U, V, V0, mdet, A = NULL, perm = NULL;
2310
2311 n0 = n = lg(x)-1;
2312 if (!n) {
2313 if (ptU) *ptU = cgetg(1,t_MAT);
2314 if (ptV) *ptV = cgetg(1,t_MAT);
2315 return cgetg(1, return_vec? t_VEC: t_MAT);
2316 }
2317 m0 = m = nbrows(x);
2318
2319 U = V = V0 = NULL; /* U = TRANSPOSE of row transform matrix [act on columns]*/
2320 if (m == n && ZM_ishnf(x))
2321 {
2322 mdet = ZM_det_triangular(x); /* != 0 */
2323 if (ptV) *ptV = matid(n);
2324 }
2325 else
2326 {
2327 mdet = ZM_detmult(x);
2328 if (!signe(mdet))
2329 x = ZM_hnfperm(x, ptV, ptU? &perm: NULL);
2330 else
2331 { /* m <= n */
2332 if (!ptV)
2333 x = ZM_hnfmod(x,mdet);
2334 else if (m == n)
2335 {
2336 GEN H = ZM_hnfmod(x,mdet);
2337 *ptV = ZM_gauss(x,H);
2338 x = H;
2339 }
2340 else
2341 x = ZM_hnfperm(x, ptV, ptU? &perm: NULL);
2342 mdet = ZM_det_triangular(x); /* > 0 */
2343 }
2344 n = lg(x)-1; /* n independent columns */
2345 if (ptV)
2346 {
2347 V = *ptV;
2348 if (n != n0)
2349 {
2350 V0 = vecslice(V, 1, n0 - n); /* kernel */
2351 V = vecslice(V, n0-n+1, n0);
2352 }
2353 }
2354 if (!signe(mdet))
2355 {
2356 if (n)
2357 {
2358 x = ZM_snfall_i(shallowtrans(x), ptV, ptU, return_vec); /* swap V,U */
2359 if (!return_vec && n != m) x = shallowtrans(x);
2360 if (ptV) V = ZM_mul(V, shallowtrans(*ptV));
2361 if (ptU) U = *ptU; /* TRANSPOSE */
2362 }
2363 else /* 0 matrix */
2364 {
2365 x = cgetg(1,t_MAT);
2366 if (ptV) V = cgetg(1, t_MAT);
2367 if (ptU) U = matid(m);
2368 }
2369 goto THEEND;
2370 }
2371 }
2372 if (ptV || ptU) U = matid(n); /* we will compute V in terms of U */
2373 if (DEBUGLEVEL>7) err_printf("starting SNF loop");
2374
2375 /* square, maximal rank n */
2376 A = x; x = shallowcopy(x); av = avma;
2377 for (i = n; i > 1; i--)
2378 {
2379 if (DEBUGLEVEL>7) err_printf("\ni = %ld: ",i);
2380 for(;;)
2381 {
2382 int c = 0;
2383 GEN a, b;
2384 for (j = i-1; j >= 1; j--)
2385 {
2386 b = gcoeff(x,i,j); if (!signe(b)) continue;
2387 a = gcoeff(x,i,i);
2388 ZC_elem(b, a, x,NULL, j,i);
2389 if (gc_needed(av,1))
2390 {
2391 if (DEBUGMEM>1) pari_warn(warnmem,"[1]: ZM_snfall i = %ld", i);
2392 snf_pile1(av, &x,&U);
2393 }
2394 }
2395 if (DEBUGLEVEL>7) err_printf("; ");
2396 for (j=i-1; j>=1; j--)
2397 {
2398 GEN d;
2399 b = gcoeff(x,j,i); if (!signe(b)) continue;
2400 a = gcoeff(x,i,i);
2401 d = bezout_step(&a, &b, &u, &v);
2402 for (k = 1; k < i; k++)
2403 {
2404 GEN t = addii(mulii(u,gcoeff(x,i,k)),mulii(v,gcoeff(x,j,k)));
2405 gcoeff(x,j,k) = subii(mulii(a,gcoeff(x,j,k)),
2406 mulii(b,gcoeff(x,i,k)));
2407 gcoeff(x,i,k) = t;
2408 }
2409 gcoeff(x,j,i) = gen_0;
2410 gcoeff(x,i,i) = d;
2411 if (U) update(u,v,a,b,(GEN*)(U+i),(GEN*)(U+j));
2412 if (gc_needed(av,1))
2413 {
2414 if (DEBUGMEM>1) pari_warn(warnmem,"[2]: ZM_snfall, i = %ld", i);
2415 snf_pile1(av, &x,&U);
2416 }
2417 c = 1;
2418 }
2419 if (!c)
2420 {
2421 k = ZM_snf_no_divide(x, i);
2422 if (!k) break;
2423
2424 /* x[k,j] != 0 mod b */
2425 for (j = 1; j <= i; j++)
2426 gcoeff(x,i,j) = addii(gcoeff(x,i,j),gcoeff(x,k,j));
2427 if (U) gel(U,i) = gadd(gel(U,i),gel(U,k));
2428 }
2429 ZM_redpart(x, mdet, i);
2430 if (U && (flag & 2)) ZM_redpart(U, mdet, n);
2431 if (gc_needed(av,1))
2432 {
2433 if (DEBUGMEM>1) pari_warn(warnmem,"[3]: ZM_snfall");
2434 snf_pile1(av, &x,&U);
2435 }
2436 }
2437 }
2438 if (DEBUGLEVEL>7) err_printf("\n");
2439 for (k = n; k; k--)
2440 {
2441 GEN d = gcdii(gcoeff(x,k,k), mdet);
2442 gcoeff(x,k,k) = d;
2443 if (!is_pm1(d)) mdet = diviiexact(mdet,d);
2444 }
2445 THEEND:
2446 if (U) U = shallowtrans(U);
2447 if (ptV && A)
2448 { /* U A V = D => D^(-1) U A = V^(-1) */
2449 long l = lg(x);
2450 GEN W = ZM_mul(U, A);
2451 for (i = 1; i < l; i++)
2452 {
2453 GEN c = gcoeff(x,i,i);
2454 if (is_pm1(c)) break; /* only 1 from now on */
2455 ZMrow_divexact_inplace(W, i, c);
2456 }
2457 if (flag & 2)
2458 {
2459 W = FpM_red(W, gcoeff(x,1,1));
2460 W = matinvmod(W, gcoeff(x,1,1));
2461 }
2462 else
2463 W = ZM_inv(W, NULL);
2464 V = V? ZM_mul(V, W): W;
2465 }
2466 if (return_vec)
2467 {
2468 long l = lg(x)-1;
2469 if (typ(x) == t_MAT) x = RgM_diagonal_shallow(x);
2470 if (m0 > l) x = shallowconcat(zerovec(m0-l), x);
2471 }
2472
2473 if (V0)
2474 { /* add kernel */
2475 if (!return_vec) x = shallowconcat(zeromat(m,n0-n), x);
2476 if (ptV) V = shallowconcat(V0, V);
2477 }
2478 if (perm && U) U = vecpermute(U, perm_inv(perm));
2479 snf_pile(av0, &x,&U,&V);
2480 if (ptU) *ptU = U;
2481 if (ptV) *ptV = V;
2482 return x;
2483 }
2484 GEN
ZM_snfall(GEN x,GEN * U,GEN * V)2485 ZM_snfall(GEN x, GEN *U, GEN *V) { return ZM_snfall_i(x, U, V, 0); }
2486 GEN
ZM_snf(GEN x)2487 ZM_snf(GEN x) { return ZM_snfall_i(x, NULL,NULL, 1); }
2488 GEN
smith(GEN x)2489 smith(GEN x) { return ZM_snfall_i(x, NULL,NULL, 1); }
2490 GEN
smithall(GEN x)2491 smithall(GEN x)
2492 {
2493 GEN z = cgetg(4, t_VEC);
2494 gel(z,3) = ZM_snfall_i(x, (GEN*)(z+1),(GEN*)(z+2), 0);
2495 return z;
2496 }
2497
2498 void
ZM_snfclean(GEN d,GEN u,GEN v)2499 ZM_snfclean(GEN d, GEN u, GEN v)
2500 {
2501 long i, c, l = lg(d);
2502
2503 if (typ(d) == t_VEC)
2504 for (c=1; c<l; c++) { GEN t = gel(d,c); if (is_pm1(t)) break; }
2505 else
2506 {
2507 for (c=1; c<l; c++) { GEN t = gcoeff(d,c,c); if (is_pm1(t)) break; }
2508 if (c < l) for (i = 1; i < c; i++) setlg(gel(d,i), c);
2509 }
2510 setlg(d, c);
2511 if (u) for (i=1; i<l; i++) setlg(gel(u,i), c);
2512 if (v) setlg(v, c);
2513 }
2514
2515 /* Assume z was computed by [g]smithall(). Remove the 1s on the diagonal */
2516 GEN
smithclean(GEN z)2517 smithclean(GEN z)
2518 {
2519 long i, j, h, l, c, d;
2520 GEN U, V, y, D, t;
2521
2522 if (typ(z) != t_VEC) pari_err_TYPE("smithclean",z);
2523 l = lg(z); if (l == 1) return cgetg(1,t_VEC);
2524 U = gel(z,1);
2525 if (l != 4 || typ(U) != t_MAT)
2526 { /* assume z = vector of elementary divisors */
2527 for (c=1; c<l; c++)
2528 if (gequal1(gel(z,c))) break;
2529 return gcopy_lg(z, c);
2530 }
2531 V = gel(z,2);
2532 D = gel(z,3);
2533 l = lg(D);
2534 if (l == 1) return gcopy(z);
2535 h = lgcols(D);
2536 if (h > l)
2537 { /* D = vconcat(zero matrix, diagonal matrix) */
2538 for (c=1+h-l, d=1; c<h; c++,d++)
2539 if (gequal1(gcoeff(D,c,d))) break;
2540 }
2541 else if (h < l)
2542 { /* D = concat(zero matrix, diagonal matrix) */
2543 for (c=1, d=1+l-h; d<l; c++,d++)
2544 if (gequal1(gcoeff(D,c,d))) break;
2545 }
2546 else
2547 { /* D diagonal */
2548 for (c=1; c<l; c++)
2549 if (gequal1(gcoeff(D,c,c))) break;
2550 d = c;
2551 }
2552 /* U was (h-1)x(h-1), V was (l-1)x(l-1), D was (h-1)x(l-1) */
2553 y = cgetg(4,t_VEC);
2554 /* truncate U to (c-1) x (h-1) */
2555 gel(y,1) = t = cgetg(h,t_MAT);
2556 for (j=1; j<h; j++) gel(t,j) = gcopy_lg(gel(U,j), c);
2557 /* truncate V to (l-1) x (d-1) */
2558 gel(y,2) = gcopy_lg(V, d);
2559 gel(y,3) = t = zeromatcopy(c-1, d-1);
2560 /* truncate D to a (c-1) x (d-1) matrix */
2561 if (d > 1)
2562 {
2563 if (h > l)
2564 {
2565 for (i=1+h-l, j=1; i<c; i++,j++)
2566 gcoeff(t,i,j) = gcopy(gcoeff(D,i,j));
2567 }
2568 else if (h < l)
2569 {
2570 for (i=1, j=1+l-h; j<d; i++,j++)
2571 gcoeff(t,i,j) = gcopy(gcoeff(D,i,j));
2572 }
2573 else
2574 {
2575 for (j=1; j<d; j++)
2576 gcoeff(t,j,j) = gcopy(gcoeff(D,j,j));
2577 }
2578 }
2579 return y;
2580 }
2581
2582 /* does b = x[i,i] divide all entries in x[1..i-1,1..i-1] ? If so, return 0;
2583 * else return the index of a problematic row */
2584 static long
gsnf_no_divide(GEN x,long i,long vx)2585 gsnf_no_divide(GEN x, long i, long vx)
2586 {
2587 GEN b = gcoeff(x,i,i);
2588 long j, k;
2589
2590 if (gequal0(b))
2591 {
2592 for (k = 1; k < i; k++)
2593 for (j = 1; j < i; j++)
2594 if (!gequal0(gcoeff(x,k,j))) return k;
2595 return 0;
2596 }
2597
2598 if (!is_RgX(b,vx) || degpol(b)<=0) return 0;
2599 for (k = 1; k < i; k++)
2600 for (j = 1; j < i; j++)
2601 {
2602 GEN z = gcoeff(x,k,j), r;
2603 if (!is_RgX(z,vx)) z = scalarpol(z, vx);
2604 r = RgX_rem(z, b);
2605 if (signe(r) && (! isinexactreal(r) ||
2606 gexpo(r) > 16 + gexpo(b) - prec2nbits(gprecision(r)))
2607 ) return k;
2608 }
2609 return 0;
2610 }
2611
2612 /* Hermite Normal Form, with base change matrix if ptB != NULL.
2613 * If 'remove' = 1, remove 0 columns (do NOT update *ptB accordingly)
2614 * If 'remove' = 2, remove 0 columns and update *ptB accordingly */
2615 GEN
RgM_hnfall(GEN A,GEN * pB,long remove)2616 RgM_hnfall(GEN A, GEN *pB, long remove)
2617 {
2618 pari_sp av;
2619 long li, j, k, m, n, def, ldef;
2620 GEN B;
2621 long vx = gvar(A);
2622
2623 n = lg(A)-1;
2624 if (vx==NO_VARIABLE || !n)
2625 {
2626 RgM_check_ZM(A, "mathnf0");
2627 return ZM_hnfall(A, pB, remove);
2628 }
2629 m = nbrows(A);
2630 av = avma;
2631 A = RgM_shallowcopy(A);
2632 B = pB? matid(n): NULL;
2633 def = n; ldef = (m>n)? m-n: 0;
2634 for (li=m; li>ldef; li--)
2635 {
2636 GEN d, T;
2637 for (j=def-1; j; j--)
2638 {
2639 GEN a = gcoeff(A,li,j);
2640 if (gequal0(a)) continue;
2641
2642 k = (j==1)? def: j-1;
2643 RgC_elem(a,gcoeff(A,li,k), A,B, j,k, li, vx);
2644 }
2645 T = normalize_as_RgX(gcoeff(A,li,def), vx, &d);
2646 if (gequal0(T))
2647 { if (ldef) ldef--; }
2648 else
2649 {
2650 gcoeff(A,li,def) = T;
2651 if (B && !gequal1(d)) gel(B, def) = RgC_Rg_div(gel(B, def), d);
2652 RgM_reduce(A, B, li, def, vx);
2653 def--;
2654 }
2655 if (gc_needed(av,1))
2656 {
2657 if (DEBUGMEM>1) pari_warn(warnmem,"ghnfall");
2658 gerepileall(av, B? 2: 1, &A, &B);
2659 }
2660 }
2661 /* rank A = n - def */
2662 if (remove) remove_0cols(def, &A, &B, remove);
2663 gerepileall(av, B? 2: 1, &A, &B);
2664 if (B) *pB = B;
2665 return A;
2666 }
2667
2668 static GEN
RgXM_snf(GEN x,long all)2669 RgXM_snf(GEN x,long all)
2670 {
2671 pari_sp av;
2672 long i, j, k, n;
2673 GEN z, u, v, U, V;
2674 long vx = gvar(x);
2675 n = lg(x)-1; if (!n) return trivsmith(all);
2676 if (vx==NO_VARIABLE) pari_err_TYPE("RgXM_snf",x);
2677 if (lgcols(x) != n+1) pari_err_DIM("gsmithall");
2678 av = avma;
2679 x = RgM_shallowcopy(x);
2680 if (all) { U = matid(n); V = matid(n); }
2681 for (i=n; i>=2; i--)
2682 {
2683 for(;;)
2684 {
2685 GEN a, b, d;
2686 int c = 0;
2687 for (j=i-1; j>=1; j--)
2688 {
2689 b = gcoeff(x,i,j); if (gequal0(b)) continue;
2690 a = gcoeff(x,i,i);
2691 d = gbezout_step(&b, &a, &v, &u, vx);
2692 for (k = 1; k < i; k++)
2693 {
2694 GEN t = gadd(gmul(u,gcoeff(x,k,i)),gmul(v,gcoeff(x,k,j)));
2695 gcoeff(x,k,j) = gsub(gmul(a,gcoeff(x,k,j)),gmul(b,gcoeff(x,k,i)));
2696 gcoeff(x,k,i) = t;
2697 }
2698 gcoeff(x,i,j) = gen_0;
2699 gcoeff(x,i,i) = d;
2700 if (all) update(u,v,a,b,(GEN*)(V+i),(GEN*)(V+j));
2701 }
2702 for (j=i-1; j>=1; j--)
2703 {
2704 b = gcoeff(x,j,i); if (gequal0(b)) continue;
2705 a = gcoeff(x,i,i);
2706 d = gbezout_step(&b, &a, &v, &u, vx);
2707 for (k = 1; k < i; k++)
2708 {
2709 GEN t = gadd(gmul(u,gcoeff(x,i,k)),gmul(v,gcoeff(x,j,k)));
2710 gcoeff(x,j,k) = gsub(gmul(a,gcoeff(x,j,k)),gmul(b,gcoeff(x,i,k)));
2711 gcoeff(x,i,k) = t;
2712 }
2713 gcoeff(x,j,i) = gen_0;
2714 gcoeff(x,i,i) = d;
2715 if (all) update(u,v,a,b,(GEN*)(U+i),(GEN*)(U+j));
2716 c = 1;
2717 }
2718 if (!c)
2719 {
2720 k = gsnf_no_divide(x, i, vx);
2721 if (!k) break;
2722
2723 for (j=1; j<=i; j++)
2724 gcoeff(x,i,j) = gadd(gcoeff(x,i,j),gcoeff(x,k,j));
2725 if (all) gel(U,i) = gadd(gel(U,i),gel(U,k));
2726 }
2727 if (gc_needed(av,1))
2728 {
2729 if (DEBUGMEM>1) pari_warn(warnmem,"gsmithall");
2730 gerepileall(av, all? 3: 1, &x, &U, &V);
2731 }
2732 }
2733 }
2734 for (k=1; k<=n; k++)
2735 {
2736 GEN d, T = normalize_as_RgX(gcoeff(x,k,k), vx, &d);
2737 if (gequal0(T)) continue;
2738 if (all && !gequal1(d)) gel(V,k) = RgC_Rg_div(gel(V,k), d);
2739 gcoeff(x,k,k) = T;
2740 }
2741 z = all? mkvec3(shallowtrans(U), V, x): RgM_diagonal_shallow(x);
2742 return gerepilecopy(av, z);
2743 }
2744
2745 GEN
matsnf0(GEN x,long flag)2746 matsnf0(GEN x,long flag)
2747 {
2748 pari_sp av = avma;
2749 if (flag > 7) pari_err_FLAG("matsnf");
2750 if (typ(x) == t_VEC && flag & 4) return smithclean(x);
2751 if (typ(x)!=t_MAT) pari_err_TYPE("matsnf",x);
2752 if (RgM_is_ZM(x)) x = flag&1 ? smithall(x): smith(x);
2753 else x = RgXM_snf(x, flag&1);
2754 if (flag & 4) x = gerepileupto(av, smithclean(x));
2755 return x;
2756 }
2757 GEN
gsmith(GEN x)2758 gsmith(GEN x) { return RgXM_snf(x,0); }
2759 GEN
gsmithall(GEN x)2760 gsmithall(GEN x) { return RgXM_snf(x,1); }
2761
2762 /* H is a relation matrix, either in HNF or a t_VEC (diagonal HNF) */
2763 static GEN
snf_group(GEN H,GEN D,GEN * newU,GEN * newUi)2764 snf_group(GEN H, GEN D, GEN *newU, GEN *newUi)
2765 {
2766 long i, j, l;
2767
2768 ZM_snfclean(D, newU? *newU: NULL, newUi? *newUi: NULL);
2769 l = lg(D);
2770 if (newU) {
2771 GEN U = *newU;
2772 for (i = 1; i < l; i++)
2773 {
2774 GEN d = gel(D,i), d2 = shifti(d, 1);
2775 for (j = 1; j < lg(U); j++)
2776 gcoeff(U,i,j) = centermodii(gcoeff(U,i,j), d, d2);
2777 }
2778 *newU = U;
2779 }
2780 if (newUi && l > 1)
2781 { /* UHV=D -> U^-1 = (HV)D^-1 -> U^-1 = H(VD^-1 mod 1) mod H */
2782 /* Ui = ZM_inv(U, NULL); setlg(Ui, l); */
2783 GEN V = *newUi, Ui;
2784 int Hvec = (typ(H) == t_VEC);
2785 for (i = 1; i < l; i++) gel(V,i) = FpC_red(gel(V,i), gel(D,i));
2786 if (!Hvec)
2787 {
2788 if (ZM_isdiagonal(H)) { H = RgM_diagonal_shallow(H); Hvec = 1; }
2789 }
2790 Ui = Hvec? ZM_diag_mul(H, V): ZM_mul(H, V);
2791 for (i = 1; i < l; i++) gel(Ui,i) = ZC_Z_divexact(gel(Ui,i), gel(D,i));
2792 if (Hvec)
2793 { for (i = 1; i < l; i++) gel(Ui,i) = vecmodii(gel(Ui,i), H); }
2794 else
2795 Ui = ZM_hnfrem(Ui, H);
2796 *newUi = Ui;
2797 }
2798 return D;
2799 }
2800 /* H relation matrix among row of generators g in HNF. Let URV = D its SNF,
2801 * newU R newV = newD its clean SNF (no 1 in Dnew). Return the diagonal of
2802 * newD, newU and newUi such that 1/U = (newUi, ?).
2803 * Rationale: let (G,0) = g Ui be the new generators then
2804 * 0 = G U R --> G D = 0, g = G newU and G = g newUi */
2805 GEN
ZM_snf_group(GEN H,GEN * newU,GEN * newUi)2806 ZM_snf_group(GEN H, GEN *newU, GEN *newUi)
2807 {
2808 GEN D = ZM_snfall_i(H, newU, newUi, 1 + 2);
2809 return snf_group(H, D, newU, newUi);
2810 }
2811
2812 /* D a ZV: SNF for matdiagonal(D). Faster because we only ensure elementary
2813 * divisors condition: d[n] | ... | d[1] and need not convert D to matrix form*/
2814 GEN
ZV_snfall(GEN D,GEN * pU,GEN * pV)2815 ZV_snfall(GEN D, GEN *pU, GEN *pV)
2816 {
2817 pari_sp av = avma;
2818 long j, n = lg(D)-1;
2819 GEN U = pU? matid(n): NULL;
2820 GEN V = pV? matid(n): NULL;
2821 GEN p;
2822
2823 D = leafcopy(D);
2824 for (j = n; j > 0; j--)
2825 {
2826 GEN b = gel(D,j);
2827 if (signe(b) < 0)
2828 {
2829 gel(D,j) = negi(b);
2830 if (V) ZV_togglesign(gel(V,j));
2831 }
2832 }
2833 /* entries are nonnegative integers */
2834 p = gen_indexsort(D, NULL, &negcmpii);
2835 D = vecpermute(D, p);
2836 if (U) U = vecpermute(U, p);
2837 if (V) V = vecpermute(V, p);
2838 /* entries are sorted by decreasing value */
2839 for (j = n; j > 0; j--)
2840 {
2841 GEN b = gel(D,j);
2842 long i;
2843 for (i = j-1; i > 0; i--)
2844 { /* invariant: a >= b. If au+bv = d is a Bezout relation, A=a/d and B=b/d
2845 * we have [B,-A;u,v]*diag(a,b)*[1-u*A,1; -u*A,1]] = diag(Ab, d) */
2846 GEN a = gel(D,i), u,v, d = bezout(a,b, &u,&v), A, Wi, Wj;
2847 if (equalii(d,b)) continue;
2848 A = diviiexact(a,d);
2849 if (V)
2850 {
2851 GEN t = mulii(u,A);
2852 Wi = ZC_lincomb(subui(1,t), negi(t), gel(V,i), gel(V,j));
2853 Wj = ZC_add(gel(V,i), gel(V,j));
2854 gel(V,i) = Wi;
2855 gel(V,j) = Wj;
2856 }
2857 if (U)
2858 {
2859 GEN B = diviiexact(b,d);
2860 Wi = ZC_lincomb(B, negi(A), gel(U,i), gel(U,j));
2861 Wj = ZC_lincomb(u, v, gel(U,i), gel(U,j));
2862 gel(U,i) = Wi;
2863 gel(U,j) = Wj;
2864 }
2865 gel(D,i) = mulii(A,b); /* lcm(a,b) */
2866 gel(D,j) = d; /* gcd(a,b) */
2867 b = gel(D,j); if (equali1(b)) break;
2868 }
2869 }
2870 snf_pile(av, &D,&U,&V);
2871 if (U) *pU = shallowtrans(U);
2872 if (V) *pV = V;
2873 return D;
2874 }
2875 GEN
ZV_snf_group(GEN d,GEN * newU,GEN * newUi)2876 ZV_snf_group(GEN d, GEN *newU, GEN *newUi)
2877 {
2878 GEN D = ZV_snfall(d, newU, newUi);
2879 return snf_group(d, D, newU, newUi);
2880 }
2881
2882 /* D a vector of elementary divisors. Truncate (setlg) to leave out trivial
2883 * entries (= 1) */
2884 void
ZV_snf_trunc(GEN D)2885 ZV_snf_trunc(GEN D)
2886 {
2887 long i, l = lg(D);
2888 for (i = 1; i < l; i++)
2889 if (is_pm1(gel(D,i))) { setlg(D,i); break; }
2890 }
2891