polyedre.h File Reference

#include "ray_dte.h"
#include "sg.h"
#include "polynome.h"

Include dependency graph for polyedre.h:

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)

Function Documentation

elementary_convex_union()

Psysteme elementary_convex_union	(	Psysteme	s1,
		Psysteme	s2
	)

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?

Parameters

s1	1
s2	2

Definition at line 171 of file sc_enveloppe.c.

{
  bool
    b1 = sc_empty_p(s1),
    b2 = sc_empty_p(s2);
    
  if (b1 && b2)
    return sc_empty(base_union(sc_base(s1), sc_base(s2)));
 
  if (b1) {
    Psysteme s = sc_dup(s2);
    Pbase b = base_union(sc_base(s1), sc_base(s2));
    base_rm(sc_base(s));
    sc_base(s) = b;
    return s;
  }
  
  if (b2) {
    Psysteme s = sc_dup(s1);
    Pbase b = base_union(sc_base(s1), sc_base(s2));
    base_rm(sc_base(s));
    sc_base(s) = b;
    return s;
  }
  
  if (sc_rn_p(s1) || sc_rn_p(s2) || 
      !vect_common_variables_p(sc_base(s1), sc_base(s2)))
    return sc_rn(base_union(sc_base(s1), sc_base(s2)));
 
  /*
  if (sc_dimension(s1)==1 && sc_dimension(s2)==1 && 
      sc_base(s1)->var == sc_base(s2)->var)
  {
    // fast computation...
  }
  */
 
  return actual_convex_union(s1, s2);
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_convex_hull()

Psysteme sc_convex_hull	(	Psysteme	sc1,
		Psysteme	sc2
	)

Parameters

sc1	c1
sc2	c2

Definition at line 74 of file chernikova.c.

{
        Psysteme sc;
 
        if (linear_use_gmp())
#ifdef HAVE_GMP_H
                sc = sc_convex_hull_mulprec(sc1, sc2);
#else
    abort();
#endif // HAVE_GMP_H
        else
                sc = sc_convex_hull_fixprec(sc1, sc2);
 
        return sc;
}

References abort, linear_use_gmp(), and sc_convex_hull_fixprec().

Referenced by main(), and sc_enveloppe_chernikova_ofl_ctrl().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_convex_hull_fixprec()

Psysteme sc_convex_hull_fixprec	(	Psysteme	sc1,
		Psysteme	sc2
	)

Parameters

sc1	c1
sc2	c2

Definition at line 40 of file chernikova_fixprec.c.

                                                            {
        return sc_union(sc1, sc2);
}

References sc_union().

Referenced by sc_convex_hull().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_cute_convex_hull()

Psysteme sc_cute_convex_hull	(	Psysteme	is1,
		Psysteme	is2
	)

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.

Parameters

is1	s1
is2	s2

Definition at line 369 of file sc_enveloppe.c.

{
  Psysteme s1, s2, sc, stc, su, scsaved;
  int current_overflow_count;
 
  s1 = sc_dup(is1);
  s2 = sc_dup(is2);
 
  /* CA: extract common disjoint part.
   */
  sc = extract_common_syst(s1, s2);
  scsaved = sc_dup(sc);
  stc = transitive_closure_from_two_bases(sc, s1->base, s2->base);
 
  /* FI: in sc_common_projection_convex_hull
     note that equalities are not that big a burden to chernikova?
   */
  sc_extract_exact_common_equalities(stc, sc, s1, s2);
 
  /* fast sc_append */
  s1 = sc_fusion(s1, sc_dup(stc));
  sc_fix(s1);
 
  s2 = sc_fusion(s2, stc);
  sc_fix(s2);
 
  stc = NULL;
 
  current_overflow_count = linear_number_of_exception_thrown;
 
  su = elementary_convex_union(s1, s2);
  
  /* 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.
   */
  if (current_overflow_count!=linear_number_of_exception_thrown)
  {
    if (su) sc_rm(su), su = NULL;
    if (sc) sc_rm(sc), sc = NULL;
    sc = scsaved;
  }
  else
  {
    sc_rm(scsaved);
  }
 
  scsaved = NULL; /* dead. either rm or moved as sc. */
  sc_rm(s1); 
  sc_rm(s2);
 
  /* 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?
   */
  sc_transform_ineg_in_eg(sc); /* ok, it will look better. */
  /* misleading... not really projected. { x==y, y==3 } => { x==3, y==3 } */
  sc_project_very_simple_equalities(sc);
 
  /* sc, su: fast union of disjoint. */
  sc = sc_fusion(sc, su);
 
  /* regenerate the expected base. */
  if (sc) 
  {
    sc_fix(sc);
    if (sc_base(sc)) base_rm(sc_base(sc));
  }
  else
  {
      sc = sc_rn(NULL);
  }
  sc_base(sc) = base_union(sc_base(is1), sc_base(is2));
  sc_dimension(sc) = vect_size(sc_base(sc));
  
  return sc;
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_enveloppe_chernikova()

Psysteme sc_enveloppe_chernikova	(	Psysteme	s1,
		Psysteme	s2
	)

Parameters

s1	1
s2	2

Definition at line 127 of file sc_enveloppe.c.

{
  return sc_enveloppe_chernikova_ofl_ctrl((s1), (s2), OFL_CTRL);
}

References OFL_CTRL, s1, and sc_enveloppe_chernikova_ofl_ctrl().

Referenced by actual_convex_union(), and dependence_cone_positive().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_enveloppe_chernikova_ofl_ctrl()

Psysteme sc_enveloppe_chernikova_ofl_ctrl	(	Psysteme	s1,
		Psysteme	s2,
		int	ofl_ctrl
	)

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:

• declaration de Ppoly et Spoly utilisant Psysteme au lieu de struct Ssysteme * (FI, 3/1/90) obsolete (not maintained) macro d'acces aux champs et sous-champs d'un polyedre, de son systeme generateur sg et de son systeme de contraintes sc cproto-generated files sc_enveloppe.c

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

mem_spy_begin();

calcul de l'enveloppe convexe

printf("systeme final \n"); sc_dump(s);

mem_spy_end("sc_enveloppe_chernikova_ofl_ctrl");

Parameters

s1	1
s2	2
ofl_ctrl	fl_ctrl

Definition at line 68 of file sc_enveloppe.c.

{
  Psysteme s = SC_UNDEFINED;
  volatile bool catch_performed = false;
  /* mem_spy_begin(); */
 
  assert(!SC_UNDEFINED_P(s1) && !SC_UNDEFINED_P(s2));
 
  // yuk
  if (ofl_ctrl == OFL_CTRL)
  {
    ofl_ctrl = FWD_OFL_CTRL;
    catch_performed = true;
    CATCH(overflow_error|timeout_error) {
      //CATCH(overflow_error) {
      /*
       *   PLEASE do not remove this warning.
       *
       *   BC 24/07/95
       */
      fprintf(stderr, "[sc_enveloppe_chernikova_ofl_ctrl] "
              "arithmetic error occured\n" );
      s = sc_rn(base_dup(sc_base(s1)));
      return s;
    }
  }
 
  if (SC_RN_P(s2) || sc_rn_p(s2) || sc_dimension(s2)==0
      || sc_empty_p(s1) || !sc_faisabilite_ofl(s1))
  {
    Psysteme sc2 = sc_dup(s2);
    sc2 = sc_elim_redond(sc2);
    s = SC_UNDEFINED_P(sc2)? sc_empty(base_dup(sc_base(s2))): sc2;
  }
  else
  {
    if (SC_RN_P(s1) ||sc_rn_p(s1) || sc_dimension(s1)==0
        || sc_empty_p(s2) || !sc_faisabilite_ofl(s2))
    {
      Psysteme sc1 = sc_dup(s1);
      sc1 = sc_elim_redond(sc1);
      s = SC_UNDEFINED_P(sc1)? sc_empty(base_dup(sc_base(s1))): sc1;
    }
    else
    {
      /* calcul de l'enveloppe convexe */
      s = sc_convex_hull(s1,s2);
      /* printf("systeme final \n"); sc_dump(s);  */
    }
  }
  if (catch_performed)
    UNCATCH(overflow_error|timeout_error);
  /* mem_spy_end("sc_enveloppe_chernikova_ofl_ctrl"); */
  return s;
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_rectangular_hull()

Psysteme sc_rectangular_hull	(	Psysteme	sc,
		Pbase	pb
	)

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 ...

Parameters

sc	c
pb	b

Definition at line 456 of file sc_enveloppe.c.

                                                    {
    volatile Psysteme rectangular = SC_UNDEFINED;
    rectangular = sc_projection_on_variables(sc,pb,pb);
    CATCH(overflow_error) {
        ;
        // it does not matter if we fail ...
    }
    TRY {
        sc_nredund(&rectangular);
        UNCATCH(overflow_error);
    }
    return rectangular;
}

References CATCH, overflow_error, TRY, and UNCATCH.

Referenced by do_array_expansion(), do_solve_hardware_constraints_on_nb_proc(), and rectangularization_region().

Here is the caller graph for this function:

sc_to_sg_chernikova()

Ptsg sc_to_sg_chernikova

(

Psysteme

sc

)

chernikova_mulprec.c

chernikova.c

Parameters

sc

c

Definition at line 42 of file chernikova.c.

{
        Ptsg sg;
 
        if (linear_use_gmp())
#ifdef HAVE_GMP_H
                sg = sc_to_sg_chernikova_mulprec(sc);
#else
    abort();
#endif
        else
                sg = sc_to_sg_chernikova_fixprec(sc);
 
        return sg;
}

References abort, linear_use_gmp(), sc_to_sg_chernikova_fixprec(), and sg.

Referenced by dependence_cone_positive(), main(), and unimodular().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_to_sg_chernikova_fixprec()

Ptsg sc_to_sg_chernikova_fixprec

(

Psysteme

sc

)

chernikova_fixprec.c

Parameters

sc

c

Definition at line 32 of file chernikova_fixprec.c.

                                              {
        return sg_of_sc(sc);
}

References sg_of_sc().

Referenced by sc_to_sg_chernikova().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_to_sc_chernikova()

Psysteme sg_to_sc_chernikova

(

Ptsg

sg

)

Parameters

sg

g

Definition at line 58 of file chernikova.c.

{
        Psysteme sc;
 
        if (linear_use_gmp())
#ifdef HAVE_GMP_H
                sc = sg_to_sc_chernikova_mulprec(sg);
#else
    abort();
#endif // HAVE_GMP_H
        else
                sc = sg_to_sc_chernikova_fixprec(sg);
 
        return sc;
}

References abort, linear_use_gmp(), sg, and sg_to_sc_chernikova_fixprec().

Referenced by main(), prettyprint_dependence_graph(), and prettyprint_dependence_graph_view().

Here is the call graph for this function:

Here is the caller graph for this function:

sg_to_sc_chernikova_fixprec()

Psysteme sg_to_sc_chernikova_fixprec

(

Ptsg

sg

)

Parameters

sg

g

Definition at line 36 of file chernikova_fixprec.c.

                                              {
        return sc_of_sg(sg);
}

References sc_of_sg(), and sg.

Referenced by sg_to_sc_chernikova().

Here is the call graph for this function:

Here is the caller graph for this function: