Exhaust over Weil polynomials

[kedlaya]

I have reasonably stable code (mostly in C, depending on FLINT) for exhausting over Weil polynomials:

https://github.com/kedlaya/root-unitary

The goal of this ticket is to incorporate this code into Sage in some fashion.

Depends on #24016

CC: @roed314

Component: number theory

Keywords: Weil polynomials, sd91

Author: Kiran Kedlaya

Branch/Commit: e02ae3c

Reviewer: David Roe

Issue created by migration from https://trac.sagemath.org/ticket/23946

[kedlaya]

comment:1

Status update: I've pushed many recent changes to the branch repackage_for_sage of the Github repo. In particular, I have been working to make the call syntax much more transparent; for instance, to compute the Weil polynomials corresponding to abelian varieties of dimension g over the finite field of order q, one can now use standard Python iterator syntax:

sage: wp = WeilPolynomials(2*g, q)
sage: for i in wp:
...

Some to-do items: check that all my old test scripts still work; write more tests; add more documentation; add more input sanitization.

In the meantime, I'd appreciate some feedback about where this might belong in Sage.

[kedlaya]

Dependencies: #24016

[jdemeyer]

comment:2

Replying to @kedlaya:

In the meantime, I'd appreciate some feedback about where this might belong in Sage.

First of all, your github repo contains both C code and .sage files. Are the .sage files considered to be part of your package or are they really only use cases/examples/tests/documentation?

There are two possibilities, each with its advantages and disadvantages:

(A) Make it an external (presumably optional) package and interface it from Sage.

(B) Make it actually a part of Sage itself.

Advantages of (A) are that you keep control of the package: you can easily change the package at will (with (B) every change would need to go through the Sage Trac) and you don't need to care about Sage coding standards. Also important: with (A) your package could be used without Sage. With (B), there might be more initial work needed to get it into Sage but then it might be less work to maintain.

[kedlaya]

comment:3

I just merged a pull request in from another branch, which has the effect of significantly reconfiguring the file structure. In particular, there are no longer any .sage files in the main directory; the ones that exist are all in subdirectories and are indeed examples/tests.

The main code base now consists of two .c files (and their .h headers) and one .pyx file. I still don't have any sort of independent build structure set up; moreover, the .pyx file is more than just a simple wrapper, it is where the parallelism is currently implemented. So at the moment there is really no way to use the code without Sage, and I don't particularly intend to work on making that possible. (Exception: if someone wants to use the code from some other platform like Julia, I'd be willing to cooperate with that.)

[roed314]

comment:4

I think that the code is stable enough that we should just add it to Sage. Maybe create a folder sage/rings/polynomial/weil/ and put them in there?

[kedlaya]

comment:5

Replying to @roed314:

I think that the code is stable enough that we should just add it to Sage. Maybe create a folder sage/rings/polynomial/weil/ and put them in there?

Do you mean put everything in there? Or put the Cython in sage/rings/polynomials/weil_polynomials.pyx and the C files in sage/rings/polynomial/weil?

Also, if someone can point me to some guidance about a module to the Sage library (e.g., how to format __init__.py and all.py and the like to make the new code discoverable), that would be helpful.

[roed314]

comment:6

Replying to @kedlaya:

Replying to @roed314:

I think that the code is stable enough that we should just add it to Sage. Maybe create a folder sage/rings/polynomial/weil/ and put them in there?

Do you mean put everything in there? Or put the Cython in sage/rings/polynomials/weil_polynomials.pyx and the C files in sage/rings/polynomial/weil?

I meant putting everything in there. We should also talk about the best way for a user to access these methods; perhaps a method weil_polynomials on ZZ[x] and QQ[x] that returns your iterator?

Also, if someone can point me to some guidance about a module to the Sage library (e.g., how to format __init__.py and all.py and the like to make the new code discoverable), that would be helpful.

See http://doc.sagemath.org/html/en/developer/coding_basics.html#files-and-directory-structure for some details. You'll also need to add lines to src/module_list.py for each extension module.

[kedlaya]

Branch: u/kedlaya/exhaust_over_weil_polynomials

[kedlaya]

comment:8

Pushed some partial progress, but this doesn't compile yet.

---

New commits:

da3d483	Add directory src/sage/rings/polynomial/weil/
d12b0ea	Update module list, all.py

[kedlaya]

Commit: d12b0ea

[kedlaya]

New commits:

da3d483	Add directory src/sage/rings/polynomial/weil/
d12b0ea	Update module list, all.py

[kedlaya]

Changed branch from u/kedlaya/exhaust_over_weil_polynomials to none

[kedlaya]

Changed commit from d12b0ea to none

[kedlaya]

Branch: u/kedlaya/weilpoly_search

[kedlaya]

comment:12

OK, here is a new branch which seems to compile. Still a lot of polishing to be done, but it should be possible to at least play with the code now.

---

New commits:

2bfaf04	Initial commit
d7e1e2a	Succesful compilation
2a62e66	Bug fix from upstream (incorrect handling of leading coeffs)

[kedlaya]

Commit: 2a62e66

[fchapoton]

comment:13

does not work for me:

sage: from sage.rings.polynomial.weil.weil_polynomials import *
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-5b4f8184ba57> in <module>()
----> 1 from sage.rings.polynomial.weil.weil_polynomials import *

ImportError: /home/chapoton/sage3/local/lib/python3.7/site-packages/sage/rings/polynomial/weil/weil_polynomials.cpython-37m-x86_64-linux-gnu.so: undefined symbol: GOMP_loop_nonmonotonic_dynamic_start

and there are missing empty lines in the doc after lines ending with ::

[kedlaya]

comment:14

That is the code looking for OpenMP (which is optional, since we don't ship it with Sage). Does it help if you take out the compiler directive in line 2 of sage/rings/polynomial/weil/weil_polynomials.pyx?

The docstrings need a fair bit of work to get to 100% doctest coverage, let alone proper formatting. I can of course work on that independently.

[fchapoton]

comment:15

yes, removing the distutils directive make it work

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

cd2f537	Eliminate compiler warnings about return from a void function
1438c23	Suppress OpenMP, add doctests

[sagetrac-git]

Changed commit from 2a62e66 to 1438c23

[kedlaya]

comment:17

In addition to suppressing OpenMP, I also added doctests to get to 100% coverage.

Cc'ing roed, who is somewhat familiar to the code.

[fchapoton]

comment:18

please remove the "next" method.

and in the test of __next__, use next(it) to call the iterator.

[sagetrac-git]

Changed commit from 1438c23 to 7516836

[vbraun]

comment:39

On Python 2 there are various errors of the form

**********************************************************************
File "src/sage/rings/polynomial/weil/weil_polynomials.pyx", line 168, in sage.rings.polynomial.weil.weil_polynomials.dfs_manager.node_count
Failed example:
    _ = next(it)
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.rings.polynomial.weil.weil_polynomials.dfs_manager.node_count[3]>", line 1, in <module>
        _ = next(it)
    TypeError: instance has no next() method
**********************************************************************

[sagetrac-git]

Changed commit from e0b9ff9 to 7f44a49

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7f44a49

Reinstate next() method for Py2 compatibility

[kedlaya]

comment:42

Replying to @vbraun:

On Python 2 there are various errors of the form

**********************************************************************
File "src/sage/rings/polynomial/weil/weil_polynomials.pyx", line 168, in sage.rings.polynomial.weil.weil_polynomials.dfs_manager.node_count
Failed example:
    _ = next(it)
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.rings.polynomial.weil.weil_polynomials.dfs_manager.node_count[3]>", line 1, in <module>
        _ = next(it)
    TypeError: instance has no next() method
**********************************************************************

I was asked to remove that method (see comment:18), but anyway here it is again.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6a3e93d

Fix typos in doctest

[sagetrac-git]

Changed commit from 7f44a49 to 6a3e93d

[kedlaya]

comment:44

Looking at the patchbot logs, it seems that at least one of the bots failed to build because of nested function declarations in the C code. I thought we were always compiling the Sage library with gcc, which supports nested functions even though they are not in the ANSI standard...?

[vbraun]

comment:45

on osx we now use clang by default

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e02ae3c

Un-nest functions in C code for non-GNU compilers

[sagetrac-git]

Changed commit from 6a3e93d to e02ae3c

[kedlaya]

comment:47

Ah, it seems clang does not (yet) support nested functions as in GNU C. So I redid that bit of the C code; let's see what the patchbots have to say now.

[kedlaya]

comment:48

Some of the patchbots are set up strangely, but I'm not seeing any systemic issues with this branch.

[roed314]

comment:49

I agree. We have successful tests run on Darwin, so I'm setting this back to positive review.

[vbraun]

Changed branch from u/kedlaya/weilpoly_search to e02ae3c