How to deal with large input files

Questions and problems about using polymake go here.

Moderator: Moderators

Jteve
Posts: 7
Joined: 16 Jan 2018, 04:35

How to deal with large input files

Postby Jteve » 16 Jan 2018, 04:58

Dear all,

I would like to read in an input file containing points for which I want polymake to compute the facets as inequalities.

Using the method prescribed at https://polymake.org/doku.php/tutorial/data, I have come up with the following script that runs to completion on small input file sizes.

Code: Select all

use application "polytope"; use vars qw($pts $M $ptope); open($pts, "<polymakepoints.txt") || die "Error : $!"; my $M = new Matrix<Rational>(<$pts>); close($pts); $ptope = new Polytope<Rational>(POINTS=>$M); print_constraints($ptope);
For a large input file, obviously, the above code is likely to run for a long time. I tried this on the attached input file, for instance. This input file has around 200 input points and upward of 400 dimensions. Impressively, polymake is indeed able to compute the facetial representation of these points in about 30 seconds on my machine. There are around 200+ facets, it reports.

I have two specific questions:

(1)During the 30 seconds that this script mentioned above runs, if I press Ctrl C in the terminal window, I get the following:

Code: Select all

^Cpolymake: WARNING: rule POINTED : INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule ppl.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule cdd.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule lrs.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule cdd.convex_hull.canon: POINTED, RAYS, LINEALITY_SPACE : INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule cdd.convex_hull.lineality: LINEALITY_SPACE, POINTED : INPUT_RAYS failed: killed by signal polymake: ERROR: no more rules available to compute 'FACETS | INEQUALITIES'
Should I be worried about these? Or, are these normal when Ctrl C is pressed?

(2)I ended up doing Ctrl C on an input file that was even larger since I had no way of knowing whether polymake was running or it was stuck in an endless loop, etc. (apart from querying the OS which indicated that the process was indeed consuming 100% CPU, but 100% CPU can be consumed even if a process is stuck in an endless loop.) Is there any setting that lets the user know that the current run is 25% complete, 50% complete, etc?

(3)Related to (2), is there any recommended way to terminate a run on computing facets prematurely and still recover the facets computed thus far? For instance, is there any setting that I can add to my script file such that if and when I terminate/interrupt it, polymake dumps all facets it has discovered thus far to an output file? Or, even better, can polymake dynamically and instantaneously update an output facet file as and when it discovers a new facet? This way, if I terminate the run, I still have some facetial representation of the polytope. As of now, if I understand correctly, polymake gives the facets only after all facets are discovered.

Thank you.
Regards.
Attachments
polymakepoints.txt
(162.36 KiB) Downloaded 81 times

User avatar
joswig
Main Author
Posts: 216
Joined: 24 Dec 2010, 11:10

Re: How to deal with large input files

Postby joswig » 16 Jan 2018, 17:41

For a large input file, obviously, the above code is likely to run for a long time. I tried this on the attached input file, for instance. This input file has around 200 input points and upward of 400 dimensions. Impressively, polymake is indeed able to compute the facetial representation of these points in about 30 seconds on my machine. There are around 200+ facets, it reports.
You have been extremely lucky or rather your input has a very special (simple) structure. See also viewtopic.php?f=8&t=522
and viewtopic.php?f=8&t=344 as well as a more comprehensive discussion in https://link.springer.com/article/10.10 ... 016-0104-z.
(1)During the 30 seconds that this script mentioned above runs, if I press Ctrl C in the terminal window, I get the following:

Code: Select all

^Cpolymake: WARNING: rule POINTED : INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule ppl.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule cdd.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule lrs.convex_hull.primal: FACETS, LINEAR_SPAN : RAYS | INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule cdd.convex_hull.canon: POINTED, RAYS, LINEALITY_SPACE : INPUT_RAYS failed: killed by signal ^Cpolymake: WARNING: rule cdd.convex_hull.lineality: LINEALITY_SPACE, POINTED : INPUT_RAYS failed: killed by signal polymake: ERROR: no more rules available to compute 'FACETS | INEQUALITIES'
Should I be worried about these? Or, are these normal when Ctrl C is pressed?
polymake works in a rule based fashion. For some things, like (dual) convex hull computations, there are competing rules. If you kill the execution of one (by pressing ctrl-c) polymake will try the next. What you see here is that polymake informs you about what is going on. So this is perfectly normal.
(2) I ended up doing Ctrl C on an input file that was even larger since I had no way of knowing whether polymake was running or it was stuck in an endless loop, etc. (apart from querying the OS which indicated that the process was indeed consuming 100% CPU, but 100% CPU can be consumed even if a process is stuck in an endless loop.) Is there any setting that lets the user know that the current run is 25% complete, 50% complete, etc?
Essentially no. cdd and lrs do have some means for estimating, which would allow some guessing, but even that will be way off most of the time. Currently, polymake does not support their debug/verbose output, but the next version (3.2), due next week, does.
(3) Related to (2), is there any recommended way to terminate a run on computing facets prematurely and still recover the facets computed thus far? For instance, is there any setting that I can add to my script file such that if and when I terminate/interrupt it, polymake dumps all facets it has discovered thus far to an output file? Or, even better, can polymake dynamically and instantaneously update an output facet file as and when it discovers a new facet? This way, if I terminate the run, I still have some facetial representation of the polytope. As of now, if I understand correctly, polymake gives the facets only after all facets are discovered.
No, for polymake it is essential that all computations are complete and correct. The whole mechanism relies on this. If you are interested in partial (dual) convex hulls for large input, use lrs directly.
http://cgm.cs.mcgill.ca/~avis/C/lrs.html

Jteve
Posts: 7
Joined: 16 Jan 2018, 04:35

Re: How to deal with large input files

Postby Jteve » 16 Jan 2018, 18:06

Hi joswig,

Thanks for your inputs.

On the same input file, with the script as specified (call this the original script), (with no preference), I observed that ppl was used (the terminal window displays this) and it took 30 seconds. (RUN1)

However, when I insisted on lrs by prefer "lrs"; the computation took forever. (RUN2)

So, if I understand correctly, using lrs from within polymake will not suffice for my purposes.

Surprisingly, after I preferred "lrs"; and terminated that run, I removed this line from my script. Then, on rerunning with this script (which is the same as my original script with no "preference"), polymake defaulted to "lrs". This was quite surprising to me since this run should have been same as RUN1 (which defaulted to ppl).

Let me try lrs directly to see if that helps.

Thanks.

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

Re: How to deal with large input files

Postby gawrilow » 16 Jan 2018, 18:33

The command "prefer" stores your choice persistently in ~/.polymake/prefer.pl, therefore it's active in all subsequent sessions. Simply remove this command from the file, or execute

reset_preference "*.convex_hull";

In a script, it's recommended to use prefer_now instead of prefer, this stays valid just for the time of script execution.

User avatar
joswig
Main Author
Posts: 216
Joined: 24 Dec 2010, 11:10

Re: How to deal with large input files

Postby joswig » 17 Jan 2018, 11:37

On the same input file, with the script as specified (call this the original script), (with no preference), I observed that ppl was used (the terminal window displays this) and it took 30 seconds. (RUN1)

However, when I insisted on lrs by prefer "lrs"; the computation took forever. (RUN2)
ppl and lrs implement two distinct algorithms, and they behave quite differently. There is input where ppl is much superior to lrs, but there is also input where it is just the other way around. If you want to learn more about this, please have a look at our paper which I mentioned previously.


Return to “Helpdesk”

cron