Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#9055 closed enhancement (fixed)

Moving/cleaning enumeration functions for points on schemes

Reported by: cturner Owned by: AlexGhitza
Priority: minor Milestone: sage-4.6.2
Component: algebraic geometry Keywords: rational points enumeration
Cc: cremona, wdj Merged in: sage-4.6.2.alpha0
Authors: Charlie Turner, David Joyner, Robert Miller, Andrey Novoseltsev Reviewers: Robert Miller, Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

I think it would be sensible to move the functions

enum_projective_rational_field

enum_projective_finite_field

enum_affine_rational_field

enum_affine_finite field

from their current position at the top of sage.schemes.generic.homset, and to clean up their code to make it easier to read whilst (I believe) keeping the timing about the same.

I have started work on a patch that does this, putting them into a new file sage.schemes.generic.rational_point and using the cartesian_product_iterator function to make the code much more readable.

This is a preamble to putting other (more efficient) functions that find rational points in specific cases into the same file - I am currently working on this, and will make a separate ticket for it.

Attachments (2)

trac_9055_reviewer.patch (14.0 KB) - added by novoselt 7 years ago.
Apply last
trac_9055-rebased.patch (36.8 KB) - added by rlm 7 years ago.
rebased on sage-4.6.1.alpha2 + #6094

Download all attachments as: .zip

Change History (24)

comment:1 Changed 7 years ago by cturner

  • Authors Charlie Turner deleted
  • Status changed from new to needs_work

comment:2 Changed 7 years ago by novoselt

I support the idea of moving these functions - I was a bit surprised to see them when I was going over homset file. And of course nobody should be against making them more readable ;-)

comment:3 Changed 7 years ago by cturner

  • Status changed from needs_work to needs_review

I have uploaded a patch. It does the following:

  1. Moves the functions mentioned to a new file, rational_point
  2. Changed enum_projective_rational_field, enum_projective_finite_field, enum_affine_finite_field to be, I hope, more readable, but to run no faster. I have also added a sort at the end.

I did not change enum_affine_rational_field in the end because I couldn't see a simpler way to do it.

  1. Added docstrings for these four functions.
  2. Changed some doctests for the rational_points function (which use these functions) in the algebraic_scheme file. This is because the old functions returned an unsorted list and the new ones sort before returning, so the ordering has changed but the set of points has not.

comment:4 Changed 7 years ago by novoselt

  • Status changed from needs_review to needs_work

I just glanced at the patch, but I have the following comments:

1) "Set of homomorphisms between two schemes" should stay in the original file, it is the docstring of the module describing what does it do.

2) There should be a new description (hopefully, more informative) in the new module. The first line is how this module will be listed in the documentation, the rest can be any text. Also, there should be the copyright/license notice and AUTHORS field in the module docline (stating who has written these functions initially and that you have improved and documented them).

3) There are some doctests with very long output strings. This leads to not very good looking formatting of the documentation. You can insert line breaks in the output and doctests still will run fine. I would suggest doing it to keep line length under 80 (or even 60, excluding leading spaces,) characters.

4) Did you try to compile a documentation with this module? I didn't, but it seems to me that there are quite a few problems with indentations and "::"s. Also, now that you have actually added the docstrings to these functions, it would make sense to include this module into the auto-generated documentation tree.

5) Is there any specific reason for importing these functions in the homset module right before their use? It is my strong belief that all imports should be in the beginning of the file to avoid repetitions and to make it clear what is used by this module.

I think that 1), 2), and 4) are mandatory, while 3) and 5) may reflect my personal taste (although I tried to explain why do I think that they make sense).

comment:5 Changed 7 years ago by cturner

  • Cc wdj added
  • Status changed from needs_work to needs_review

1) I (believe I have) fixed the issues flagged by novoselt. Thank you novoselt for your help in pointing them out.

2) I have improved the code so that it can take either a scheme or an abstract set of rational points of a scheme as input.

THERE IS A KNOWN DOCTEST FAIL with this patch;

The following tests failed:

sage/coding/code_constructions.py
sage/coding/linear_code.py
sage/coding/decoder.py
doc/en/constructions/linear_codes.rst

I think this is because the coding modules use the enum_projective_finite_field function. This causes the same problem as point 4. of my previous comment (circa 8th June). The new versions of each of these functions sort points but the old ones did not. I suspect that the coding functions depend on the order of the output of enum_projective_finite_field and so fail now that that order has changed. I am not proficient with codes and do not feel able to fix this issue. I wonder if someone who does understand coding could help and fix this? I CC David Joyner, who originally wrote these modules. Perhaps it is simply a matter of adapting the doctests to take into account the new ordering. I believe that this is the right way round; that the ordering of the output of the "enum" functions should not depend on the algorithm used.

Because of this, I suggest that the patch be reviewed ignoring these problems with coding modules, and in the meantime a coding person might be able to help solve the problems.

comment:6 Changed 7 years ago by cturner

Both patches (so far!) are based on sage 4.4.3

comment:7 follow-up: Changed 7 years ago by cturner

  • Status changed from needs_review to needs_work

We (John Cremona, David Joyner and myself) believe we have identified what needs to be done to fix the issues with the coding modules and we will return to it after sage days 22!

comment:8 in reply to: ↑ 7 Changed 7 years ago by wdj

Replying to cturner:

We (John Cremona, David Joyner and myself) believe we have identified what needs to be done to fix the issues with the coding modules and we will return to it after sage days 22!

The new attachment (to be applied on top of the previous one) seems to fix the problems in the coding thry docstrings.

comment:9 Changed 7 years ago by novoselt

  • Work issues set to second patch has to be rebased

The second patch does not apply cleanly anymore, on sage-4.6.rc0 I am getting

applying trac-9055-coding-thry-docstring-fixes.patch
patching file sage/coding/linear_code.py
Hunk #13 FAILED at 2028

comment:10 follow-up: Changed 7 years ago by novoselt

  • Authors set to Charlie Turner, David Joyner
  • Milestone set to sage-4.6.1

What exactly has happened to the broken doctests? It does not seem to me that the new output is merely a permutation of the old one.

There are (sometimes) extra spaces in front of the output.

There are some notes/warnings in the documentation and it would be nice if they were formatted according to http://sagemath.org/doc/developer/conventions.html#documentation-strings

comment:11 in reply to: ↑ 10 Changed 7 years ago by rlm

  • Status changed from needs_work to needs_review
  • Work issues second patch has to be rebased deleted

Replying to novoselt:

What exactly has happened to the broken doctests? It does not seem to me that the new output is merely a permutation of the old one.

The ordering of vector spaces over finite fields is used all over the place. In constructing the Hamming codes, etc. I think there is a echelon form involved afterward as well, so it is easy enough to seem like this isn't just a problem with order changing...

The new patch includes all previous ones, and fixes a docstring fix which needed to be rebased.

comment:12 Changed 7 years ago by rlm

I will simply mention for the record that things like

        G = self.gen_mat()
        F = self.base_ring()
        q = F.order()
        q0 = F0.order()
        a = log(q,q0)  # test if F/F0 is a field extension
        if not isinstance(a, Integer):
            raise ValueError,"Base field must be an extension of given field %s"%F0
        n = len(G.columns())
        k = len(G.rows())
        G0 = [[x**q0 for x in g.list()] for g in G.rows()]
        G1 = [[x for x in g.list()] for g in G.rows()]
        G2 = G0+G1
        MS = MatrixSpace(F,2*k,n)
        G3 = MS(G2)
        r = G3.rank()
        MS = MatrixSpace(F,r,n)
        Grref = G3.echelon_form()
        G = MS([Grref.row(i) for i in range(r)])
        return LinearCode(G)

(galois_closure in linear_code.py) can be vastly simplified, and probably sped up in the process.

Programming no-nos:

  1. Using logarithms to test whether one finite field is contained in another (why not just check whether the characteristics are the same and if one degree divides the other?).
  2. G1 = [[x for x in g.list()] for g in G.rows()] ... Why not G1 = G.rows() or at least G1 = [g.list() for g in G.rows()] etc.? This is a big waste of time (remember that Python is slow anyway...)
  3. This is also bad:
            MS = MatrixSpace(F,2*k,n)
            G3 = MS(G2)
            r = G3.rank()
            MS = MatrixSpace(F,r,n)
            Grref = G3.echelon_form()
            G = MS([Grref.row(i) for i in range(r)])
    

... why not just G3 = Matrix(F, 2*k, n, G2); G = G3.row_space().basis_matrix() or the equivalent? It's easier to follow and might be more efficient, too.

(Not criticisms of code in this ticket at all, for the skimmer -- just an indication that linear_code.py needs more work...)

Changed 7 years ago by novoselt

Apply last

comment:13 Changed 7 years ago by novoselt

  • Authors changed from Charlie Turner, David Joyner to Charlie Turner, David Joyner, Robert Miller, Andrey Novoseltsev
  • Reviewers set to Robert Miller, Andrey Novoseltsev

I've prettified documentation of the new module and improved exception handling, since there were several blocks like

try:
   ...
except:
   pass

which potentially can cause strange errors or results. In particular, such a code may be hard to interrupt if it is taking too long.

If someone can go over my patch and approve it, please switch this ticket to positive review. Tests pass.

comment:14 Changed 7 years ago by rlm

  • Status changed from needs_review to positive_review

comment:15 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:16 Changed 7 years ago by jdemeyer

This will likely need to be rebased when sage-4.6.1.alpha3 will be released.

comment:17 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to Rebase to #6094

Changed 7 years ago by rlm

rebased on sage-4.6.1.alpha2 + #6094

comment:18 Changed 7 years ago by rlm

  • Status changed from needs_work to positive_review
  • Work issues Rebase to #6094 deleted

comment:19 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:20 follow-up: Changed 7 years ago by vbraun

Depends on #9055

comment:21 Changed 7 years ago by vbraun

Sorry wrong ticket, my bad :(

comment:22 in reply to: ↑ 20 Changed 7 years ago by jdemeyer

Replying to vbraun:

Depends on #9055

Interesting, a recursive ticket :-) Do you want to denial-of-service the patchbot?

Note: See TracTickets for help on using tickets.