Opened 23 months ago
Closed 23 months ago
#27418 closed enhancement (fixed)
Global function fields: completions
Reported by:  klee  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  algebra  Keywords:  
Cc:  Merged in:  
Authors:  Kwankyu Lee  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  13ce935 (Commits)  Commit:  13ce9355e549247c17a0ed83cc1be0df08545d7b 
Dependencies:  Stopgaps: 
Description
This is part of the metaticket #22982.
The goal of the present ticket is to add code for computing with higher derivations and completions of global function fields.
Change History (17)
comment:1 Changed 23 months ago by
 Branch set to u/klee/27418
comment:2 Changed 23 months ago by
 Commit set to 06d41fd4eeba447383ecb4b7e5a1691737cab5b3
comment:3 Changed 23 months ago by
 Status changed from new to needs_review
comment:4 followup: ↓ 9 Changed 23 months ago by
Some comments:
FunctionFieldHigherDerivation.__init__
is missing a doctest (add a TestSuite(foo).run()
here ;)
, if something is failing, add a skip="_test_failed"
or skip=["_test_failed", "_test_failure"]
).
Same for FunctionFieldHigherDerivation_rational
.
I think you should include a definition of the Cartier operation (unless this is something anyone who has ever learned about function fields will know about it; pardon my ignorance here)?
In _pth_root
, I would avoid the import from .element import FunctionFieldElement_rational
as this can really slow things down more than you expect (in my experience). If you need to put it in the method because of circular imports, then I would instead make it a lazy_import
.
This seems like the better (i.e., faster) way to do it instead of dividing by `x.derivative() in the lambda function:
xderinv = ~(x.derivative()) derivative = lambda f: xderinv * f.derivative()
I am not sure this comparison if prec < infinity:
for prec=None
will always work on Python3. So I think you are better changing the order of the tests to be
if prec is None or prec == infinity: raise NotImplementedErorr # continue with init
Some nitpicks:
R(0)
> R.zero()
(unless you expect R
to be a Python type like int
, but I don't see that happening here).
Microoptimization for when the basis is empty:
+ if not basis: + return [],[] d = len(basis)   if d == 0:  return [],[]
The oneline sentence for completion()
is missing a period/fullstop.
Return ith derivative of f with respect to the separating element. +Return ``i``th derivative of ``f`` with respect to the separating element.
I think doing pth_root = self._pth_root
obfuscates the code at little bit. I doubt that one additional indirection matters that much for speed (but maybe I am wrong).
A little more clarity on the message:
raise NotImplementedError('not yet supported') +raise NotImplementedError('exact results not yet supported')
Instead of checking while len(gaps) < g:
, you could instead decrement g
when adding to gaps
and test while g:
. This should be faster.
comment:5 followup: ↓ 6 Changed 23 months ago by
So why the pickling isn't working is this:
sage: F.<x> = FunctionField(GF(2)) sage: d = F.higher_derivation() sage: d.__reduce__() (<builtin function unpickle_map>, (<class 'sage.rings.function_field.maps.FunctionFieldHigherDerivation_rational'>, Set of Homomorphisms from Rational function field in x over Finite Field of size 2 to Rational function field in x over Finite Field of size 2, {'_field': Rational function field in x over Finite Field of size 2, '_p': 2, '_pth_root_in_finite_field': <function <lambda> at 0x7f01f807f230>, '_separating_element': x}, {'_codomain': Rational function field in x over Finite Field of size 2, '_domain': Rational function field in x over Finite Field of size 2, '_is_coercion': False, '_repr_type_str': None}))
The lambda function cannot be pickled. This was indicated by trying to do
sage: dumps(d) ... PicklingError: Can't pickle <type 'function'>: attribute lookup __builtin__.function failed
So the simple solution would be to remove _pth_root_in_finite_field
and just inline the checks. I did that, but then the pickling still failed because equality was not implemented.
Thus, hat I would suggest doing is making these Map
classes also inherit from UniqueRepresentation
. I don't think this will introduce any reference cycles (i.e., a memory leak) considering your input parameter is just the field
.
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 23 months ago by
So the simple solution would be to remove
_pth_root_in_finite_field
and just inline the checks. I did that, but then the pickling still failed because equality was not implemented.
I already have done both.
Thus, hat I would suggest doing is making these
Map
classes also inherit fromUniqueRepresentation
. I don't think this will introduce any reference cycles (i.e., a memory leak) considering your input parameter is just thefield
.
I also have tried this :) But adding UniqueRepresentation
also raises an exception complaining of multiple metaclasses...
comment:7 in reply to: ↑ 6 ; followup: ↓ 10 Changed 23 months ago by
Replying to klee:
Thus, hat I would suggest doing is making these
Map
classes also inherit fromUniqueRepresentation
. I don't think this will introduce any reference cycles (i.e., a memory leak) considering your input parameter is just thefield
.I also have tried this :) But adding
UniqueRepresentation
also raises an exception complaining of multiple metaclasses...
What you need to do is use is the metaclass that is a combination of the two being passed:
from six import with_metaclass from sage.structure.unique_representation import UniqueRepresentation from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass class FunctionFieldDerivation(with_metaclass(InheritComparisonClasscallMetaclass, UniqueRepresentation, Map)):
With the appropriate change, I get the pickling test to pass.
comment:8 Changed 23 months ago by
 Commit changed from 06d41fd4eeba447383ecb4b7e5a1691737cab5b3 to 6ece364586eaf8c95b026568745dae92d68e0a34
Branch pushed to git repo; I updated commit sha1. New commits:
6ece364  Fixes to respond to reviewer comments

comment:9 in reply to: ↑ 4 ; followup: ↓ 15 Changed 23 months ago by
FunctionFieldHigherDerivation.__init__
is missing a doctest (add aTestSuite(foo).run()
here;)
, if something is failing, add askip="_test_failed"
orskip=["_test_failed", "_test_failure"]
).Same for
FunctionFieldHigherDerivation_rational
.
Done, but I made some changes as efforts to pass the tests.
I think you should include a definition of the Cartier operation (unless this is something anyone who has ever learned about function fields will know about it)?
Done. It seems not a standard material.
In
_pth_root
, I would avoid the importfrom .element import FunctionFieldElement_rational
as this can really slow things down more than you expect (in my experience). If you need to put it in the method because of circular imports, then I would instead make it alazy_import
.
Done. I could use .element_class
This seems like the better (i.e., faster) way to do it instead of dividing by `x.derivative() in the lambda function:
xderinv = ~(x.derivative()) derivative = lambda f: xderinv * f.derivative()
Done. I forgot that I did it elsewhere.
I am not sure this comparison
if prec < infinity:
forprec=None
will always work on Python3. So I think you are better changing the order of the tests to beif prec is None or prec == infinity: raise NotImplementedErorr # continue with init
Note that None < infinity
is True
. If prec
is None
, a default precision is used.
I plan to (but did not yet) support prec=infinity
for infinite precision, once after #27347 (lazy laurent series) is merged.
R(0)
>R.zero()
(unless you expectR
to be a Python type likeint
, but I don't see that happening here).
Done.
Microoptimization for when the basis is empty:
+ if not basis: + return [],[] d = len(basis)   if d == 0:  return [],[]
Done.
The oneline sentence for
completion()
is missing a period/fullstop.
Fixed.
Return ith derivative of f with respect to the separating element. +Return ``i``th derivative of ``f`` with respect to the separating element.
Done.
I think doing
pth_root = self._pth_root
obfuscates the code at little bit. I doubt that one additional indirection matters that much for speed (but maybe I am wrong).
Right. I removed these evil optimizations.
A little more clarity on the message:
raise NotImplementedError('not yet supported') +raise NotImplementedError('exact results not yet supported')
Done. It is now infinite precision is not yet supported
.
Instead of checking
while len(gaps) < g:
, you could instead decrementg
when adding togaps
and testwhile g:
. This should be faster.
Good idea. Done.
comment:10 in reply to: ↑ 7 Changed 23 months ago by
Replying to tscrim:
Replying to klee:
Thus, hat I would suggest doing is making these
Map
classes also inherit fromUniqueRepresentation
. I don't think this will introduce any reference cycles (i.e., a memory leak) considering your input parameter is just thefield
.I also have tried this :) But adding
UniqueRepresentation
also raises an exception complaining of multiple metaclasses...What you need to do is use is the metaclass that is a combination of the two being passed:
from six import with_metaclass from sage.structure.unique_representation import UniqueRepresentation from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass class FunctionFieldDerivation(with_metaclass(InheritComparisonClasscallMetaclass, UniqueRepresentation, Map)):With the appropriate change, I get the pickling test to pass.
Ugh.. I prefer just to avoid the pickling test :)
comment:11 Changed 23 months ago by
 Commit changed from 6ece364586eaf8c95b026568745dae92d68e0a34 to 917149bfa57a9d380b715439a3692b98a6cb0110
Branch pushed to git repo; I updated commit sha1. New commits:
917149b  Fix the broken lambda and pass _test_pickling

comment:12 Changed 23 months ago by
Somehow, I managed to pass the _test_pickling
.
comment:13 Changed 23 months ago by
 Commit changed from 917149bfa57a9d380b715439a3692b98a6cb0110 to bc476cfbacf3aac139a0319633e20392de81989d
Branch pushed to git repo; I updated commit sha1. New commits:
bc476cf  Prevent coverage degradation

comment:14 Changed 23 months ago by
 Commit changed from bc476cfbacf3aac139a0319633e20392de81989d to dc4a852c44507de9e25fa36636eb548c9f1e91e8
Branch pushed to git repo; I updated commit sha1. New commits:
dc4a852  A trivial fix in a doctest

comment:15 in reply to: ↑ 9 Changed 23 months ago by
 Branch changed from u/klee/27418 to u/tscrim/function_fields_completions27418
 Commit changed from dc4a852c44507de9e25fa36636eb548c9f1e91e8 to 13ce9355e549247c17a0ed83cc1be0df08545d7b
 Reviewers set to Travis Scrimshaw
Thank you for the fixes. I have made a few more (see below).
Replying to klee:
FunctionFieldHigherDerivation.__init__
is missing a doctest (add aTestSuite(foo).run()
here;)
, if something is failing, add askip="_test_failed"
orskip=["_test_failed", "_test_failure"]
).Same for
FunctionFieldHigherDerivation_rational
.Done, but I made some changes as efforts to pass the tests.
Thank you. I also got rid of some code duplication. Personally, I think what we should do is add a pth_root
method to a prime field to get rid of this hack. Anyways, this will work for now as that should be on a separate ticket.
This seems like the better (i.e., faster) way to do it instead of dividing by `x.derivative() in the lambda function:
xderinv = ~(x.derivative()) derivative = lambda f: xderinv * f.derivative()Done. I forgot that I did it elsewhere.
I fixed one more of these.
I am not sure this comparison
if prec < infinity:
forprec=None
will always work on Python3. So I think you are better changing the order of the tests to beif prec is None or prec == infinity: raise NotImplementedErorr # continue with initNote that
None < infinity
isTrue
. Ifprec
isNone
, a default precision is used.
Ah, right. However, this is something that should be addressed because there is no guarantee that this will remain this way (or not raise an error). So I have changed it to be what should be equivalent code (as None == infinity
should always return False
).
I also made a few other trivial tweaks for PEP8. If my changes are good, then you can set a positive review.
New commits:
985f44e  One more xderinv added.

79d6eef  Removing some code duplication for __pth_root (changed to _pth_root_func).

a6affc4  Some last little tidbits for uniformity.

13ce935  Replacing None < infinity comparison with equivalent code.

comment:16 Changed 23 months ago by
 Status changed from needs_review to positive_review
Very nice! Thank you :)
comment:17 Changed 23 months ago by
 Branch changed from u/tscrim/function_fields_completions27418 to 13ce9355e549247c17a0ed83cc1be0df08545d7b
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Add higherderivations and completions