forum.polymake.org

Hello everyone! I'm new both to the forum and to polymake, and I have a quick question:

I need to define a polytope in terms of vertices. But both the dimension of the ambient space (R^100 ish) and the number of vertices is huge. Is there a way to import data from, say, a text file? Or can anyone suggest how to go about defining vertices without manually entering them? If I define them with a formula, it will be quite complicated, and I'll have to learn tons of new syntax, which I'm inclined not to do due to both laziness and a very busy schedule.

Thank you.

Hello JQX,

what you can do is the following. Save everything in a file, which looks like the following sample: Every row correspond to one vertex. Please read http://polymake.org/doku.php/tutorial/coordinates in order to understand how the coordinates in polymake work. In a nutshell: The first coordinate of a vertex is always 1, and the first coordinate of a ray is always 0.
Only if you are 100% sure that the points you got are vertices you may replace POINTS by VERTICES.

Then you can load this into polymake by: BUT: here is a warning. As you are operating with many points in large dimension, computations can take very long, and might not finish at all. It is hard to predict if polymake can produce an output. Please see: http://forum.polymake.org/viewtopic.php ... ound#p1051
So do not expect too much. Your problem just might be to hard to compute in your available time and memory.

Code: Select all

polytope> $p = new Polytope(load("path/to/your/file"));

$p=load("..."); suffices.

Polytope<Rational> is the default object type for application polytope.

Well thanks guys for your most useful answers. Much obliged.

Glad we could help. If you encounter any problems, don't hessitate to ask.

One further question:

As a test I'm trying to get the facet description of a polytope in R^81, with about 600 vertices. The computation does not finish after about 5 hours. Now, I know that the polytope is not full dimensional, actually I know that it has dimension 48, so I can reduce the size of the description of the vertices a little bit by working in that subspace. My question is: do you think that would improve the computation time?

As a trivia question: what is the longest time you have seen for a computation which is eventually completed?

Thanks again!

Hi,

the answer is: maybe?!

The problem is that obtaining the projected representation of your vertices might be hard and takes long, and may not be worth it. And besides that the output might be very ugly (very BIG rational numbers, or not even rational). So it may be that looking at the projected coordinates make things worse. But on the other hand the matrices you are working with are smaller so there is a chance that computational time does indeed get better, but I suspect only by a small margin.

But my warning from before is still valid. The Problem is that the number of possible facets gets really really big. So that even listing these wouldn't work. So 5 hours is not very surprising or even considered long in your context. When you don't know anything about the structure of your polytope, the odds are not in your favour. When something finishes in this big input size, you can consider yourself lucky

But there are some pointers I can give you:

• exploid every symmetry you know to reduce the input size
• try different algorithms with the polymake command: prefer "...", where you might use: cdd, lrs, beneath_beyond or ppl. See: http://arxiv.org/abs/1408.4653
• the program lrs has an estimate function (check the lrs manual), where it gives you an estimate on how many facets your polytope has. You might want to run this estimate a couple of times since apperantly it has a high variance.

As for your 'trivia' question:
I think the longest I witnessed for one convex hull computation to finish was ~10 hours over night. But from other people I heared that they waited for days or weeks for a convex hull algorithm to finish until they stopped the computation.