Computer Science – Symbolic Computation
Scientific paper
2011-08-30
Computer Science
Symbolic Computation
15 pages, 4 figures, 2 tables. In proceedings of SoCG 2012
Scientific paper
We develop an incremental algorithm to compute the Newton polytope of the resultant, aka resultant polytope, or its projection along a given direction. The resultant is fundamental in algebraic elimination and in implicitization of parametric hypersurfaces. Our algorithm exactly computes vertex- and halfspace-representations of the desired polytope using an oracle producing resultant vertices in a given direction. It is output-sensitive as it uses one oracle call per vertex. We overcome the bottleneck of determinantal predicates by hashing, thus accelerating execution from 18 to 100 times. We implement our algorithm using the experimental CGAL package triangulation. A variant of the algorithm computes successively tighter inner and outer approximations: when these polytopes have, respectively, 90% and 105% of the true volume, runtime is reduced up to 25 times. Our method computes instances of 5-, 6- or 7-dimensional polytopes with 35K, 23K or 500 vertices, resp., within 2hr. Compared to tropical geometry software, ours is faster up to dimension 5 or 6, and competitive in higher dimensions.
Emiris Ioannis Z.
Fisikopoulos Vissarion
Konaxis Christos
Peñaranda Luis
No associations
LandOfFree
An output-sensitive algorithm for computing projections of resultant polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An output-sensitive algorithm for computing projections of resultant polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An output-sensitive algorithm for computing projections of resultant polytopes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-729078