Opened 3 years ago

Closed 3 years ago

#21872 closed defect (fixed)

Conversion from a function field to its field of constants

Reported by: saraedum Owned by:
Priority: minor Milestone: sage-7.5
Component: commutative algebra Keywords: function field, conversion
Cc: Merged in:
Authors: Julian Rüth Reviewers: David Roe
Report Upstream: N/A Work issues:
Branch: 21a6a10 (Commits) Commit: 21a6a105637a9ecafe6b103e8dfae54c59b82653
Dependencies: Stopgaps:

Description

Currently, there is no such conversion

sage: K.<x> = FunctionField(QQ)
sage: K(1) in QQ
False

Change History (25)

comment:1 Changed 3 years ago by saraedum

  • Branch set to u/saraedum/conversion_from_a_function_field_to_its_field_of_constants

comment:2 Changed 3 years ago by saraedum

  • Commit set to 69bcf160a9f7dcbedcb8e621d6c0c427dea7c278
  • Status changed from new to needs_review

New commits:

7960d44Fix conversion from rational function fields to its constant base field
69bcf16Fix conversion of function fields into their subfields

comment:3 Changed 3 years ago by git

  • Commit changed from 69bcf160a9f7dcbedcb8e621d6c0c427dea7c278 to bb2e08e7ea03c06c03762c0226531d2f7768650f

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

bb2e08eremoved indirect doctest marker

comment:4 Changed 3 years ago by saraedum

I ran doctests in function_fields/. The documentation builds without errors. Let's see whether the patchbot likes it as well…

comment:5 Changed 3 years ago by nbruin

Are you sure that installing a *conversion* map is the right solution? In many similar situations, there is no such map:

sage: K.<I>=NumberField(x^2+1)
sage: K(1) in QQ
True
sage: QQ._convert_map_from_(K) == None
sage: P.<t>=ZZ[]
sage: P(1) in ZZ
True
sage: ZZ._convert_map_from_(P) == None
True
sage: L.<u>=FunctionField(QQ) #this is one of your cases
sage: L(1) in QQ
False

It might be worth checking how these other cases succeed in making this work, and why they're doing it. It might be because their methods predate the coercion framework, but it might also be because introducing cycles in the conversion graph is not preferred.

comment:6 Changed 3 years ago by saraedum

nbruin: Thanks for having a look at this.

Conversion to ZZ works differently:

sage: sage: K.<I>=NumberField(x^2+1)
sage: ZZ.convert_map_from(K)

Conversion via _integer_ method map:
  From: Number Field in I with defining polynomial x^2 + 1
  To:   Integer Ring
sage: ZZ.convert_map_from(QQ)

So, this path does not apply for function fields.

Asking for a conversion to QQ:

sage: QQ.convert_map_from(K)
Conversion map:
  From: Number Field in I with defining polynomial x^2 + 1
  To:   Rational Field

so a DefaultConvertMap_unique which

    […] defers action to the codomain's
    element_constructor method, WITHOUT passing in the codomain as the
    first argument. […]

i.e., the target ring needs to understand what to do with the elements. I certainly do not want to teach the rational ring what a function field element is.

Finally, cycles in conversions are no problem. Conversions are not automatically composed (unlike coercions.)

comment:7 Changed 3 years ago by saraedum

I believe that installing a conversion map down to the constant base field is necessary. For the intermediate fields, one could also change _element_constructor_ to make sense of function field elements but then the _to_constant_field would get quite a bit more complicated.

comment:8 Changed 3 years ago by roed

I agree with Julian that there's no problem having cycles in the conversion graph, and many rings in Sage with a concept of base ring have a conversion back to it for constants.

Julian, have you looked at how this change impacts object creation time for function fields? Maybe it would be better to implement this in _convert_map_from_ rather than calling register_conversion in __init__. I think register_conversion is available for end users who aren't able to modify _convert_map_from_.

Otherwise, I'm happy with this change, and willing to give a positive review once we hear back from the patchbot.

comment:9 Changed 3 years ago by saraedum

For the conversion down to the constant base field, I do not really have an option. (I would have to change _convert_map_from_ for Field or something similar.)

sage: K.<x> = FunctionField(QQ)
sage: from sage.rings.function_field.function_field import FunctionField_polymod
sage: K.<x> = FunctionField(QQ)
sage: R.<y> = K[]
sage: # work around caching by calling the class directly
sage: %timeit FunctionField_polymod(y^2-x, 'y')

Yes, object creation time does go up here from 332 µs to 555 µs. I am not sure if that is an issue. Function fields are cached after all, and I have a hard time imagining someone to create tons of them with different defining polynomials. I implemented this with _convert_map_from_ on the level of function fields (but I still need the register_conversion_map for the constant base field) which gets this number down to 440 µs. Imho, the code is substantially less readable that way. So, about 110 µs seems to be the cost of a call to register_conversion_map.

David, what do you think?

comment:10 Changed 3 years ago by saraedum

PS: I am planning to install another conversion down to the polynomial ring that is used to implement the elements of the function field, i.e., K(x) to K[x]. Here again, I won't have no choice but to register the conversion in __init__, so using _convert_map_from_ is about 660 µs or 550 µs which does not look like that much of a difference anymore.

comment:11 follow-up: Changed 3 years ago by roed

You're right that we'll need register_conversion_map for the constant field and for K[x]. I'm fine with a 20% slowdown in parent creation for the sake of readibility, though I would be curious to know if Nils has use cases where he wants to create tons of different function fields and object creation is the bottleneck. I guess another instance where your approach would cause problems is deeply nested relative extensions of function fields, where the total number of conversion maps created grows quadratically with the depth. I don't think that's a common use case though....

comment:12 in reply to: ↑ 11 ; follow-up: Changed 3 years ago by nbruin

Replying to roed:

I would be curious to know if Nils has use cases where he wants to create tons of different function fields and object creation is the bottleneck.

I don't have immediate examples, although I could imagine that fibred surfaces (either arithmetic or otherwise) might give rise to such a scenario. The bottleneck could arise if someone wants to try something really easy with the fibers, but ends up creating the fibers as curves and perhaps creating the function fields as an unintended side-effect. I don't know if the kind of slow-downs we're talking about here would be likely to be significant in such a setting.

I guess another instance where your approach would cause problems is deeply nested relative extensions of function fields, where the total number of conversion maps created grows quadratically with the depth. I don't think that's a common use case though....

Indeed, but I would suggest being a little conservative with implementing this. Can we first just install the conversion to the base ring and not transitively close over all the base rings below that?

Incidentally, you have to be very careful about how you implement the conversion maps to the base rings. They will be cached on the codomain (i.e., on the base ring), so you should make sure you're *not* storing any references to the domain or its elements in the map object. All of that needs to be recovered from the argument (this is part of the reason why conversion to ZZ is implemented the way it is).

Otherwise, you'll see that function fields over QQ end up not being garbage collected, because an eternal object (QQ) is keeping a reference to them in the form of registered conversion maps. This is why maps in the coercion system do NOT store their domain. See #14711 for some of the black magic that was required.

So, one thing you should probably test is that

K.<t>=FunctionField(QQ)
P.<X>=PolynomialRing(K)
c=1
while True:
  L=K.extension(X^2-t^2+c*t)
  u=QQ(L(1))

doesn't leak.

comment:13 in reply to: ↑ 12 Changed 3 years ago by roed

Replying to nbruin:

Incidentally, you have to be very careful about how you implement the conversion maps to the base rings. They will be cached on the codomain (i.e., on the base ring), so you should make sure you're *not* storing any references to the domain or its elements in the map object. All of that needs to be recovered from the argument (this is part of the reason why conversion to ZZ is implemented the way it is).

Good point; I think the current implementation has this problem.

Otherwise, you'll see that function fields over QQ end up not being garbage collected, because an eternal object (QQ) is keeping a reference to them in the form of registered conversion maps. This is why maps in the coercion system do NOT store their domain. See #14711 for some of the black magic that was required.

#14711 is interesting. I'll have to think about how that should affect conversions. But the memory leak issue definitely should be addressed.

So, one thing you should probably test is that

K.<t>=FunctionField(QQ)
P.<X>=PolynomialRing(K)
c=1
while True:
  L=K.extension(X^2-t^2+c*t)
  u=QQ(L(1))

doesn't leak.

I assume you want to increment c inside your loop.

comment:14 follow-up: Changed 3 years ago by roed

Note that #14711 has a TODO of adding an option to register_conversion to use weak references as well. I think we need that option here, but that should solve the problem you've pointed out.

comment:15 in reply to: ↑ 14 Changed 3 years ago by nbruin

I assume you want to increment c inside your loop.

yes, although I now realize that this ticket only seems to be dealing with rational function fields, so the test should be amended accordingly.

Replying to roed:

Note that #14711 has a TODO of adding an option to register_conversion to use weak references as well. I think we need that option here, but that should solve the problem you've pointed out.

Yes, with the implementation of the conversion map proposed here, it should. I don't think the maps store any references to the domain internally. In the mean time, you should use something like

   phi = to_be_registered_map
   phi._make_weak_references() #this should remove the strong references
   K.register_conversion(phi)
   del phi #or just make sure that phi doesn't escape elsewhere

comment:16 Changed 3 years ago by saraedum

Thanks for all the input. I had not thought about leaks here. Sadly, _make_weak_references() does not do the trick. The register_convert_map implementation has a line that says self._convert_from_hash.set(mor.domain(),mor) which does not seem to use weak references.

Last edited 3 years ago by saraedum (previous) (diff)

comment:17 Changed 3 years ago by saraedum

Actually _convert_from_hash does use weak references, so it must be leaking somewhere else…

comment:18 Changed 3 years ago by saraedum

Ok. The problem is the SetMorphism that I have been using. The parameter self._to_constant_base_field that I pass in holds a reference to the function field. I am going to upload a version that uses a proper FunctionFieldConversionToConstantBaseField map. Also, I found a way to implement _conversion_map_from_ that makes the code not unreadable.

comment:19 Changed 3 years ago by git

  • Commit changed from bb2e08e7ea03c06c03762c0226531d2f7768650f to 0b87e90806da4aaddec4948c0c531d41762483f7

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

7b2d90cUse _convert_map_from_
0b87e90Wire up conversion to the constant base field in the FunctionField base class

comment:20 Changed 3 years ago by saraedum

This needs review again.

comment:21 Changed 3 years ago by nbruin

Little doc nitpick:

+    def _to_base_field(self, f):
...
+        - ``f`` -- an element of this function field which is already defined
+          over the base field

you probably mean "an element of the function field that lies in the base field". All elements of the function field are defined over the base field by definition.

Elsewhere: be careful with calling subfields "constants". For instance, the function field QQ(x)[y]/(y^2-2) has as constant subfield QQ(sqrt(2)), whereas the base field is QQ. Finding the exact constant field (i.e., the algebraic closure of the base field in the function field) takes considerable computation, so I'm not sure this is part of the scope of this ticket.

comment:22 Changed 3 years ago by git

  • Commit changed from 0b87e90806da4aaddec4948c0c531d41762483f7 to 21a6a105637a9ecafe6b103e8dfae54c59b82653

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

21a6a10improve wording on base fields

comment:23 Changed 3 years ago by saraedum

The patchbot complains about modsym/space.py. I checked locally and it works fine. (It would also have been very suprising if this made a difference there.)

comment:24 Changed 3 years ago by roed

  • Reviewers set to David Roe
  • Status changed from needs_review to positive_review

I'm happy with the changes. Nils, thanks for the suggestions: feel free to add yourself as a reviewer.

comment:25 Changed 3 years ago by vbraun

  • Branch changed from u/saraedum/conversion_from_a_function_field_to_its_field_of_constants to 21a6a105637a9ecafe6b103e8dfae54c59b82653
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.