#27418 closed enhancement (fixed)

Global function fields: completions

Reported by: klee Owned by:
Priority: major Milestone: sage-8.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 meta-ticket #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 klee

  • Authors set to Kwankyu Lee
  • Branch set to u/klee/27418

comment:2 Changed 23 months ago by git

  • Commit set to 06d41fd4eeba447383ecb4b7e5a1691737cab5b3

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

06d41fdAdd higher-derivations and completions

comment:3 Changed 23 months ago by klee

  • Status changed from new to needs_review

comment:4 follow-up: Changed 23 months ago by 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.

comment:5 follow-up: Changed 23 months ago by 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.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 23 months ago by 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...

comment:7 in reply to: ↑ 6 ; follow-up: Changed 23 months ago by 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.

comment:8 Changed 23 months ago by git

  • Commit changed from 06d41fd4eeba447383ecb4b7e5a1691737cab5b3 to 6ece364586eaf8c95b026568745dae92d68e0a34

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

6ece364Fixes to respond to reviewer comments

comment:9 in reply to: ↑ 4 ; follow-up: Changed 23 months ago by 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.

comment:10 in reply to: ↑ 7 Changed 23 months ago by 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 :-)

comment:11 Changed 23 months ago by git

  • Commit changed from 6ece364586eaf8c95b026568745dae92d68e0a34 to 917149bfa57a9d380b715439a3692b98a6cb0110

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

917149bFix the broken lambda and pass _test_pickling

comment:12 Changed 23 months ago by klee

Somehow, I managed to pass the _test_pickling.

comment:13 Changed 23 months ago by git

  • Commit changed from 917149bfa57a9d380b715439a3692b98a6cb0110 to bc476cfbacf3aac139a0319633e20392de81989d

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

bc476cfPrevent coverage degradation

comment:14 Changed 23 months ago by git

  • Commit changed from bc476cfbacf3aac139a0319633e20392de81989d to dc4a852c44507de9e25fa36636eb548c9f1e91e8

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

dc4a852A trivial fix in a doctest

comment:15 in reply to: ↑ 9 Changed 23 months ago by tscrim

  • Branch changed from u/klee/27418 to u/tscrim/function_fields_completions-27418
  • 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 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:

985f44eOne more xderinv added.
79d6eefRemoving some code duplication for __pth_root (changed to _pth_root_func).
a6affc4Some last little tidbits for uniformity.
13ce935Replacing None < infinity comparison with equivalent code.

comment:16 Changed 23 months ago by klee

  • Status changed from needs_review to positive_review

Very nice! Thank you :-)

comment:17 Changed 23 months ago by vbraun

  • Branch changed from u/tscrim/function_fields_completions-27418 to 13ce9355e549247c17a0ed83cc1be0df08545d7b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.