Global function fields: completions

[klee]

This is part of the meta-ticket #22982.

The goal of the present ticket is to add code for computing with higher derivations and completions of global function fields.

[git]

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

​06d41fd

Add higher-derivations and completions

[tscrim]

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).

Micro-optimization for when the basis is empty:

+        if not basis:
+            return [],[]
         d = len(basis)
-
-        if d == 0:
-            return [],[]

The one-line sentence for completion() is missing a period/full-stop.

-Return i-th 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.

[tscrim]

So why the pickling isn't working is this:

sage: F.<x> = FunctionField(GF(2))
sage: d = F.higher_derivation()
sage: d.__reduce__()
(<built-in 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.

[klee]

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 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.

I also have tried this :-) But adding UniqueRepresentation also raises an exception complaining of multiple metaclasses...

[tscrim]

Replying to klee:

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.

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.

[git]

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

​6ece364

Fixes to respond to reviewer comments

[klee]

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.

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 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.

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: 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

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 expect R to be a Python type like int, but I don't see that happening here).

Done.

Micro-optimization for when the basis is empty:

+        if not basis:
+            return [],[]
         d = len(basis)
-
-        if d == 0:
-            return [],[]

Done.

The one-line sentence for completion() is missing a period/full-stop.

Fixed.

-Return i-th 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 decrement g when adding to gaps and test while g:. This should be faster.

Good idea. Done.

[klee]

Replying to tscrim:

Replying to klee:

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.

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 :-)

[git]

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

​917149b

Fix the broken lambda and pass _test_pickling

[klee]

Somehow, I managed to pass the _test_pickling.

[git]

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

​bc476cf

Prevent coverage degradation

[git]

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

​dc4a852

A trivial fix in a doctest

[tscrim]

Thank you for the fixes. I have made a few more (see below).

Replying to klee:

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.

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: 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

Note that None < infinity is True. If prec is None, 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.

[klee]

Very nice! Thank you :-)