2 #include <NTL/mat_ZZ.h>
3 #include <NTL/vec_ZZ.h>
4 #include <barvinok/barvinok.h>
5 #include <barvinok/evalue.h>
6 #include <barvinok/util.h>
8 #include "conversion.h"
9 #include "lattice_point.h"
10 #include "param_util.h"
15 #define ALLOC(type) (type*)malloc(sizeof(type))
17 /* returns an evalue that corresponds to
21 static evalue
*term(int param
, ZZ
& c
, Value
*den
= NULL
)
23 evalue
*EP
= new evalue();
25 value_set_si(EP
->d
,0);
26 EP
->x
.p
= new_enode(polynomial
, 2, param
+ 1);
27 evalue_set_si(&EP
->x
.p
->arr
[0], 0, 1);
28 value_init(EP
->x
.p
->arr
[1].x
.n
);
30 value_set_si(EP
->x
.p
->arr
[1].d
, 1);
32 value_assign(EP
->x
.p
->arr
[1].d
, *den
);
33 zz2value(c
, EP
->x
.p
->arr
[1].x
.n
);
37 /* returns an evalue that corresponds to
41 evalue
*multi_monom(vec_ZZ
& p
)
43 evalue
*X
= new evalue();
46 unsigned nparam
= p
.length()-1;
47 zz2value(p
[nparam
], X
->x
.n
);
48 value_set_si(X
->d
, 1);
49 for (int i
= 0; i
< nparam
; ++i
) {
52 evalue
*T
= term(i
, p
[i
]);
61 * Check whether mapping polyhedron P on the affine combination
62 * num yields a range that has a fixed quotient on integer
64 * If zero is true, then we are only interested in the quotient
65 * for the cases where the remainder is zero.
66 * Returns NULL if false and a newly allocated value if true.
68 static Value
*fixed_quotient(Polyhedron
*P
, vec_ZZ
& num
, Value d
, bool zero
)
71 int len
= num
.length();
72 Matrix
*T
= Matrix_Alloc(2, len
);
73 zz2values(num
, T
->p
[0]);
74 value_set_si(T
->p
[1][len
-1], 1);
75 Polyhedron
*I
= Polyhedron_Image(P
, T
, P
->NbConstraints
);
79 for (i
= 0; i
< I
->NbRays
; ++i
)
80 if (value_zero_p(I
->Ray
[i
][2])) {
88 int bounded
= line_minmax(I
, &min
, &max
);
92 mpz_cdiv_q(min
, min
, d
);
94 mpz_fdiv_q(min
, min
, d
);
95 mpz_fdiv_q(max
, max
, d
);
97 if (value_eq(min
, max
)) {
100 value_assign(*ret
, min
);
108 * Normalize linear expression coef modulo m
109 * Removes common factor and reduces coefficients
110 * Returns index of first non-zero coefficient or len
112 int normal_mod(Value
*coef
, int len
, Value
*m
)
117 Vector_Gcd(coef
, len
, &gcd
);
119 Vector_AntiScale(coef
, coef
, gcd
, len
);
121 value_division(*m
, *m
, gcd
);
128 for (j
= 0; j
< len
; ++j
)
129 mpz_fdiv_r(coef
[j
], coef
[j
], *m
);
130 for (j
= 0; j
< len
; ++j
)
131 if (value_notzero_p(coef
[j
]))
137 static bool mod_needed(Polyhedron
*PD
, vec_ZZ
& num
, Value d
, evalue
*E
)
139 Value
*q
= fixed_quotient(PD
, num
, d
, false);
144 value_oppose(*q
, *q
);
147 value_set_si(EV
.d
, 1);
149 value_multiply(EV
.x
.n
, *q
, d
);
151 free_evalue_refs(&EV
);
157 /* Computes the fractional part of the affine expression specified
158 * by coef (of length nvar+1) and the denominator denom.
159 * If PD is not NULL, then it specifies additional constraints
160 * on the variables that may be used to simplify the resulting
161 * fractional part expression.
163 * Modifies coef argument !
165 evalue
*fractional_part(Value
*coef
, Value denom
, int nvar
,
166 Polyhedron
*PD
, bool up
)
170 evalue
*EP
= evalue_zero();
174 /* {{ x }} = 1 - { -x } */
175 value_set_si(EP
->x
.n
, 1);
176 Vector_Oppose(coef
, coef
, nvar
+1);
180 value_assign(m
, denom
);
181 int j
= normal_mod(coef
, nvar
+1, &m
);
189 values2zz(coef
, num
, nvar
+1);
196 evalue_set_si(&tmp
, 0, 1);
200 while (j
< nvar
&& (num
[j
] == g
/2 || num
[j
] == 0))
202 if ((j
< nvar
&& num
[j
] > g
/2) || (j
== nvar
&& num
[j
] >= (g
+1)/2)) {
203 for (int k
= j
; k
< nvar
; ++k
)
206 num
[nvar
] = g
- 1 - num
[nvar
];
207 value_assign(tmp
.d
, m
);
209 zz2value(t
, tmp
.x
.n
);
215 ZZ t
= num
[nvar
] * sign
;
216 zz2value(t
, tmp
.x
.n
);
217 value_assign(tmp
.d
, m
);
220 evalue
*E
= multi_monom(num
);
224 if (PD
&& !mod_needed(PD
, num
, m
, E
)) {
226 value_set_si(EV
.x
.n
, sign
);
227 value_assign(EV
.d
, m
);
232 value_set_si(EV
.x
.n
, 1);
233 value_assign(EV
.d
, m
);
236 value_set_si(EV
.d
, 0);
237 EV
.x
.p
= new_enode(fractional
, 3, -1);
238 evalue_copy(&EV
.x
.p
->arr
[0], E
);
239 evalue_set_si(&EV
.x
.p
->arr
[1], 0, 1);
240 value_init(EV
.x
.p
->arr
[2].x
.n
);
241 value_set_si(EV
.x
.p
->arr
[2].x
.n
, sign
);
242 value_set_si(EV
.x
.p
->arr
[2].d
, 1);
247 free_evalue_refs(&EV
);
252 free_evalue_refs(&tmp
);
260 static evalue
*ceil(Value
*coef
, int len
, Value d
,
261 barvinok_options
*options
)
265 Vector_Oppose(coef
, coef
, len
);
266 c
= fractional_part(coef
, d
, len
-1, NULL
, false);
267 if (options
->lookup_table
)
268 evalue_mod2table(c
, len
-1);
272 evalue
* bv_ceil3(Value
*coef
, int len
, Value d
, Polyhedron
*P
)
274 Vector
*val
= Vector_Alloc(len
);
279 Vector_Scale(coef
, val
->p
, t
, len
);
280 value_absolute(t
, d
);
283 values2zz(val
->p
, num
, len
);
284 evalue
*EP
= multi_monom(num
);
289 value_set_si(tmp
.x
.n
, 1);
290 value_assign(tmp
.d
, t
);
294 Vector_Oppose(val
->p
, val
->p
, len
);
295 evalue
*f
= fractional_part(val
->p
, t
, len
-1, P
, false);
302 /* copy EP to malloc'ed evalue */
303 evalue
*E
= ALLOC(evalue
);
307 free_evalue_refs(&tmp
);
313 void lattice_point_fixed(Value
*vertex
, Value
*vertex_res
,
314 Matrix
*Rays
, Matrix
*Rays_res
,
315 Value
*point
, int *closed
)
317 unsigned dim
= Rays
->NbRows
;
318 if (value_one_p(vertex
[dim
]) && !closed
)
319 Vector_Copy(vertex_res
, point
, Rays_res
->NbColumns
);
321 Matrix
*R2
= Matrix_Copy(Rays
);
322 Matrix
*inv
= Matrix_Alloc(Rays
->NbRows
, Rays
->NbColumns
);
323 int ok
= Matrix_Inverse(R2
, inv
);
326 Vector
*lambda
= Vector_Alloc(dim
);
327 Vector_Matrix_Product(vertex
, inv
, lambda
->p
);
329 for (int j
= 0; j
< dim
; ++j
)
330 if (!closed
|| closed
[j
])
331 mpz_cdiv_q(lambda
->p
[j
], lambda
->p
[j
], vertex
[dim
]);
333 value_addto(lambda
->p
[j
], lambda
->p
[j
], vertex
[dim
]);
334 mpz_fdiv_q(lambda
->p
[j
], lambda
->p
[j
], vertex
[dim
]);
336 Vector_Matrix_Product(lambda
->p
, Rays_res
, point
);
341 static Matrix
*Matrix_AddRowColumn(Matrix
*M
)
343 Matrix
*M2
= Matrix_Alloc(M
->NbRows
+1, M
->NbColumns
+1);
344 for (int i
= 0; i
< M
->NbRows
; ++i
)
345 Vector_Copy(M
->p
[i
], M2
->p
[i
], M
->NbColumns
);
346 value_set_si(M2
->p
[M
->NbRows
][M
->NbColumns
], 1);
350 #define FORALL_COSETS(det,D,i,k) \
352 Vector *k = Vector_Alloc(D->NbRows+1); \
353 value_set_si(k->p[D->NbRows], 1); \
354 for (unsigned long i = 0; i < det; ++i) { \
355 unsigned long _fc_val = i; \
356 for (int j = 0; j < D->NbRows; ++j) { \
357 value_set_si(k->p[j], _fc_val % mpz_get_ui(D->p[j][j]));\
358 _fc_val /= mpz_get_ui(D->p[j][j]); \
360 #define END_FORALL_COSETS \
365 /* Compute the lattice points in the vertex cone at "values" with rays "rays".
366 * The lattice points are returned in "vertex".
368 * Rays has the generators as rows and so does W.
369 * We first compute { m-v, u_i^* } with m = k W, where k runs through
372 * [k 1] [ d1*W 0 ] [ U' 0 ] = [k 1] T2
374 * where d1 and d2 are the denominators of v and U^{-1}=U'/d2.
375 * Then lambda = { k } (componentwise)
376 * We compute x - floor(x) = {x} = { a/b } as fdiv_r(a,b)/b
377 * For open rays/facets, we need values in (0,1] rather than [0,1),
378 * so we compute {{x}} = x - ceil(x-1) = a/b - ceil((a-b)/b)
379 * = (a - b cdiv_q(a-b,b) - b + b)/b
380 * = (cdiv_r(a,b)+b)/b
381 * Finally, we compute v + lambda * U
382 * The denominator of lambda can be d1*d2, that of lambda2 = lambda*U
383 * can be at most d1, since it is integer if v = 0.
384 * The denominator of v + lambda2 is 1.
386 * The _res variants of the input variables may have been multiplied with
387 * a (list of) nonorthogonal vector(s) and may therefore have fewer columns
388 * than their original counterparts.
390 void lattice_points_fixed(Value
*vertex
, Value
*vertex_res
,
391 Matrix
*Rays
, Matrix
*Rays_res
, Matrix
*points
,
392 unsigned long det
, int *closed
)
394 unsigned dim
= Rays
->NbRows
;
396 lattice_point_fixed(vertex
, vertex_res
, Rays
, Rays_res
,
397 points
->p
[0], closed
);
401 Smith(Rays
, &U
, &W
, &D
);
405 unsigned long det2
= 1;
406 for (int i
= 0 ; i
< D
->NbRows
; ++i
)
407 det2
*= mpz_get_ui(D
->p
[i
][i
]);
410 Matrix
*T
= Matrix_Alloc(W
->NbRows
+1, W
->NbColumns
+1);
411 for (int i
= 0; i
< W
->NbRows
; ++i
)
412 Vector_Scale(W
->p
[i
], T
->p
[i
], vertex
[dim
], W
->NbColumns
);
416 value_set_si(tmp
, -1);
417 Vector_Scale(vertex
, T
->p
[dim
], tmp
, dim
);
419 value_assign(T
->p
[dim
][dim
], vertex
[dim
]);
421 Matrix
*R2
= Matrix_AddRowColumn(Rays
);
422 Matrix
*inv
= Matrix_Alloc(R2
->NbRows
, R2
->NbColumns
);
423 int ok
= Matrix_Inverse(R2
, inv
);
427 Matrix
*T2
= Matrix_Alloc(dim
+1, dim
+1);
428 Matrix_Product(T
, inv
, T2
);
431 Vector
*lambda
= Vector_Alloc(dim
+1);
432 Vector
*lambda2
= Vector_Alloc(Rays_res
->NbColumns
);
433 FORALL_COSETS(det
, D
, i
, k
)
434 Vector_Matrix_Product(k
->p
, T2
, lambda
->p
);
435 for (int j
= 0; j
< dim
; ++j
)
436 if (!closed
|| closed
[j
])
437 mpz_fdiv_r(lambda
->p
[j
], lambda
->p
[j
], lambda
->p
[dim
]);
439 mpz_cdiv_r(lambda
->p
[j
], lambda
->p
[j
], lambda
->p
[dim
]);
440 value_addto(lambda
->p
[j
], lambda
->p
[j
], lambda
->p
[dim
]);
442 Vector_Matrix_Product(lambda
->p
, Rays_res
, lambda2
->p
);
443 for (int j
= 0; j
< lambda2
->Size
; ++j
)
444 assert(mpz_divisible_p(lambda2
->p
[j
], inv
->p
[dim
][dim
]));
445 Vector_AntiScale(lambda2
->p
, lambda2
->p
, inv
->p
[dim
][dim
], lambda2
->Size
);
446 Vector_Add(lambda2
->p
, vertex_res
, lambda2
->p
, lambda2
->Size
);
447 for (int j
= 0; j
< lambda2
->Size
; ++j
)
448 assert(mpz_divisible_p(lambda2
->p
[j
], vertex
[dim
]));
449 Vector_AntiScale(lambda2
->p
, points
->p
[i
], vertex
[dim
], lambda2
->Size
);
452 Vector_Free(lambda2
);
459 /* Returns the power of (t+1) in the term of a rational generating function,
460 * i.e., the scalar product of the actual lattice point and lambda.
461 * The lattice point is the unique lattice point in the fundamental parallelepiped
462 * of the unimodual cone i shifted to the parametric vertex W/lcm.
464 * The rows of W refer to the coordinates of the vertex
465 * The first nparam columns are the coefficients of the parameters
466 * and the final column is the constant term.
467 * lcm is the common denominator of all coefficients.
469 static evalue
**lattice_point_fractional(const mat_ZZ
& rays
, vec_ZZ
& lambda
,
471 unsigned long det
, int *closed
)
473 unsigned nparam
= V
->NbColumns
-2;
474 evalue
**E
= new evalue
*[det
];
476 Matrix
* Rays
= zz2matrix(rays
);
477 Matrix
*T
= Transpose(Rays
);
478 Matrix
*T2
= Matrix_Copy(T
);
479 Matrix
*inv
= Matrix_Alloc(T2
->NbRows
, T2
->NbColumns
);
480 int ok
= Matrix_Inverse(T2
, inv
);
484 matrix2zz(V
, vertex
, V
->NbRows
, V
->NbColumns
-1);
487 num
= lambda
* vertex
;
489 evalue
*EP
= multi_monom(num
);
491 evalue_div(EP
, V
->p
[0][nparam
+1]);
493 Matrix
*L
= Matrix_Alloc(inv
->NbRows
, V
->NbColumns
);
494 Matrix_Product(inv
, V
, L
);
497 matrix2zz(T
, RT
, T
->NbRows
, T
->NbColumns
);
500 vec_ZZ p
= lambda
* RT
;
506 for (int i
= 0; i
< L
->NbRows
; ++i
) {
508 Vector_Oppose(L
->p
[i
], L
->p
[i
], nparam
+1);
509 f
= fractional_part(L
->p
[i
], V
->p
[i
][nparam
+1], nparam
,
510 NULL
, closed
&& !closed
[i
]);
519 for (int i
= 0; i
< L
->NbRows
; ++i
)
520 value_assign(L
->p
[i
][nparam
+1], V
->p
[i
][nparam
+1]);
524 mpz_set_ui(denom
, det
);
525 value_multiply(denom
, L
->p
[0][nparam
+1], denom
);
528 Smith(Rays
, &U
, &W
, &D
);
532 unsigned long det2
= 1;
533 for (int i
= 0 ; i
< D
->NbRows
; ++i
)
534 det2
*= mpz_get_ui(D
->p
[i
][i
]);
537 Matrix_Transposition(inv
);
538 Matrix
*T2
= Matrix_Alloc(W
->NbRows
, inv
->NbColumns
);
539 Matrix_Product(W
, inv
, T2
);
542 unsigned dim
= D
->NbRows
;
543 Vector
*lambda
= Vector_Alloc(dim
);
545 Vector
*row
= Vector_Alloc(nparam
+1);
546 FORALL_COSETS(det
, D
, i
, k
)
547 Vector_Matrix_Product(k
->p
, T2
, lambda
->p
);
550 evalue_copy(E
[i
], EP
);
551 for (int j
= 0; j
< L
->NbRows
; ++j
) {
553 Vector_Oppose(L
->p
[j
], row
->p
, nparam
+1);
554 value_addmul(row
->p
[nparam
], L
->p
[j
][nparam
+1], lambda
->p
[j
]);
555 f
= fractional_part(row
->p
, denom
, nparam
,
556 NULL
, closed
&& !closed
[j
]);
571 free_evalue_refs(EP
);
583 static evalue
**lattice_point(const mat_ZZ
& rays
, vec_ZZ
& lambda
,
585 unsigned long det
, int *closed
,
586 barvinok_options
*options
)
588 evalue
**lp
= lattice_point_fractional(rays
, lambda
, V
->Vertex
, det
, closed
);
589 if (options
->lookup_table
) {
590 for (int i
= 0; i
< det
; ++i
)
591 evalue_mod2table(lp
[i
], V
->Vertex
->NbColumns
-2);
596 /* returns the unique lattice point in the fundamental parallelepiped
597 * of the unimodual cone C shifted to the parametric vertex V.
599 * The return values num and E_vertex are such that
600 * coordinate i of this lattice point is equal to
602 * num[i] + E_vertex[i]
604 void lattice_point(Param_Vertices
*V
, const mat_ZZ
& rays
, vec_ZZ
& num
,
605 evalue
**E_vertex
, barvinok_options
*options
)
607 unsigned nparam
= V
->Vertex
->NbColumns
- 2;
608 unsigned dim
= rays
.NumCols();
610 /* It doesn't really make sense to call lattice_point when dim == 0,
611 * but apparently it happens from indicator_constructor in lexmin.
617 vertex
.SetLength(nparam
+1);
622 assert(V
->Vertex
->NbRows
> 0);
623 Param_Vertex_Common_Denominator(V
);
625 if (value_notone_p(V
->Vertex
->p
[0][nparam
+1])) {
626 Matrix
* Rays
= zz2matrix(rays
);
627 Matrix
*T
= Transpose(Rays
);
628 Matrix
*T2
= Matrix_Copy(T
);
629 Matrix
*inv
= Matrix_Alloc(T2
->NbRows
, T2
->NbColumns
);
630 int ok
= Matrix_Inverse(T2
, inv
);
634 /* temporarily ignore (common) denominator */
635 V
->Vertex
->NbColumns
--;
636 Matrix
*L
= Matrix_Alloc(inv
->NbRows
, V
->Vertex
->NbColumns
);
637 Matrix_Product(inv
, V
->Vertex
, L
);
638 V
->Vertex
->NbColumns
++;
645 evalue
*remainders
[dim
];
646 for (int i
= 0; i
< dim
; ++i
)
647 remainders
[i
] = ceil(L
->p
[i
], nparam
+1, V
->Vertex
->p
[0][nparam
+1],
652 for (int i
= 0; i
< V
->Vertex
->NbRows
; ++i
) {
653 values2zz(V
->Vertex
->p
[i
], vertex
, nparam
+1);
654 E_vertex
[i
] = multi_monom(vertex
);
657 value_set_si(f
.x
.n
, 1);
658 value_assign(f
.d
, V
->Vertex
->p
[0][nparam
+1]);
660 emul(&f
, E_vertex
[i
]);
662 for (int j
= 0; j
< dim
; ++j
) {
663 if (value_zero_p(T
->p
[i
][j
]))
667 evalue_copy(&cp
, remainders
[j
]);
668 if (value_notone_p(T
->p
[i
][j
])) {
669 value_set_si(f
.d
, 1);
670 value_assign(f
.x
.n
, T
->p
[i
][j
]);
673 eadd(&cp
, E_vertex
[i
]);
674 free_evalue_refs(&cp
);
677 for (int i
= 0; i
< dim
; ++i
) {
678 free_evalue_refs(remainders
[i
]);
682 free_evalue_refs(&f
);
690 for (int i
= 0; i
< V
->Vertex
->NbRows
; ++i
) {
692 if (First_Non_Zero(V
->Vertex
->p
[i
], nparam
) == -1) {
694 value2zz(V
->Vertex
->p
[i
][nparam
], num
[i
]);
696 values2zz(V
->Vertex
->p
[i
], vertex
, nparam
+1);
697 E_vertex
[i
] = multi_monom(vertex
);
703 static int lattice_point_fixed(Param_Vertices
* V
, const mat_ZZ
& rays
,
704 vec_ZZ
& lambda
, term_info
* term
, unsigned long det
, int *closed
)
706 unsigned nparam
= V
->Vertex
->NbColumns
- 2;
707 unsigned dim
= rays
.NumCols();
709 for (int i
= 0; i
< dim
; ++i
)
710 if (First_Non_Zero(V
->Vertex
->p
[i
], nparam
) != -1)
713 Vector
*fixed
= Vector_Alloc(dim
+1);
714 for (int i
= 0; i
< dim
; ++i
)
715 value_assign(fixed
->p
[i
], V
->Vertex
->p
[i
][nparam
]);
716 value_assign(fixed
->p
[dim
], V
->Vertex
->p
[0][nparam
+1]);
719 Matrix
*points
= Matrix_Alloc(det
, dim
);
720 Matrix
* Rays
= zz2matrix(rays
);
721 lattice_points_fixed(fixed
->p
, fixed
->p
, Rays
, Rays
, points
, det
, closed
);
723 matrix2zz(points
, vertex
, points
->NbRows
, points
->NbColumns
);
726 term
->constant
= vertex
* lambda
;
732 /* Returns the power of (t+1) in the term of a rational generating function,
733 * i.e., the scalar product of the actual lattice point and lambda.
734 * The lattice point is the unique lattice point in the fundamental parallelepiped
735 * of the unimodual cone i shifted to the parametric vertex V.
737 * The result is returned in term.
739 void lattice_point(Param_Vertices
* V
, const mat_ZZ
& rays
, vec_ZZ
& lambda
,
740 term_info
* term
, unsigned long det
, int *closed
,
741 barvinok_options
*options
)
743 unsigned nparam
= V
->Vertex
->NbColumns
- 2;
744 unsigned dim
= rays
.NumCols();
746 vertex
.SetDims(V
->Vertex
->NbRows
, nparam
+1);
748 Param_Vertex_Common_Denominator(V
);
750 if (lattice_point_fixed(V
, rays
, lambda
, term
, det
, closed
))
753 if (det
!= 1 || closed
|| value_notone_p(V
->Vertex
->p
[0][nparam
+1])) {
754 term
->E
= lattice_point(rays
, lambda
, V
, det
, closed
, options
);
757 for (int i
= 0; i
< V
->Vertex
->NbRows
; ++i
) {
758 assert(value_one_p(V
->Vertex
->p
[i
][nparam
+1])); // for now
759 values2zz(V
->Vertex
->p
[i
], vertex
[i
], nparam
+1);
763 num
= lambda
* vertex
;
766 for (int j
= 0; j
< nparam
; ++j
)
770 term
->E
= new evalue
*[1];
771 term
->E
[0] = multi_monom(num
);
774 term
->constant
.SetLength(1);
775 term
->constant
[0] = num
[nparam
];