Is this the fastest way to compute the Betti numbers ?

[CharlesArnal]

Dear all,

I have a program in which I start with a triangulation of an n-dimensional simplex - for now, the triangulation is defined using a list of monomials and a list of coefficients. I also have a (long) list of signs distributions on the vertices of that triangulation. For each signs distribution, I want to compute the Betti numbers of the associated patchworked hypersurface.

In other words, it looks something like this :

Code: Select all

my $my_monomials = ...; my @my_coeffs = ...; my $h1 = new Hypersurface<Min>(MONOMIALS=>$my_monomials, COEFFICIENTS=>@my_coeffs); my @Betti_num_array=(); # I get my signs distributions from a file open(INPUT, "<", "$ARGV[0]/$ARGV[1]"); while(<INPUT>){ push(@Betti_num_array,$h1->PATCHWORK(SIGNS=>$_)->BETTI_NUMBERS_Z2); }

Considering that I need to compute the Betti numbers corresponding to a very large number of signs distributions (but always with the same initial triangulation), is there any way to make this faster ?
For example, I understand that polymake uses production rules to compute new properties, and I thought there might be some intermediate property that would depend only on the triangulation (and not on the signs) that I could compute once beforehand to save some time, or maybe some more low-level optimization trick.

Note that I am not complaining, I am already very impressed with polymake's performance.

Best regards and thanks in advance,

Charles Arnal

[joswig]

Indeed, the triangulation (induced by MONOMIALS and COEFFICIENTS) is the same. Yet your code already exploits this automatically.

The property PATCHWORK is declared multiple (see apps/tropical/rules/patchwork.rules) which means that all the patchworks for all your choices of signs will be kept. Probably this will be eating up a lot of memory (please check that). If the memory suffices then there is no direct way of making things faster.

If you should suffer from swapping then you should get rid of those patchworks which you do not need any more. Then you can do, e.g.,

Code: Select all

$h1->remove("PATCHWORK");

after your push statement.

What are your parameters and timings?

[CharlesArnal]

Thanks a lot for your answer.

1) adding "$h1->remove("PATCHWORK");" actually made a huge difference - it made my code about 5 times faster. Thank you very much, this is great !

2) If by parameters you mean the kind of experiments I am running or the kind of computer I am using, I am currently computing Betti numbers for a few hundred thousands hypersurfaces defined by polynomials in 2 or 3 variables and of degree ~10 on my laptop, which takes ~30mn, but I should soon move on to larger problems on my institute's cluster.

3) I knew the triangulation was the same (and that I was only computing it once) - what I meant was that there could have been another property that would be "closer" to the Betti numbers than the triangulation itself, yet would only depend on the triangulation, and hence could have been computed before the loop to save time (I don't see any geometric/mathematical object that would fit this description, but I don't know the inner workings of polymake and didn't want to exclude the possibility). (This clarification is not particularly useful, but I wouldn't want you to think I am completely dumb).

[joswig]

polymake thinks of objects (here tropical::Hypersurface) as a list of properties (each of which comes with a type). There are defining properties (here MONOMIALS and COEFFICIENTS) which just specify what it is that you are talking about.

Then there are derived properties (such as, e.g., the dimension of the tropical hypersurface, the triangulation induced by monomials and coefficients etc); full list of all properties for tropical::Hypersurface. Once computed these are kept throughout, automatically; overview of the mechanism behind that. You can kill them though, with remove (as shown before), if they eat up too much space.

Some "properties" are special in that they are not the result of any computation but rather additional data. Your PATCHWORK is an example. Actually, this is a big object type, which means that the PATCHWORK has its own properties, subject to rules, just like tropical::Hypersurface. But you can have any number of those (since that property is declared multiple).

Another example of the same kind is the LP property for polytope::Polytope. The polytope is the feasible region of a linear program, but the actual objective function is stored is a (multiple) subobject of type LinearProgram; the latter only has the objective function and everything which depends on it.

Long story short: polymake's rule basis knows where which property belongs. So whatever only depends on the tropical hypersurface is automatically stored there and computed only once. When you kill a PATCHWORK, then only the stuff which belongs to that particular patchwork goes away. So polymake, just by itself, probably does exactly what you want.

[CharlesArnal]

Great ! Thanks for the explanation.