PIPS
|
Go to the source code of this file.
Functions | |
Psysteme | sc_enveloppe_chernikova_ofl_ctrl (Psysteme, Psysteme, int) |
Warning! Do not modify this file that is automatically generated! More... | |
Psysteme | sc_enveloppe_chernikova (Psysteme, Psysteme) |
Psysteme | elementary_convex_union (Psysteme, Psysteme) |
implements FC basic idea of simple fast cases... More... | |
Psysteme | sc_cute_convex_hull (Psysteme, Psysteme) |
returns s1 v s2. More... | |
Psysteme | sc_rectangular_hull (Psysteme, Pbase) |
take the rectangular bounding box of the systeme sc , by projecting each constraint of the systeme against each of the basis in pb More... | |
Ptsg | sc_to_sg_chernikova_fixprec (Psysteme) |
chernikova_fixprec.c More... | |
Psysteme | sg_to_sc_chernikova_fixprec (Ptsg) |
Psysteme | sc_convex_hull_fixprec (Psysteme, Psysteme) |
Ptsg | sc_to_sg_chernikova (Psysteme) |
chernikova_mulprec.c More... | |
Psysteme | sg_to_sc_chernikova (Ptsg) |
Psysteme | sc_convex_hull (Psysteme, Psysteme) |
implements FC basic idea of simple fast cases...
returns s1 v s2. s1 and s2 are not touched. The bases should be minimum for best efficiency! otherwise useless columns are allocated and computed. a common base is rebuilt in actual_convex_union. other fast cases may be added?
s1 | 1 |
s2 | 2 |
Definition at line 171 of file sc_enveloppe.c.
References actual_convex_union(), b1, b2, base_rm, base_union(), s1, sc_dup(), sc_empty(), sc_empty_p(), sc_rn(), sc_rn_p(), and vect_common_variables_p().
Referenced by sc_cute_convex_hull().
sc1 | c1 |
sc2 | c2 |
Definition at line 74 of file chernikova.c.
References abort, linear_use_gmp(), and sc_convex_hull_fixprec().
Referenced by main(), and sc_enveloppe_chernikova_ofl_ctrl().
sc1 | c1 |
sc2 | c2 |
Definition at line 40 of file chernikova_fixprec.c.
References sc_union().
Referenced by sc_convex_hull().
returns s1 v s2.
initial systems are not changed.
v convex union u union n intersection T orthogonality
(1) CA:
P1 v P2 = (P n X1) v (P n X2) = let P = P' n P'' so that P' T X1 and P' T X2 and P' T P'' built by transitive closure, then P1 v P2 = (P' n (P'' n X1)) v (P' n (P'' n X2)) = P' n ((P'' n X1) v (P'' n X2))
Proof by considering generating systems: Def: A T B <=> var(A) n var(B) = 0 Prop: A n B if A T B Let A = (x,v,l), B = (y,w,m) A n B = { z | z = (x) \mu + (v) d + (l) e + (0) f (0) + (0) + (0) (I) and z = (0) \nu + (0) g + (0) h + (I) f' (y) + (w) + (m) (0) with \mu>0, \nu>0, \sum\mu=1, \sum\nu=1, d>0, g>0 } we can always find f and f' equals to the other part (by extension) so A n B = { z | z = (x 0) \mu + (v 0) d + (l 0) e (0 y) \nu (0 w) g (0 m) h with \mu \nu d g constraints... } It is a convex : ((xi) , (v 0), (l 0)) (yj)ij, (0 w), (0 m) we just need to prove that Cmn == Cg defined as (x 0) \mu == (xi) \gamma with >0 and \sum = 1 (0 y) \nu (yj)ij . Cg in a convex. . Cg \in Cmn since ((xi)(yj) ij) in Cmn with \mu = \delta i, \nu = \delta j . Cmn \in Cg by chosing \gamma_ij = \mu_i\nu_j, which >0 and \sum = 1 Prop: A T B and A T C => A T (B v C) and A T (B n C) Theo: A T B and A T C => (A n B) v (A n C) = A n (B v C) compute both generating systems with above props. they are equal.
(2) FI:
perform exact projections of common equalities. no proof at the time. It looks ok anyway.
(3) FC:
base(P) n base(Q) = 0 => P u Q = Rn and some other very basic simplifications... which are not really interesting if no decomposition is performed?
on overflows FI suggested.
1/ we want to compute : (A n B1) u (A n B2) 2/ we chose to approximate it as : (A n B1) v (A n B2) 3/ we try Corinne's factorization with transitive closure A' n ((A'' n B1) v (A'' n B2)) 4/ on overflow, we can try A n (B1 v B2) // NOT IMPLEMENTED YET 5/ if we have one more overflow, then A looks good as an approximation.
CA: extract common disjoint part.
FI: in sc_common_projection_convex_hull note that equalities are not that big a burden to chernikova?
fast sc_append
usually we use V (convex hull) as a U (set union) approximation. as we have : (A n B1) U (A n B2) \in A the common part of both systems is an approximation of the union! sc_rn is returned on overflows (and some other case). I don't think that the result is improved apart when actual overflow occurs. FC/CA.
dead. either rm or moved as sc.
better compatibility with previous version, as the convex union normalizes the system and removes redundancy, what is not done if part of the system is separated. Other calls may be considered here?
ok, it will look better.
misleading... not really projected. { x==y, y==3 } => { x==3, y==3 }
sc, su: fast union of disjoint.
regenerate the expected base.
is1 | s1 |
is2 | s2 |
Definition at line 369 of file sc_enveloppe.c.
References Ssysteme::base, base_rm, base_union(), elementary_convex_union(), extract_common_syst(), is2(), linear_number_of_exception_thrown, s1, sc_dup(), sc_fix(), sc_fusion(), sc_rm(), sc_rn(), sc_transform_ineg_in_eg(), transitive_closure_from_two_bases(), and vect_size().
Referenced by cute_convex_union(), do_array_expansion(), and statement_insertion_fix_access().
s1 | 1 |
s2 | 2 |
Definition at line 127 of file sc_enveloppe.c.
References OFL_CTRL, s1, and sc_enveloppe_chernikova_ofl_ctrl().
Referenced by actual_convex_union(), and dependence_cone_positive().
Warning! Do not modify this file that is automatically generated!
Modify src/Libs/polyedre/polyedre-local.h instead, to add your own modifications. header file built by cproto polyedre-local.h package sur les polyedres poly
Malik Imadache, Corinne Ancourt, Neil Butler, Francois Irigoin
Modifications:
Warning! Do not modify this file that is automatically generated!
Ce module est range dans le package polyedre bien qu'il soit utilisable en n'utilisant que des systemes lineaires (package sc) parce qu'il utilise lui-meme des routines sur les polyedres.
Francois Irigoin, Janvier 1990 Corinne Ancourt, Fabien Coelho from time to time (1999/2000) Psysteme sc_enveloppe_chernikova_ofl_ctrl(Psysteme s1, s2, int ofl_ctrl) input : output : modifies : s1 and s2 are NOT modified. comment : s1 and s2 must have a basis.
s = enveloppe(s1, s2); return s;
calcul d'une representation par systeme lineaire de l'enveloppe convexe des polyedres definis par les systemes lineaires s1 et s2
calcul de l'enveloppe convexe
printf("systeme final \n"); sc_dump(s);
mem_spy_end("sc_enveloppe_chernikova_ofl_ctrl");
s1 | 1 |
s2 | 2 |
ofl_ctrl | fl_ctrl |
Definition at line 68 of file sc_enveloppe.c.
References assert, base_dup(), CATCH, fprintf(), FWD_OFL_CTRL, OFL_CTRL, overflow_error, s1, sc_convex_hull(), sc_dup(), sc_empty(), sc_empty_p(), sc_rn(), sc_rn_p(), timeout_error, and UNCATCH.
Referenced by sc_enveloppe_chernikova().
take the rectangular bounding box of the systeme sc
, by projecting each constraint of the systeme against each of the basis in pb
SG: this is basically a renaming of sc_projection_on_variables ...
sc | c |
pb | b |
Definition at line 456 of file sc_enveloppe.c.
References CATCH, overflow_error, TRY, and UNCATCH.
Referenced by do_array_expansion(), do_solve_hardware_constraints_on_nb_proc(), and rectangularization_region().
sc | c |
Definition at line 42 of file chernikova.c.
References abort, linear_use_gmp(), sc_to_sg_chernikova_fixprec(), and sg.
Referenced by dependence_cone_positive(), main(), and unimodular().
sc | c |
Definition at line 32 of file chernikova_fixprec.c.
References sg_of_sc().
Referenced by sc_to_sg_chernikova().
sg | g |
Definition at line 58 of file chernikova.c.
References abort, linear_use_gmp(), sg, and sg_to_sc_chernikova_fixprec().
Referenced by main(), prettyprint_dependence_graph(), and prettyprint_dependence_graph_view().
sg | g |
Definition at line 36 of file chernikova_fixprec.c.
References sc_of_sg(), and sg.
Referenced by sg_to_sc_chernikova().