zn_poly removal

[mjo]

The zn_poly SPKG is used by sage in only one place. In hypellfrob.cpp's interval_products_wrapper(), there is a case...

if (!force_ntl  &&  modulus <= (1UL << (ULONG_BITS - 1)) - 1)
{
   // Small modulus; let's try using zn_poly if we're allowed.
   ...

But sometimes that fails, and the fallback is to use NTL anyway. The zn_poly project was abandoned upstream in 2008:

​https://web.maths.unsw.edu.au/~davidharvey/code/zn_poly/index.html

We've forked it to keep it building on modern systems,

​https://gitlab.com/sagemath/zn_poly

but the build system is still a mess. Erik started an autotools branch (​https://gitlab.com/sagemath/zn_poly/-/tree/autotooling), but it never got finished, because the source layout is a bit weird for autotools and it should most likely be redone from scratch.

And zn_poly is not packaged in Gentoo because of how many hacks it still requires to build on a distro with stronger user experience expectations:

​https://github.com/cschwan/sage-on-gentoo/blob/master/sci-libs/zn_poly/zn_poly-0.9.2.ebuild

In short, we're not getting a lot of benefit out of zn_poly these days, and nothing breaks if we remove it, because the one function that uses it falls back to the more-reliable NTL anyway.

In this ticket we remove the zn_poly SPKG, to avoid having to rewrite its build system some day.

[mjo]

Last 10 new commits:

​3e055e3	Trac #32841: remove zn_poly from the library order.
​3e19fe9	Trac #32841: remove zn_poly dependency from sagelib.
​f9c6481	Trac #32841: remove the zn_poly SPKG.
​c7a6fe2	Trac #32841: use zlib instead of zn_poly in a sage-package comment.
​209ef4c	Trac #32841: use zlib instead of zn_poly in package list examples.
​ca1bdaf	Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
​c8bf248	Trac #32841: remove zn_poly section from COPYING.txt.
​a6e61d5	Trac #32841: remove mentions of zn_poly from README.md.
​cd0d40f	Trac #32841: remove zn_poly mention from a thematic tutorial.
​8fc2403	Trac #32841: don't mention zn_poly in flint header comments.

[roed]

There's a discussion on sage-devel about how much/whether we're giving up speed by switching from zn_poly to NTL. I'd like to do some benchmarking before removing this package.

[mjo]

No problem, I'm not in a hurry.

Is it even possible to hit the zn_poly branch from within the normal sage user interface? The only call to interval_products_wrapper() I see (before or after this branch) passes force_ntl=1. You could still conceivably call it directly from within your own library, though.

[roed]

Yes. Line 257 of ​hypellfrob.pyx calls hypellfrob_matrix, which has force_ntl=0 ​by default. This function is called various places: matrix_of_frobenius in sage.schemes.elliptic_curves.padics, frobenius_matrix and count_points in sage.schemes.hyperelliptic_curves.hyperelliptic_finite_field.py.

[mjo]

Replying to roed:

Yes...

Ah, I didn't see matrix() at the bottom of hypellfrob.h. Ok. Do you have a plan for benchmarking? I can throw random inputs at it but I don't want to unfairly bias the results with poor choices for test cases.

[cremona]

Has anyone asked David Harvey about this?

[mjo]

Replying to cremona:

Has anyone asked David Harvey about this?

No, but his webpage is pretty clear:

Current status

zn_poly is no longer maintained.

It's maintained by the sage team and essentially has been (via patches) for over a decade. With all due respect, if he's not going to help maintain the code, what can his opinion change?

If there's a huge performance regression (I'll need help with realistic test cases that don't make zn_poly fail and fall back to NTL unusually often), then we'll have to keep it around until NTL gets faster. But otherwise, the decision whether to keep it for nostalgia's sake alone should rest with the people who are going to have to maintain it.

[mjo]

I've been throwing examples at this for an hour or so. I've hacked my local tree to make hypellfrob take a force_ntl parameter, and to alert me when zn_poly fails and falls back to NTL. I've been picking my p,Q,N by hand for lack of a better approach.

I'll cut to the chase: the biggest difference between the two in favor of zn_poly is on the order of...

sage: %timeit hypellfrob(p, 3, f, force_ntl=False)
864 ms ± 5.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit hypellfrob(p, 3, f, force_ntl=True)
1.2 s ± 5.06 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Typically, they're a bit closer together, with zn_poly having a slight edge. And when zn_poly fails, of course, the NTL-only strategy wins by a huge margin (however long it takes zn_poly to fail).

So the question is, is a slowdown like this (for the cases that zn_poly can handle) a deal-breaker, considering the improvement in the cases it cannot?

[mkoeppe]

My suggestion would be to downgrade zn_poly to "experimental" and to change the defaults to the code path that does not use it, but to still keep the code that calls zn_poly for a little while as an option. Instead of force_ntl, how about an algorithm parameter, similar to what many other functions accept.

[mjo]

Replying to mkoeppe:

My suggestion would be to downgrade zn_poly to "experimental" and to change the defaults to the code path that does not use it, but to still keep the code that calls zn_poly for a little while as an option. Instead of force_ntl, how about an algorithm parameter, similar to what many other functions accept.

I'm willing to do this, but first, can I selfishly request at least one user come forward who would actually use it?

[roed]

As one of the people who initially requested a speed comparison, I'm content with the removal of zn_poly rather than making mjo put the work into making it experimental. I think that the speed difference is not worth the maintenance burden.

I'll check with Alex to see if he agrees, and then am happy to review this.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​8defe99	Trac #32841: remove zn_poly from the library order.
​6525bda	Trac #32841: remove zn_poly dependency from sagelib.
​be482a3	Trac #32841: remove the zn_poly SPKG.
​9c9344b	Trac #32841: use zlib instead of zn_poly in a sage-package comment.
​d4c75e9	Trac #32841: use zlib instead of zn_poly in package list examples.
​c14762d	Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
​d393f7b	Trac #32841: remove zn_poly section from COPYING.txt.
​fc63ad7	Trac #32841: remove mentions of zn_poly from README.md.
​78841ee	Trac #32841: remove zn_poly mention from a thematic tutorial.
​b0de396	Trac #32841: don't mention zn_poly in flint header comments.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​bc4829d	Trac #32841: remove zn_poly from the library order.
​bb8e1e1	Trac #32841: remove zn_poly dependency from sagelib.
​38d52c1	Trac #32841: remove the zn_poly SPKG.
​98a75c8	Trac #32841: use zlib instead of zn_poly in a sage-package comment.
​73ed717	Trac #32841: use zlib instead of zn_poly in package list examples.
​ee4ad0f	Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
​f700a4b	Trac #32841: remove zn_poly section from COPYING.txt.
​9c11ac9	Trac #32841: remove mentions of zn_poly from README.md.
​d18bd78	Trac #32841: remove zn_poly mention from a thematic tutorial.
​d49f959	Trac #32841: don't mention zn_poly in flint header comments.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​3f80162	Trac #32841: remove zn_poly from the library order.
​cdf2a3b	Trac #32841: remove zn_poly dependency from sagelib.
​a0d2752	Trac #32841: remove the zn_poly SPKG.
​17786a8	Trac #32841: use zlib instead of zn_poly in a sage-package comment.
​41718b3	Trac #32841: use zlib instead of zn_poly in package list examples.
​8681e82	Trac #32841: remove zn_poly TARGETS from cygwin github workflows.
​275f9a7	Trac #32841: remove zn_poly section from COPYING.txt.
​5170681	Trac #32841: remove mentions of zn_poly from README.md.
​aaaa272	Trac #32841: remove zn_poly mention from a thematic tutorial.
​752c53d	Trac #32841: don't mention zn_poly in flint header comments.