#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)
Change History (24)
comment:1 Changed 8 years ago by
- Status changed from new to needs_work
comment:2 Changed 8 years ago by
comment:3 Changed 8 years ago by
- Status changed from needs_work to needs_review
I have uploaded a patch. It does the following:
- Moves the functions mentioned to a new file, rational_point
- 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.
- Added docstrings for these four functions.
- 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 8 years ago by
- 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 8 years ago by
- 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 8 years ago by
Both patches (so far!) are based on sage 4.4.3
comment:7 follow-up: ↓ 8 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
- 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: ↓ 11 Changed 8 years ago by
- 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 8 years ago by
- 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 8 years ago by
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:
- 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?).
G1 = [[x for x in g.list()] for g in G.rows()]
... Why notG1 = G.rows()
or at leastG1 = [g.list() for g in G.rows()]
etc.? This is a big waste of time (remember that Python is slow anyway...)- 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...)
comment:13 Changed 8 years ago by
- 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 8 years ago by
- Status changed from needs_review to positive_review
comment:15 Changed 8 years ago by
- Milestone changed from sage-4.6.1 to sage-4.6.2
comment:16 Changed 8 years ago by
This will likely need to be rebased when sage-4.6.1.alpha3 will be released.
comment:17 Changed 8 years ago by
- Status changed from positive_review to needs_work
- Work issues set to Rebase to #6094
comment:18 Changed 8 years ago by
- Status changed from needs_work to positive_review
- Work issues Rebase to #6094 deleted
comment:19 Changed 7 years ago by
- Merged in set to sage-4.6.2.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:20 follow-up: ↓ 22 Changed 7 years ago by
Depends on #9055
comment:21 Changed 7 years ago by
Sorry wrong ticket, my bad :(
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 ;-)