August 2004 - PPL-devel - BUGSENG Mailman

Re: Benchmarks for PPL 0.5 -> 0.61
by Roberto Bagnara 30 Aug '04

30 Aug '04

Goran Frehse wrote: > I just tried the new PPL with some examples. > Here are some numbers taken from a reachability analysis of a hybrid automaton: (PPL 0.5 -> PPL 0.61) > > - Remapping and Intersection of 1249 3--6-dimensional polyhedra: > 1.26s -> 0.85s > - Remapping and Intersection of 1341 2--4-dimensional polyhedra: > 1.64s -> 1.45s > - Reachability analysis in 3-dimensional space > (roughly 10000 intersections and projections in 6--3 dimensions): > 57.31s -> 55.87s > > I'm very happy with these results, so congratulations! On behalf of all the developers: Thank you! If you care about (time and memory) performance, whatch out for PPL 0.7. Cheers, 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

PowerSet operations (Was: Re: Compiling PPL under Cygwin?)
by Roberto Bagnara 30 Aug '04

30 Aug '04

Goran Frehse wrote: > congratulations on the new version. I will try it asap, and I'm > particularly excited about the faster map_dimensions routine. Hello Goran, yes, the speedup for map_dimensions() is significant. > If I understand correctly, the PowerSets are finite unions of polyhedra, > so I guess I could use those instead of my own implementation. We'll see > who's are faster ;-) But seriously, this is great. They are finite sets of polyhedra that are non-redundant. This means that a powerset cannot contain the empty polyhedron or two polyhedra that are one the subset of the other. > Do you plan to implement all boolean operations (union, intersection, > difference)? Here I am not sure I understand your needs, that is, if you need something like std::set<C_Polyhedron, ...> or what we call Polyhedra_PowerSet. In the first case, a strict weak ordering is required, and this is not available (any idea on how to realize it efficiently is very welcome). In the latter case, we have void upper_bound_assign(const PowerSet& y); that computes the union, then it eliminates the redundant elements. We have void meet_assign(const PowerSet& y); (which we may rename before the next release) that computes all the intersections of a polyhedron from *this with a polyhedron from y, then it eliminates the redundant elements from the collection so obtained. Difference has still to be implemented: it will compute a non-redundant set of polyhedra such that their union is the difference of the unions of the polyhedra contained in its arguments. Are these the operations you need? All the best, 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 TODO
by Roberto Bagnara 30 Aug '04

30 Aug '04

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2004-08-30 23:27:46 Modified files: . : TODO Log message: Three more things to do. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/TODO.diff?cvsroot=ppl&r1=1.85…

1 0

ppl TODO
by Roberto Bagnara 30 Aug '04

30 Aug '04

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2004-08-30 23:24:18 Modified files: . : TODO Log message: Added several new things to be done. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/TODO.diff?cvsroot=ppl&r1=1.84…

1 0

ppl/demos/ppl_lcdd/examples README
by Roberto Bagnara 30 Aug '04

30 Aug '04

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2004-08-30 21:59:12 Added files: demos/ppl_lcdd/examples: README Log message: Explain and give pointers to the origins of these examples. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/demos/ppl_lcdd/examples/READM…

1 0

ppl/doc devref-browse.doxyconf-latex.in devref ...
by Enea Zaffanella 30 Aug '04

30 Aug '04

CVSROOT: /cvs/ppl Module name: ppl Changes by: zaffanella(a)cs.unipr.it 2004-08-30 16:34:19 Modified files: doc : devref-browse.doxyconf-latex.in devref-print.doxyconf-latex.in devref.doxyconf-html.in user-browse.doxyconf-latex.in user-print.doxyconf-latex.in user.doxyconf-html.in Log message: Updated to the latest doxygen version (1.3.8). Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref-browse.doxyconf-la… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref-print.doxyconf-lat… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref.doxyconf-html.in.d… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/user-browse.doxyconf-late… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/user-print.doxyconf-latex… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/user.doxyconf-html.in.dif…

1 0

w3ppl/htdocs/Links Links.raw
by Roberto Bagnara 29 Aug '04

29 Aug '04

CVSROOT: /cvs/ppl Module name: w3ppl Changes by: roberto(a)cs.unipr.it 2004-08-29 20:20:33 Modified files: htdocs/Links : Links.raw Log message: Added a link to pd: an implementation of a primal-dual algorithm for vertex and facet enumeration. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/w3ppl/htdocs/Links/Links.raw.diff…

1 0

[Fwd: Benchmarks for PPL 0.5 -> 0.61]
by Roberto Bagnara 29 Aug '04

29 Aug '04

-------- Original Message -------- Subject: Benchmarks for PPL 0.5 -> 0.61 Date: Fri, 27 Aug 2004 15:11:58 -0400 (EDT) From: Goran Frehse <gfrehse(a)andrew.cmu.edu> To: Roberto Bagnara <bagnara(a)cs.unipr.it> References: <402A51EB.60609(a)andrew.cmu.edu> <402AA44B.2010702(a)cs.unipr.it> <402A77E8.2000907(a)andrew.cmu.edu> <41249897.9060800(a)cs.unipr.it> Dear Roberto, I just tried the new PPL with some examples. Here are some numbers taken from a reachability analysis of a hybrid automaton: (PPL 0.5 -> PPL 0.61) - Remapping and Intersection of 1249 3--6-dimensional polyhedra: 1.26s -> 0.85s - Remapping and Intersection of 1341 2--4-dimensional polyhedra: 1.64s -> 1.45s - Reachability analysis in 3-dimensional space (roughly 10000 intersections and projections in 6--3 dimensions): 57.31s -> 55.87s I'm very happy with these results, so congratulations! Best wishes, Goran -- 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

[Fwd: Re: [PPL-devel] Compiling PPL under Cygwin?]
by Roberto Bagnara 29 Aug '04

29 Aug '04

-------- Original Message -------- Subject: Re: [PPL-devel] Compiling PPL under Cygwin? Date: Wed, 25 Aug 2004 16:52:28 -0400 From: Goran Frehse <gfrehse(a)ece.cmu.edu> To: Roberto Bagnara <bagnara(a)cs.unipr.it> References: <402A51EB.60609(a)andrew.cmu.edu> <402AA44B.2010702(a)cs.unipr.it> <402A77E8.2000907(a)andrew.cmu.edu> <41249897.9060800(a)cs.unipr.it> Dear Roberto, congratulations on the new version. I will try it asap, and I'm particularly excited about the faster map_dimensions routine. If I understand correctly, the PowerSets are finite unions of polyhedra, so I guess I could use those instead of my own implementation. We'll see who's are faster ;-) But seriously, this is great. Do you plan to implement all boolean operations (union, intersection, difference)? Thanks for trying out the Cygwin installation. These are good news. Best wishes, Goran Roberto Bagnara wrote: > Goran Frehse wrote: > >> Actually I just noticed that somebody answered my request in the >> Cygwin mailing list about this. It turns out that the paths in the .la >> files are wrong and must be corrected by hand in the current >> installation. >> For details, see: >> http://cygwin.com/ml/cygwin/2004-02/msg00304.html > > > Dear Goran, > > I have just tried a fresh installation of GMP 4.1.3 and PPL 0.6 > (just released) on the latest Cygwin distribution. I followed > exactly the same procedure I follow on GNU/Linux systems > and it worked immediately. I take this as an indication that > the problems you experienced some time ago have been solved. > All the best, > > 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/doc devref-browse.doxyconf-latex.in devref ...
by Roberto Bagnara 28 Aug '04

28 Aug '04

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2004-08-28 22:11:00 Modified files: doc : devref-browse.doxyconf-latex.in devref-print.doxyconf-latex.in devref.doxyconf-html.in Log message: Replaced globals.hh with globals.defs.hh and globals.inlines.hh. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref-browse.doxyconf-la… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref-print.doxyconf-lat… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/doc/devref.doxyconf-html.in.d…

1 0