March 2002 - PPL-devel - BUGSENG Mailman

Bug in PolyBase::generators() and maybe somewhere else
by Roberto Bagnara 30 Mar '02

30 Mar '02

I have just added a new program, `generators2' to the `tests' directory. It shows a bug in PolyBase::generators() when it is invoked on a polyhedron that is "semantically empty" and not "syntactically empty". The analysis is easy: since generators are not up to date, we invoke update_generators(), which returns false because the polyhedron was found to be empty. We ignore the return value of update_generators() and happily call obtain_sorted_generators()... BOOM! 231 if (!generators_are_up_to_date()) 232 update_generators(); 233 234 // We insist in returning a sorted system of generators. 235 obtain_sorted_generators(); At a first sight, there are other places where the return value of update_generators() is ignored, and this is not a nice thing. Ciao Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

1 0

ppl/interfaces/C ppl_c.cc ppl_c.h
by Roberto Bagnara 30 Mar '02

30 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2002-03-30 10:42:39 Modified files: interfaces/C : ppl_c.cc ppl_c.h Log message: More functions to deal with coefficients. New function to get the type of a generator. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/C/ppl_c.cc.diff?cv… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/C/ppl_c.h.diff?cvs…

1 0

ppl/src PolyBase.inlines.hh
by Roberto Bagnara 30 Mar '02

30 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2002-03-30 10:41:11 Modified files: src : PolyBase.inlines.hh Log message: Added an empty implementation for PolyBase::shrink_bounding_box(). Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/PolyBase.inlines.hh.diff?…

1 0

ppl/tests Makefile.am generators2.cc
by Roberto Bagnara 30 Mar '02

30 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2002-03-30 10:39:48 Modified files: tests : Makefile.am Added files: tests : generators2.cc Log message: New test computing the generators of an empty polyhedron. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/tests/generators2.cc.diff?cvs… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/tests/Makefile.am.diff?cvsroo…

1 0

ppl/interfaces/C ppl_c.cc ppl_c.h
by Roberto Bagnara 30 Mar '02

30 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2002-03-30 09:07:12 Modified files: interfaces/C : ppl_c.cc ppl_c.h Log message: New functions and bug fixes. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/C/ppl_c.cc.diff?cv… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/C/ppl_c.h.diff?cvs…

1 0

Again on NNC minimization.
by Enea Zaffanella 29 Mar '02

29 Mar '02

Hi all. You might have noted that the current implementation of NNC minimization only works starting from generators, meaning that in order to obtain an NNC-minimized set of constraints you have to call once again the (standard) minimize method ... or the update_constraints() method, which is basically the same, since we have generators already minimized. I now think that a _similar_ minimization process can be applied also to constraints, exploiting "a kind of" duality principle, so that it is possible to avoid the second minimization process if ONLY the constraints are needed. I will try and implement such a method, so that we can start doing experiments with it. For the time being, I would like to better explain what I mean when I say "a kind of" duality principle, in order to obtain some feedback from you. Consider an n-dimension-space NNC polyhedron, which is encoded using an (n+1)-dimension-space _closed_ polyhedron. The standard minimization process is representation preserving, meaning that the input (redundant) and output (reduced) systems do represent the same (n+1)-dimension-space closed polyhedron. In contrast, the NNC minimization process, while being "semantic" preserving (i.e., the NNC-redundant and NNC-reduced systems do encode the same n-space-dimension NNC polyhedron), it is not representation preserving, because the NNC-reduced system (in general) will represent a _different_ (n+1)-dimension-space closed polyhedron. This fact has consequences when we do want to be lazy. Consider the following scenario: We have a NNC-polyhedron having only constraints up-to-date and we do want to obtain the NNC-reduced system of generators. We can do the following: 1) update the generators (using the standard algorithm), obtaining as by-product both the sat_c matrix and a minimized con_sys. 2) use the first part of the NNC_minimize() method (i.e., without the last call to minimize()) to compute the NNC-reduced system of generators. At this point we have that: a) both the con_sys and the gen_sys do represent the same NNC-polyhedron b) the gen_sys is NNC-minimized c) the con_sys is minimized, but it might be NNC-redundant d) gen_sys and con_sys might represent DIFFERENT (n+1-space-dim) closed polyhedra. Note in particular points a) and d). This situation could be exploited positively: we could add further status flags to the polyhedron, to remember that the con_sys is both up-to-date and minimized, but it is not NNC-minimized, while the gen_sys is NNC-minimized (which implies the other two). Clearly, we have to be careful with this "partial" misalignment of con_sys and gen_sys ... they are NOT the dual of each other! In particular, in such a situation the saturation matrices will NOT be up-to-date (as far as I can see). So, a first question for Elisa: as things are now, do we ever "assume" that whenever both con_sys and gen_sys are minimized, then the saturation matrices are up-to-date ? (Such an assumption is no longer valid in the scenario above.) Enea.

2 3

ppl src/PolyBase.cc src/PolyBase.defs.hh tests ...
by Enea Zaffanella 29 Mar '02

29 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: zaffanella(a)cs.unipr.it 2002-03-29 14:51:27 Modified files: src : PolyBase.cc PolyBase.defs.hh tests : NNCminimize4.cc Log message: Added methods NNC_minimize_generators() and NNC_minimize_constraints(), which enforce NNC-minimization on only one system. They have a common kernel, which might be factored out in a "generic" NNC-minimization function (something like the simplify() method). Now test NNCminimize4.cc uses the (more lazy) NNC_minimize_constraints() function. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/PolyBase.cc.diff?cvsroot=… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/PolyBase.defs.hh.diff?cvs… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/tests/NNCminimize4.cc.diff?cv…

1 0

ppl/tests Makefile.am NNCminimize4.cc
by Enea Zaffanella 29 Mar '02

29 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: zaffanella(a)cs.unipr.it 2002-03-29 10:14:42 Modified files: tests : Makefile.am Added files: tests : NNCminimize4.cc Log message: New test put under CVS control. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/tests/NNCminimize4.cc.diff?cv… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/tests/Makefile.am.diff?cvsroo…

1 0

ppl/interfaces/C ppl_c.cc ppl_c.h
by Roberto Bagnara 28 Mar '02

28 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2002-03-28 22:08:37 Modified files: interfaces/C : ppl_c.cc ppl_c.h Log message: ppl_Polyhedron_shrink_bounding_box() added to the C interface. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/C/ppl_c.cc.diff?cv… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/C/ppl_c.h.diff?cvs…

1 0

ppl/src Generator.cc Generator.defs.hh Matrix. ...
by Enea Zaffanella 28 Mar '02

28 Mar '02

CVSROOT: /cvs/ppl Module name: ppl Changes by: zaffanella(a)cs.unipr.it 2002-03-28 20:07:47 Modified files: src : Generator.cc Generator.defs.hh Matrix.cc NNC_Polyhedron.cc PolyBase.cc Log message: Added method bool Generator::is_corresponding_closure_point(const Generator&) const; Methods NNC_Polyhedron::is_necessarily_closed() and PolyBase::NNC_minimize() updated to use the above method; this also corrects a bug in the previous implementations. Added a \param Doxygen command in Matrix.cc to avoid a warning. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Generator.cc.diff?cvsroot… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Generator.defs.hh.diff?cv… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/Matrix.cc.diff?cvsroot=pp… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/NNC_Polyhedron.cc.diff?cv… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/src/PolyBase.cc.diff?cvsroot=…

1 0