Help with importing lists

Questions and problems about using polymake go here.
JQX
Posts: 5
Joined: 03 Nov 2014, 06:43

Help with importing lists

Postby JQX » 03 Nov 2014, 06:50

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.

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Help with importing lists

Postby assarf » 03 Nov 2014, 09:23

Hello JQX,

what you can do is the following. Save everything in a file, which looks like the following sample:

Code: Select all

POINTS 1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 -1 1 1 1 1 1 1
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:

Code: Select all

polytope> $p = new Polytope(load("path/to/your/file"));
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.
no signature

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: Help with importing lists

Postby gawrilow » 03 Nov 2014, 12:06

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.

JQX
Posts: 5
Joined: 03 Nov 2014, 06:43

Re: Help with importing lists

Postby JQX » 04 Nov 2014, 15:55

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

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Help with importing lists

Postby assarf » 05 Nov 2014, 09:07

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

JQX
Posts: 5
Joined: 03 Nov 2014, 06:43

Re: Help with importing lists

Postby JQX » 08 Nov 2014, 20:58

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!

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Help with importing lists

Postby assarf » 10 Nov 2014, 10:34

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.
no signature


Return to “Helpdesk”