Make Parma Polyhedra Library a standard spkg

[Volker Braun]

=== Introduction ===

I would like to have the Parma Polyhedra Library (PPL) included
as a standard spkg. My goal is to rewrite as much of the
sage.geometry.* modules on top of a Cython PPL wrapper as opposed
to piping ASCII to/from cddlib. Some of the reasons are:

* PPL is already faster by itself, and having a Cython wrapper reduces
overhead. I'm seeing about 20x speedup on medium-sized problems.

* PPL is the only polyhedral computation toolkit that is from the
ground up designed to be used as a shared library.(1)

* PPL is mature, well tested, has an active development including bug
tracker and mailing list. It is used in a variety of other projects,
including gcc's Graphite loop optimizer. It has been tested on
Linux, FreeBSD, OpenBSD, Solaris, IRIX64, Mac OS X, Cygwin, DEC
OSF/1.

cddlib was the first really useful software package back in the day
and it was hugely influential for many subsequent codes. But nowadays
there are alternatives that combine the same algorithms with better
implementations and software development practices.(2)

Note that I'm not proposing to remove cddlib entirely. It is still a
requirement for gfan and the only program to do polyhedral
computations over floating point numbers.(3)


=== Work Plan ===

I have written a PPL spkg and a Cython (C++) wrapper that should cover
all functions necessary for dealing with polyhedra in Sage. You can
find it here:

http://trac.sagemath.org/sage_trac/ticket/10039

Using this wrapper, I patched sage.geometry.cone:

http://trac.sagemath.org/sage_trac/ticket/10140

I think that the PPL spkg and the Cython wrapper is ready for
inclusion in the next Sage release (4.6.1?). In the subsequent release
we can then rebase sage.geometry modules on top of the wrapper.

Right now I would like to invite any comments on this plan!


=== Notes ===

(1) cddlib also comes with a shared library. But its poorly documented
and, according to valgrind, leaks memory. Other toolkits like lrs and
qhull don't build shared libraries but have minimal instructions for
statically linking with parts of their code.

(2) In particular, cddlib has no bug tracker, no new release in the
last 5 years, and segfaults on some of its own testsuite.

(3) Though in a numerically unstable way, see Trac #10046, #10037.

[Andrey Novoseltsev]

I definitely vote YES.

I often have problems and have to create work-arounds due to Sage poor
performance on (a lot of) *very simple* polyhedra, since both current
options (cddlib and PALP) are used as standalone programs and
therefore add a system call overhead. I actually expect speed ups up
to 100x (and maybe even over!) in this case. Also, I have considered
switching to library calls for PALP, but its documentation is
insufficient and I was not able to dig trough the source code. Plus it
has hard-coded limitations on everything. As with cddlib, I want to
keep PALP in Sage for computing lattice points inside polytopes as
well as nef partitions, but using PPL as a library for computing
convex hulls and facets will make life much better.

Thank you,
Andrey

[Dima Pasechnik]

Yes, it's a good idea to have PPL.
You can start by making it an optional package.

Are you saying that PPL cannot work with floating point numbers?

Dima

[Volker Braun]

On Oct 19, 5:56 am, Dima Pasechnik <dimp...@gmail.com> wrote:
> Are you saying that PPL cannot work with floating point numbers?

The short answer is no. The PPL can work with floating point types for
some upper-approximations of polyhedral regions. But right now the
Cython wrapper only exposes the core functionality for Polyhedra,(1)
which always works with gmp/mpir integers.(2)

(1) Polyhedra can be both closed (defined by <= inequalities) and "not
necessarily closed" (combinations of < and <= inequalities). I don't
know any other polyhedral computation code that can do this, certainly
not cddlib.

(2) Internally all computations are done with mpz_t integers, but
point and closure point coordinates can be specified with an overall
divisor. So, mathematically, the PPL supports polyhedra over QQ.

[Volker Braun]

On Oct 19, 5:35 am, Andrey Novoseltsev <novos...@gmail.com> wrote:
> As with cddlib, I want to
> keep PALP in Sage for computing lattice points inside polytopes as
> well as nef partitions, but using PPL as a library for computing
> convex hulls and facets will make life much better.

Yes, PALP has some useful toric functionality and I think we should
definitely keep it around. But I think the long-term goal should be to
reduce the reliance of the LatticePolytope class on PALP. In
particular, enumerating the lattice points is a problem that pops up
frequently enough that an implementation without the dimension
limitations of PALP would be nice. Did you ever figure out which
algorithm PALP uses? I also looked at the source code but I quickly
gave up...

[mhampton]

I support replacing cddlib with PPL for the default computation of
exact polyhedra.

Eventually I would really like to see lrs as a standard component as
well, because:
1) It is small and compiles on all our supported platforms.
2) David Avis has always been very responsive to any emails about lrs.
3) It uses a very different algorithm from PPL; sometimes it performs
much better, and always with relatively little memory use.
4) It has been an optional package for a couple of years now, with no
known problems.

PPL can be the default, ideally with lrs as an optional backend.

For numerical polytopes we should keep cddlib for now. Qhull might be
the better long-term choice for numerical polytopes, since it was
written from the beginning with that in mind. For now I am working on
Qhull as an optional package (but its not very high on my priority
list).

-Marshall

[Andrey Novoseltsev]

On Oct 19, 4:37 am, Volker Braun <vbraun.n...@gmail.com> wrote:
> Yes, PALP has some useful toric functionality and I think we should
> definitely keep it around. But I think the long-term goal should be to
> reduce the reliance of the LatticePolytope class on PALP. In

> particular enumerating the lattice points is a problem that pops up

> frequently enough that an implementation without the dimension
> limitations of PALP would be nice. Did you ever figure out which
> algorithm PALP uses? I also looked at the source code but I quickly
> gave up...

No, I didn't. Although as far as I know I read all available
documentation on it. I think that so far I needed lattice points only
inside reflexive polytopes in dimension up to 6 and in this case PALP
limitations do not show up. I also didn't have any need to do it for
sequences of polytopes where next elements are computed based on
previous ones, so my work-around (all_points) to eliminate extra
system call overheads was sufficient.

By the way - does PPL use any random numbers like cddlib? I like
referencing polytope vertices/points/facets by their numbers and it
will be impossible if the order can change from session to session. I
don't care about having some specific order - just a fixed one (except
that vertices should be listed in the same way in which they were
given by the user, I think).

[William Stein]

On Tue, Oct 19, 2010 at 6:35 AM, mhampton <hamp...@gmail.com> wrote:

I support replacing cddlib with PPL for the default computation of
exact polyhedra.

Does gfan depend on cddlib?  If we remove cddlib, would we then also have to remove gfan?  From deps:

$(INST)/$(GFAN): $(BASE) $(INST)/$(MPIR) $(INST)/$(CDDLIB)

        $(INSTALL) "$(SAGE_SPKG) $(GFAN) 2>&1" "tee -a $(SAGE_LOGS)/$(GFAN).log"

I would personally be fine with removing gfan, unless some people strongly object.

 

--
To post to this group, send an email to sage-...@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Andrey Novoseltsev]

On Oct 19, 8:53 am, William Stein <wst...@gmail.com> wrote:
> Does gfan depend on cddlib?  If we remove cddlib, would we then also have to
> remove gfan?  From deps:

I'd rather leave cddlib for polyhedra over RDF until there is an
alternative.

[Volker Braun]

On Oct 19, 3:37 pm, Andrey Novoseltsev <novos...@gmail.com> wrote:
> By the way - does PPL use any random numbers like cddlib?

I'm pretty sure that it does not randomize the output; certainly grep
doesn't find any references to rand(). And there is absolutely no
reason to call a pseudo random number generator for the polyhedral
algorithms in the first place.

[Volker Braun]

gfan definitely depends on cddlib.

Unless it is somehow broken I would keep sage.geometry.groebner_fan
and the gfan spkg for now. In the long term we should rewrite
sage.geometry.groebner_fan to work with the new Fan class from the
toric geometry stuff. And I think it would be easy enough to take
Singular's groebner fan code (which uses polymake internally) and
replace its use of cddlib and TOPCOM with Sage's Cone/Fan and
triangulation code. Then we wouldn't need gfan any more...

[David Kirkby]

On 18 October 2010 13:13, Volker Braun <vbrau...@gmail.com> wrote:
> === Introduction ===
>
> I would like to have the Parma Polyhedra Library (PPL) included
> as a standard spkg. My goal is to rewrite as much of the
> sage.geometry.* modules on top of a Cython PPL wrapper as opposed
> to piping ASCII to/from cddlib. Some of the reasons are:
>
> * PPL is already faster by itself, and having a Cython wrapper reduces
>  overhead. I'm seeing about 20x speedup on medium-sized problems.
>
> * PPL is the only polyhedral computation toolkit that is from the
>  ground up designed to be used as a shared library.(1)
>
> * PPL is mature, well tested, has an active development including bug
>  tracker and mailing list. It is used in a variety of other projects,
>  including gcc's Graphite loop optimizer. It has been tested on
>  Linux, FreeBSD, OpenBSD, Solaris, IRIX64, Mac OS X, Cygwin, DEC
>  OSF/1.

From what you say there, it suggests the code is good quality. But I
would suggest an audit is performed and this evaluated. It would be
good to avoid code like that of Sympow and some other packages which
are very dubious.

But my gut feeling is if someone has tested their code on those wide
range of platforms, they have probably done a decent job of writing
it. But I feel this should be ascertained. Potentially they could
assume the use of the GNU linker, which is not good on Solaris.

Does the code generate lots of compiler warnings?

Dave

[Volker Braun]

For reference I've put the buildlog here:

http://www.stp.dias.ie/~vbraun/Sage/spkg/ppl-buildlog.txt

There are two related bogus "may be used uninitialized" warnings,
thats all. Actually the warnings look more like a gcc bug, I think it
should have been able to figure out that the variable does get
initialized in the switch{} statement.

The doxygen-documentation also includes the sources, so its easy to
see the cross-referenced implementation:

https://www.cs.unipr.it/ppl/Documentation/devref/ppl-devref-0.11-html/

In my opinion it is very consistent C++ code and generally easy to
follow with lots of useful comments.

When I compiled it on OpenSolaris I used gcc+sun linker. Since the PPL
buildsystem is using libtool there is some hope that either linker
would work, but then I haven't tried.

[mhampton]

I strongly object to removing gfan.

-Marshall

On Oct 19, 9:53 am, William Stein <wst...@gmail.com> wrote:

> > sage-devel+...@googlegroups.com<sage-devel%2Bunsu...@googlegroups.com>

[mhampton]

Gfan does a lot more than compute the Groebner fan. My main use for
it is computing tropical prevarieties. Anders Jensen keeps improving
gfan, and in fact our interface to it doesn't wrap all the current
functionality. I think it would be quite a job to replace it.

-Marshall