Opened 6 years ago
Closed 6 years ago
#21872 closed defect (fixed)
Conversion from a function field to its field of constants
Reported by:  saraedum  Owned by:  

Priority:  minor  Milestone:  sage7.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, GitHub, GitLab)  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 6 years ago by
 Branch set to u/saraedum/conversion_from_a_function_field_to_its_field_of_constants
comment:2 Changed 6 years ago by
 Commit set to 69bcf160a9f7dcbedcb8e621d6c0c427dea7c278
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Commit changed from 69bcf160a9f7dcbedcb8e621d6c0c427dea7c278 to bb2e08e7ea03c06c03762c0226531d2f7768650f
Branch pushed to git repo; I updated commit sha1. New commits:
bb2e08e  removed indirect doctest marker

comment:4 Changed 6 years ago by
I ran doctests in function_fields/
. The documentation builds without errors. Let's see whether the patchbot likes it as well…
comment:5 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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^2x, '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 6 years ago by
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 followup: ↓ 12 Changed 6 years ago by
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 ; followup: ↓ 13 Changed 6 years ago by
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 sideeffect. I don't know if the kind of slowdowns 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^2t^2+c*t) u=QQ(L(1))
doesn't leak.
comment:13 in reply to: ↑ 12 Changed 6 years ago by
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^2t^2+c*t) u=QQ(L(1))doesn't leak.
I assume you want to increment c
inside your loop.
comment:14 followup: ↓ 15 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
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.
comment:17 Changed 6 years ago by
Actually _convert_from_hash
does use weak references, so it must be leaking somewhere else…
comment:18 Changed 6 years ago by
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 6 years ago by
 Commit changed from bb2e08e7ea03c06c03762c0226531d2f7768650f to 0b87e90806da4aaddec4948c0c531d41762483f7
comment:20 Changed 6 years ago by
This needs review again.
comment:21 Changed 6 years ago by
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^22)
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 6 years ago by
 Commit changed from 0b87e90806da4aaddec4948c0c531d41762483f7 to 21a6a105637a9ecafe6b103e8dfae54c59b82653
Branch pushed to git repo; I updated commit sha1. New commits:
21a6a10  improve wording on base fields

comment:23 Changed 6 years ago by
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 6 years ago by
 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 6 years ago by
 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
New commits:
Fix conversion from rational function fields to its constant base field
Fix conversion of function fields into their subfields