[Re] [Ten Year Challenge] Volume computation for polytopes: Vingt ans après

[ghost]

Original article: B. Büeler, A. Enge, and K. Fukuda. Exact Volume Computation for Polytopes: A Practical Study. In: Polytopes — Combinatorics and Computation. Ed. by G. Kalai and G. M. Ziegler. Vol. 29. DMV Seminar. Basel: Birkhäuser Verlag, 2000, pp. 131–154

PDF URL:
https://gitlab.inria.fr/enge/revinci/-/blob/master/article/revinci.pdf

Metadata URL: https://gitlab.inria.fr/enge/revinci/-/blob/master/article/metadata.yaml

Code URL:
https://gitlab.inria.fr/enge/revinci/-/tree/master/code

Data URL: https://gitlab.inria.fr/enge/revinci/-/tree/master/data

Scientific domain: Discrete Mathematics

Programming language: C

Suggested editor:
None of the editors seems to be from this field; potential reviewers from the current list are Markus Pfeiffer, Dmitrii Pasechnik and Bruno Levy, with whom I have no conflict of interest.

[rougier]

Thanks for your submission. We'll assign an editor soon (hopefully).

@ThomasA Could you edit this submission for the Ten Years Reproducibility Challenge (only 1 reviewer needed). I know it's not your domain but @andreas-enge suggested some reviewer names that might review this submission.

[ThomasA]

Sorry @rougier, for some reason I did not notice this comment until now. I suppose I can edit this submission, but my C is a bit rusty and I have only ever briefly heard of polytopes...

[rougier]

Well actually, you only need to find a (single) reviewer to do the actual review and your role is mostly to guarantee the process goes smoothly. I'll help you with the publication process at the end if necessary.

[rougier]

@ThomasA Gentle reminder (You only need to assign one reviewer at this stage)

[rougier]

@ThomasA Gentle reminder

[ThomasA]

Sorry, sorry. These GitHub notifications have been flooding my inbox all spring and I have not been diligent enough about sifting through them for mentions of me :see_no_evil: I will get right on it.

[ThomasA]

@markuspf, @dimpase, or @BrunoLevy can one of you review this submission?

[dimpase]

I am on it.

[dimpase]

Can I point this out to a colleague, too? I understand that all this happens in the open, right?

[ThomasA]

Thanks a lot. It is OK to let your colleague in on it as well. The review process is open.

[dimpase]

It seems that --- otherwise very nicely written --- article lacks clear instructions on how to reproduce the computations (short of installing guix - is this what the author kept in mind?)

It explains in great length how the author went about reproducing the computations himself, but shouldn't the referee (or any reader, in fact) be able to reproduce the reproduced easily?

[khinsen]

@dimpase You raise an interesting question that we didn't really discuss in the guidelines for the challenge. In principle, you are right: the idea is that everything published in ReScience C should be "easily" reproducible by anyone. But what does "easily" mean in practice? All software has dependencies, and those are rarely available out of the box on all modern computing platforms. So reproducing a computation is always easier for readers who use the same platform as the author. This reproduction has Guix as a dependency. If you have Guix, reproduction is easy. Otherwise... it's as hard as installing Guix first. And that can be tough, e.g. if you are starting from Windows. So... I have no good answer.

[ghost]

Hello, I am new to this open referee process, so I am not sure if it is appropriate for the author to react immediately. If it is, here are some explanations:

Indeed I am also showing how to redo the computations with Guix (section 2.3), but I agree with Dima that this may not help the reader install the software (if they have Guix, yes, otherwise, no). Also it is cheating, since I added the needed software to Guix when preparing the Ten Years Challenge submission.

But there is all of section 2.2 that explains how to do things "by hand" from the source. It should be possible to just follow all the steps given in the lines of shell starting with "$"; they include calls to wget, tar, and even cd and so on; and after writing the paper, I went once again through the process to make sure it works, so I hope there is no error left. Then there are two simple patches also given explicitly that need to be applied to compile the helper software. (Of course this assumes a GNU/Linux machine; all source code is C, so I suppose it can be made to work on other platforms, but I did not test this at all; and I do not think that porting software is the goal of reproduction.)

Now if this approach gets lost in the paper, there must be a problem with my structure or formulations - too much flourish in the section headings? too much discussion of history? I would be grateful about suggestions why the paper is not clear enough.

[ThomasA]

Interesting aspects are being discussed here. I would say: as long as it reproduces the original experiment, anything goes. The purpose is to show what it took to get there. Now I will go through the paper as well to see how the process is described. I have not had time to do that until now. @andreas-enge I think it is fine for you as author to weigh in here with your clarfications on how things were done.

[dimpase]

I'd still be curious on what happens if the up-to-date components are used in a reproduction attempt.

[ThomasA]

@dimpase do you mean what the computational performance is of the first attempt, described in Section 2.1?

[dimpase]

I mean an extra effort going into getting old versions of everything, e.g. lrslib - why would I try that if its up to date version is already installed on my system?

[ThomasA]

Sorry, summer de-railed me. I am now back, let's get this one handled... IMO it is relevant to attempt to get as close as possible to the original software versions since actual runtime performance is a major part of the original scientific results. For that reason, never versions of the software might have a significant impact on the performance in addition to the impact that newer hardware already has.

[ThomasA]

I'd still be curious on what happens if the up-to-date components are used in a reproduction attempt.

That is definitely also interesting @dimpase, but I think the currently described reproduction is what gets closest to the original and thus is best aligned with the spirit of the special issue. It think it would go too far to require @andreas-enge to do both. @khinsen what is your take on this?

[dimpase]

Essentially, the only thing I am still puzzled with here is Guix package described in the paper. I presume vinci package would use up to date dependencies, such as lrslib. Thus, it appears that vinci is present in Guix with the up-to day deps (and not only via Guix time-machine feature, cf. p 9) but the paper is silent on how it fares against the historic version.

[ThomasA]

Perhaps @andreas-enge can clarify this?

[khinsen]

@ThomasA The central question of the ten-year challenge is "can you get your old code to run?" From that perspective, staying as close as possible to the original work is indeed the best approach. But in the end, it's the authors' decision how they proceed, as long as they present their strategy clearly. The approach chosen by @andreas-enge looks perfectly fine to me.

The last question by @dimpase is relevant however: it should be clear from the article which versions of all dependencies were actually used. Hint to @andreas-enge : I wrote a Guile script for listing the complete dependencies of a set of packages in Guix, with version numbers. There's also a blog post that explains how it works.

[ghost]

Hello @khinsen, @dimpase, @ThomasA,

to quickly summarise: For me, the core of the reproduction experiment is Section 2.2, which explains in detail (with command line snippets) how to install the as original as possible software from source. The first sentence of Section 3 states that this is how the numerical results of Table 7 are obtained, which is the basis for the comparison with the original Table 1. So Guix does not intervene in the computations at all.

Section 2.3 on Guix is more of an afterthought. I have not carried out the computations with the Guix version, and I do not expect them to be different. Vinci itself has evolved a bit, but not very much (I left this field of research after writing the software); mainly I have taken out algorithms that were numerically unstable. The lrslib dependency changed, but it is not used in many places in vinci - just as one particular volume computation method to compute the first column of Table 7, and hereby the computation is completely outsourced (by a system call and parsing the result of the lrs file output); and for the last two columns about transformation of the polytope description, which is not directly related to volume computation.

I suggest to redo at least part of the computation with Guix and check whether this guess is correct, then report back here. If my hunch is correct, this could translate into a single sentence in the paper of the kind "The results are essentially the same with the version packaged in Guix as explained in Section 2.3".

[dimpase]

Thanks Andreas, I would be happy to see the result of the suggested Guix experiment added.

[ThomasA]

Thanks @andreas-enge, let us do it this way.

[ghost]

It turns out that the Guix approach is not all that relevant after all. The latest version of vinci, that I added to Guix (there was no real point in packaging older versions besides for this challenge), contains improvements to data structures; the ChangeLog states that this has made some volume computation algorithms "noticeably faster on near-simple input", which I also noticed on some examples (with a factor of about 3). Lrslib in its latest version (I upgraded to 7.1, released in June), is considerably faster than the code from 20 years ago (a factor of about 3 to 8 on the examples I tried). So if you really want to do volume computation or polytope conversion, you should definitely use the latest releases of all software!

However, for this challenge I think the point is to redo the same experiments as in the past, and not to redo the same kind of computation with more modern and improved software.

So I would suggest to drop section 2.3 on Guix, as it is finally irrelevant to the topic of the paper (and causes confusion). What do you think?

[dimpase]

Dropping 2.3 would lead to a natural question: is vinci alive in any form (it is, it lives on in Guix - a by-product of the work done on this text)? So it should be kept in some way.

[ghost]

Hello,

On Mon, Aug 31, 2020 at 03:05:05AM -0700, Dima Pasechnik wrote:

Dropping 2.3 would lead to a natural question: is vinci alive in any form (it is, it lives on in Guix - a by-product of the work done on this text)? So it should be kept in some way.

in the end I opted for adding material...

I added the old versions used for the reproducibility challenge to the guix-past channel, and explained in 2.3 how to use the channel. So 2.3 now explains how to either use standard Guix with the most up-to-date versions (that will lead to faster running times; and yes, this article motivated me to add them to Guix), or how to redo the computations with the old versions without going through the hand-compilation described in 2.2.

Then it was natural to also update 2.2: I reused as patches the unified diffs as required by the Guix recipes in guix-past, while previously I opted for shorter, simple diffs. I also added a few commands (some more "make" or "cd", essentially) to the shell script snippets. Now if a user copy-pastes all the lines starting with "$" into a shell, they should end up with correctly patched and compiled software as I used them for recomputing the running times table.

This approach provides some more options to simplify reproducing my reproduction of the original experiment :), so I hope it will be a useful addition.

Everything, including a compiled pdf, is pushed to my submission repo https://gitlab.inria.fr/enge/revinci

Andreas

[ThomasA]

Thanks @andreas-enge. Does this mean that there is now a reasonably complete procedure to "reprocude the reproduction" either with new or old libraries and with or without Guix? I am going to read the update today and get back to you.

[ghost]

On Mon, Sep 21, 2020 at 01:31:09AM -0700, Thomas Arildsen wrote:

Thanks @andreas-enge. Does this mean that there is now a reasonably complete procedure to "reprocude the reproduction" either with new or old libraries and with or without Guix?

I hope so! It should be easily possible to follow the approach with old libraries as described with or without Guix.

Alternatively I mention that you can also use newer versions with Guix (and of course also by compiling everything by hand, supposedly with fewer patches); but I do not consider this to be the point of the article, so am rather brief about it.

Thanks,

Andreas

[ThomasA]

Thanks for your patience. I conclude that the paper can be accepted. I will now go through the steps of preparing publication of the paper. @andreas-enge I will send you a pull request against your repository with an updated file 'metadata.yaml'. When you update your final paper accordingly, can you please update your "TODO" URLs in the paper?

[dimpase]

yes, I agree, thanks, and sorry for sitting on it for longer than needed.

[ThomasA]

@dimpase no worries, you were not the only one :blush:

[ThomasA]

@andreas-enge I have updated the article metadata. I cannot create a pull request for you since I do not have an account on https://gitlab.inria.fr. I have created a "fork" at https://github.com/ThomasA/revinci where you can pull the change from.

[rougier]

@andreas-enge @ThomasA Any progress ?

[ghost]

Hello, Thomas and Dima,

On Tue, Nov 03, 2020 at 11:18:50AM -0800, Thomas Arildsen wrote:

Thanks for your patience. I conclude that the paper can be accepted.

thanks for your patience, and the good news! Sorry for being slow, there were too many deadlines over the past weeks.

I am not familiar yet with the technical workflow for publication; in any case, I will work on updating the TODO, moving code and data to a permanent repository and so on on my side.

On Tue, Nov 03, 2020 at 12:21:31PM -0800, Thomas Arildsen wrote:

@andreas-enge I have updated the article metadata. I cannot create a pull request for you since I do not have an account on https://gitlab.inria.fr. I have created a "fork" at https://github.com/ThomasA/revinci where you can pull the change from.

This is an annoying newly introduced "feature" of our gitlab instance; if useful, I can also send you an invitation later on. For the time being, I will simply apply your patch.

One more question: I would like to add a dedication (of about a line and a half), but did not see any way to do so besides as a fake date.

Thanks,

Andreas

[ThomasA]

Hello @andreas-enge, Great to hear that we are now able to close the publication. I am not familiar enough with the paper template to know what the most suitable "feature" is for a dedication. @rougier @khinsen, do you know? Otherwise, I will also try to look closer into the template. I hear there are some minor technical complications with the metadata file. We will just deal with the technicalities outside this forum and report back here when it is done.

[ThomasA]

@andreas-enge putting the dedication in the date field causes it to be typeset in a rather large font. I am not sure this is desirable. It can be tweaked by prefixing a \small or similar, but still... @rougier @khinsen would it be better to add a dedication for example at the end of the abstract?

[ThomasA]

@rougier @khinsen by the way, what is the policy on the date displayed in the article? @andreas-enge here wrote the date, probably when he last edited the paper, using \date in the LaTeX template. Should the \date command even be used at all? Checking some of the other published papers from the challenge, it seems the date should not be there. I can no longer find the author instructions for the Ten Year Reproducibility Challenge to check there: http://rescience.github.io/ten-years/ten-years-author-guidelines.md

[ghost]

On Thu, Nov 26, 2020 at 11:03:07AM +0000, Thomas Arildsen wrote:

@rougier @khinsen would it be better to add a dedication for example at the end of the abstract?

It would be nice if it were a bit more prominent, but if there already is a precedent, I am of course happy to follow it.

Independently, I have the impression that the abstract is not printed in the pdf, but only on the website?

Andreas

[khinsen]

I'd put a dedication at the end of the abstract or as the first paragraph of the main text. In other words, there is no special feature in the template for that, as far as I know.

[rougier]

Yes, we're not too rigid about the template (as long as my eyes are not bleeding). For the different date (submitted/ccepted published), we extracted them from the metadata file. For other dates, not sure what would be the best way. @andreas-enge If you want to insert the dedication just after the astract that might be doable. Best would be probably to modify the template in your repo.

[ghost]

On Sat, Nov 28, 2020 at 03:55:58AM -0800, Nicolas P. Rougier wrote:

Yes, we're not too rigid about the template (as long as my eyes are not bleeding). For the different date (submitted/ccepted published), we extracted them from the metadata file. For other dates, not sure what would be the best way. @andreas-enge If you want to insert the dedication just after the astract that might be doable. Best would be probably to modify the template in your repo.

Thanks for your suggestions! I ended up putting the dedication just into my text, before the first \section, and it appears in the right place, between abstract and content.

Andreas

[ThomasA]

The publication process has now been completed and all that remains is for someone to merge https://github.com/ReScience/articles/tree/10.5281_zenodo.4242972 in. Thanks for your contributions @andreas-enge and @dimpase.

[rougier]

Merged and online. Congratulations @andreas-enge

[ghost]

Many thanks to @ThomasA, @dimpase, @khinsen and @rougier! This has been a pleasant adventure, giving the impression of taking part in the future of publication, and I have learnt many new things.

Andreas