Opened 4 years ago

Closed 3 years ago

#25435 closed task (fixed)

Global function fields: orders and ideals

Reported by: klee Owned by:
Priority: major Milestone: sage-8.4
Component: algebra Keywords:
Cc: Merged in:
Authors: Kwankyu Lee Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 48100b4 (Commits, GitHub, GitLab) Commit: 48100b41622d43e75c263cf62b32be9b335d88f6
Dependencies: Stopgaps:

Status badges

Description (last modified by klee)

This is part of the meta-ticket #22982.

The goal of the present ticket is to add code for computing finite and infinite maximal orders and ideals thereof.

The central engine for computing maximal orders is the Leonard-Pellikaan-Singh-Swanson algorithm implemented in Singular. Most algorithms for computing with ideals are from Cohen's book A Course in Computational Algebraic Number Theory.

Change History (73)

comment:1 Changed 4 years ago by klee

  • Branch set to u/klee/25435

comment:2 Changed 4 years ago by git

  • Commit set to 14d325abf6b996b9e30be854cdf1e91c439f32ee

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

14d325aAdd orders and ideals

comment:3 Changed 4 years ago by git

  • Commit changed from 14d325abf6b996b9e30be854cdf1e91c439f32ee to 1649c1010c1f53671c76003201afa81faa1eab68

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

1649c10Remove is_Ideal

comment:4 Changed 4 years ago by git

  • Commit changed from 1649c1010c1f53671c76003201afa81faa1eab68 to 36aae0779df68316055119cd9c841a64aeeb8fa1

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

36aae07Trim some comments

comment:5 Changed 4 years ago by klee

  • Status changed from new to needs_review

comment:6 follow-up: Changed 4 years ago by tscrim

There are some doctest failures according to the patchbot. Some of them come the file name change, which technically you should deprecate the old file name (see #19879 for an example how to do this) if you think people could be importing directly from the file.

comment:7 Changed 4 years ago by git

  • Commit changed from 36aae0779df68316055119cd9c841a64aeeb8fa1 to 77a64da3c7b2eb3b5d0f8a9fca471a47f83524c0

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

77a64daFix a doctest failure due to a changed name

comment:8 in reply to: ↑ 6 Changed 4 years ago by klee

Replying to tscrim:

There are some doctest failures according to the patchbot. Some of them come the file name change, which technically you should deprecate the old file name (see #19879 for an example how to do this) if you think people could be importing directly from the file.

I regard it as an internal change. So there is no need to deprecate.

comment:9 Changed 4 years ago by klee

  • Status changed from needs_review to needs_work

The startup modules plugin complains that

New:
    _md5
    _sha
    _sha256
    _sha512
    sage.rings.function_field.element
    sage.rings.function_field.ideal
    sage.rings.function_field.order
Removed:
    _hashlib
    _ssl
    sage.rings.function_field.function_field_element
    ssl

I don't really understand what is happening and how to deal with it. I suspect that this is somehow related with __hash__ method in the ideal or order modules...

Travis, would you give me some tips?

comment:10 follow-up: Changed 4 years ago by tscrim

So the last three extra imports are from this change to function_field.py:

+from .order import (
+    FunctionFieldOrder_basis,
+    FunctionFieldOrderInfinite_basis,
+    FunctionFieldMaximalOrder_rational,
+    FunctionFieldMaximalOrder_global,
+    FunctionFieldMaximalOrderInfinite_rational,
+    FunctionFieldMaximalOrderInfinite_global)

However, you seem to basically be doing these imports locally anyways. I would run pyflakes on the file to see what is being duplicated in terms of imports, and you should decide if they need to be at the module level.

I probably wouldn't worry about the others as they seem to be unrelated.

comment:11 Changed 4 years ago by git

  • Commit changed from 77a64da3c7b2eb3b5d0f8a9fca471a47f83524c0 to 2811ce337e5e3193cf8149cc0641c688fda86667

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

f362751Merge branch 'develop' into function_fields_1
21d4b5bRemove imports from .order at module level
895c379Remove some more imports from module level
2811ce3Remove CAT from module level in function_field

comment:12 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by klee

Replying to tscrim:

So the last three extra imports are from this change to function_field.py:

+from .order import (
+    FunctionFieldOrder_basis,
+    FunctionFieldOrderInfinite_basis,
+    FunctionFieldMaximalOrder_rational,
+    FunctionFieldMaximalOrder_global,
+    FunctionFieldMaximalOrderInfinite_rational,
+    FunctionFieldMaximalOrderInfinite_global)

However, you seem to basically be doing these imports locally anyways. I would run pyflakes on the file to see what is being duplicated in terms of imports, and you should decide if they need to be at the module level.

I probably wouldn't worry about the others as they seem to be unrelated.

Ok. Let's see what would happen with new commits, though still I don't understand where

   _md5
    _sha
    _sha256
    _sha512

come from...

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

Replying to klee:

Ok. Let's see what would happen with new commits, though still I don't understand where

   _md5
    _sha
    _sha256
    _sha512

come from...

I don't know either. I suspect it is an artifact or bug in the plugin.

comment:14 Changed 3 years ago by git

  • Commit changed from 2811ce337e5e3193cf8149cc0641c688fda86667 to cf4b92b2f23c7294c8595498d7dfd8b316ab601c

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

cf4b92bRestore erroneously deleted valuation method

comment:15 Changed 3 years ago by klee

  • Status changed from needs_work to needs_review

comment:16 Changed 3 years ago by git

  • Commit changed from cf4b92b2f23c7294c8595498d7dfd8b316ab601c to e34194f7fade91f229d2549b77466b5685e53b1c

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

e34194fRestore ideal_with_gens_over_base method for rational function field

comment:17 Changed 3 years ago by klee

  • Description modified (diff)
  • Priority changed from minor to major

comment:18 follow-up: Changed 3 years ago by dimpase

  • Status changed from needs_review to needs_info

Why do you copy Singular's library code here? The latter is available in SAGE_LOCAL/share/singular/LIB/

E.g. normal.lib with normalP is there.

comment:19 in reply to: ↑ 18 Changed 3 years ago by klee

Replying to dimpase:

Why do you copy Singular's library code here? The latter is available in SAGE_LOCAL/share/singular/LIB/

E.g. normal.lib with normalP is there.

The code of this patch was written more than two years ago. It might be the case that the normal.lib was then an experimental package. But I don't remember well.

Another reason that may still be relevant now is that the normalP in the singular library does more computations than necessary for my case. For example, it also computes delta invariants of the given ideal. So I decided to make a stripped-down light version of normalP just for the code in this ticket.

comment:20 Changed 3 years ago by dimpase

  • Status changed from needs_info to needs_work

If it's a different version than the one in Singular, this should be made clear in the file header. The functions and .lib files also should be named differently, to prevent name clashes with the ones from the Singular lib.

comment:21 follow-up: Changed 3 years ago by dimpase

Anyway, unless Singular's own version is significantly slower, you should rather use it.

comment:22 in reply to: ↑ 21 Changed 3 years ago by klee

Replying to dimpase:

Anyway, unless Singular's own version is significantly slower, you should rather use it.

I am trying this approach. During computation, the Singular's version spits out many comments, each line starting with //, causing doctest failures. Do you know how to deal with this?

Failed example:
    O = F.maximal_order()
Expected nothing
Got:
    <BLANKLINE>
    // ** WARNING: result is correct if ideal is prime (not checked) **
    // disable option "isPrim" to decompose ideal into prime components
    <BLANKLINE>
    <BLANKLINE>
    // 'normalP' computed a list, say nor, of two lists:
    // To see the result, type
         nor;
    <BLANKLINE>
    // * nor[1] is a list of 1 ideal(s), where each ideal nor[1][i] consists
    // of elements g1..gk of the basering R such that gj/gk generate the integral
    // closure of R/P_i (where P_i is a min. associated prime of the input ideal)
    // as R-module in the quotient field of R/P_i;
    <BLANKLINE>
    // * nor[2] shows the delta-invariant of each component and of the input ideal
    // (-1 means infinite, and 0 that R/P_i is normal).

comment:23 Changed 3 years ago by klee

A small timing for you.

With my version:

sage:  K.<x> = FunctionField(GF(2));
sage: R.<t> = PolynomialRing(K);
sage: F.<y> = K.extension(t^4 + x^12*t^2 + x^18*t + x^21 + x^18)
sage: time F.maximal_order()
CPU times: user 178 ms, sys: 27.3 ms, total: 205 ms
Wall time: 201 ms

With Singular's version:

sage:  K.<x> = FunctionField(GF(2));
sage: R.<t> = PolynomialRing(K);
sage: F.<y> = K.extension(t^4 + x^12*t^2 + x^18*t + x^21 + x^18)
sage: time F.maximal_order()
//...
...
//...
CPU times: user 222 ms, sys: 31.3 ms, total: 254 ms
Wall time: 249 ms

comment:24 Changed 3 years ago by git

  • Commit changed from e34194f7fade91f229d2549b77466b5685e53b1c to 74b2e5098a644489bef564242e4bbebed034b604

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

74b2e50Rename normalP in core.lib to core_normalize

comment:25 Changed 3 years ago by klee

As using Singular's version has some technical problems noted above, I switched to the alternative path to renaming the procedure in core.lib

comment:26 Changed 3 years ago by klee

  • Status changed from needs_work to needs_review

comment:27 Changed 3 years ago by klee

  • Milestone changed from sage-8.3 to sage-8.4

comment:28 Changed 3 years ago by git

  • Commit changed from 74b2e5098a644489bef564242e4bbebed034b604 to b42ad6b02261c81d3eec04eb1da800c0bd306888

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

aa79205Add orders and ideals
b42ad6bRename files

comment:29 Changed 3 years ago by klee

I force-pushed two commits. The first commit contains all changes, and the second commit contains only filename changes.

Hopefully, a reviewer could see the changes against the devel branch more easily from the first commit.

comment:30 follow-up: Changed 3 years ago by tscrim

Can you do a rebase? If so, I will do the review for this in the next few days (now that I have freed up a bit of time).

comment:31 Changed 3 years ago by git

  • Commit changed from b42ad6b02261c81d3eec04eb1da800c0bd306888 to 5a67ee5e5f7dae6c7c9a1d00e1bf6aa5f35c8f1f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3cc6ecfAdd orders and ideals
5a67ee5Rename files

comment:32 in reply to: ↑ 30 Changed 3 years ago by klee

Replying to tscrim:

I will do the review for this in the next few days (now that I have freed up a bit of time).

Thank you, Travis. I thought of splitting this big patch into pieces, but it seemed difficult. If you find reviewing the patch annoying because of its size, let me know. Then I will try once again.

comment:33 follow-ups: Changed 3 years ago by tscrim

I have been able to make it through the code. I cannot vouch so much for the mathematical correctness, but it does work as documented. Here are my comments about the code:

  • For order_infinite_with_basis, did you want *basis instead of basis as an input (in which case, you will have to have check be part of a **kwds)? Or do you expect people to pass a list with a single list of basis elements inside?
  • Can you construct FunctionFieldMaximalOrder(Infinite)_global with having a different basis? It feels like these classes should just take one input, FunctionField(_global), which then has a hook to construct the corresponding basis (or maybe do this computation on-demand in the class itself). This would allow FunctionFieldOrder to inherit from UniqueRepresentation and maximal_order_infinite() to not be cached. I don't see how FunctionFieldOrder and subclasses are compared/hashed by default (the default Parent.__hash__ using the string representation is a horrible hash too).
  • I am pretty sure there is a bug in the caching of vector_space as the key is always return None, so the base parameter is ignored. Actually, you do not need to have a key here because you error out when base is not None. Is this for compatibility with something else? Does base**1 do something? I feel like it should just be base. I guess some of this is a hold-over from the old code, so it is not a big issue.
  • In all of the __init__ tests, it would be good to have TestSuite(I).run() (especially over a type(I) call IMO). I would also move the INPUT: block outside of the __init__ and into the class-level doc so that it is visible from the html doc.
  • Returns -> Return (in base_ring()).
  • Note that _rmul_ (like _lmul_) can have general input as they are designed to be hooks for actions. (Not that this is necessarily wrong here, but I just want to make sure this has all of the behaviors you are expecting.)
  • I don't see the point of having _gens_over_base. It is only called from gens_over_base and could be moved into there.
  • Instead of handling your own custom cache with _two_gens, I would just @cached_method gens_two.
  • You should make sure the result of basis_matrix is an immutable matrix by adding m.set_immutable().
  • I don't like avoiding self: it makes you have strange sentences like Return the ideal below the ideal., which I might even argue is close to ill-defined (which ideal is the ideal?).
  • Same comment about custom cache for _is_prime.
  • A better way from category or IntegralDomains() to get the category might be IntegralDomains().or_subcategory(category) (works fine when category=None). You can also then tack on category = category.Infinite() and then remove the is_finite method.
  • You don't need to cache ideal_monoid, at least the IdealMonoid class is better as a UniqueRepresentation.
  • Error messages should start with a lowercase letter (as per our convention).
  • Some little doc formatting things:
             - ``gens`` -- list of elements that are a basis for the
    -             ideal over the maximal order of the base field
    +           ideal over the maximal order of the base field
    
            - ``gens`` -- list of generators or an ideal in a ring which coerces
    -          to this order.
    +          to this order
    
  • Some micro-optimizations:
    -        basis = [V(sigma_a_pow[j]*beta_pow[i]) for i in range(s) for j in range(r)]
    +        basis = [V(sap * bp) for bp in beta_pow for sap in sigma_a_pow]
             W = V.span_of_basis(basis)
     
             def to_K(f):
                 coeffs = (f % q).list()
    -            return sum([sigma(coeffs[i]) * beta_pow[i] for i in range(len(coeffs))], K.zero())
    +            return sum((sigma(c) * beta_pow[i] for i, c in enumerate(coeffs)), K.zero())
     
             if r == 1: # take care of the prime field case
                 def fr_K(g):
                     co = W.coordinates(V(g),check=False)
                     return R([k(co[j]) for j in range(s)])
             else:
    -            t = r * s
                 def fr_K(g):
                     co = W.coordinates(V(g),check=False)
    -                return R([k(co[i:i+r]) for i in range(0,t,r)])
    +                return R([k(co[i:i+r]) for i in range(0,r*s,r)])
    
    (well, the last changes are for readability, less variables to keep track of).
  • Micro-optimization: in mul_vecs, you might want to move self._mtable[i] part out of the for j in range(n): loop to avoid the extra lookups.
  • I think it is bad form to use raises of errors to dictate program flow. I think a better way in _ideal_from_vectors_and_denominator (which should be faster too) is to have
                  M = []
                  g = d
                  for v in vecs:
                      for c in l:
                          g = g.gcd(c)
                          if g.is_one():
                              break
                      else:
                          M += l
                          continue
                      break
                  else:
                      d = d // g
                      mat = matrix(R, len(vecs), [c // g for c in M])
    
    where the else block is run iff the loop did not run to completion. You could also dispatch this to an internal function that would return mat or None upon failure.
  • Is there a clear benefit to having mtable a list of vectors, as opposed to a list of lists or a Matrix object?
  • Isn't this block of the div in Buchman-Lenstra algorithm just the same as mul_vec?
                          c = 0
                          for i in range(n):
                              for j in range(n):
                                  c += a[i] * b[j] * mtable[i][j]
    
    Perhaps there would be a benefit from cythonizing mul_vec considering how frequently it is used.

comment:34 in reply to: ↑ 33 Changed 3 years ago by klee

Replying to tscrim:

  • For order_infinite_with_basis, did you want *basis instead of basis as an input (in which case, you will have to have check be part of a **kwds)? Or do you expect people to pass a list with a single list of basis elements inside?

The code seems to be intended to support these three cases:

L.order_infinite_with_basis([1/x,1/x*y, 1/x^2*y^2])

L.order_infinite_with_basis([1/x])

L.order_infinite_with_basis(1/x)

But this is not described in the docstring. Also this is not consistent with order_with_basis. Hence I will remove the responsible code from order_infinite_with_basis. Happily, there is no doctest failure because of this.

comment:35 Changed 3 years ago by git

  • Commit changed from 5a67ee5e5f7dae6c7c9a1d00e1bf6aa5f35c8f1f to 9a1bbb268645c912b15ad1c610d96bbb37c211eb

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

9a1bbb2Remove unnecessary code from order_infinite_with_basis

comment:36 in reply to: ↑ 33 ; follow-up: Changed 3 years ago by klee

Replying to tscrim:

  • Can you construct FunctionFieldMaximalOrder(Infinite)_global with having a different basis?

No.

It feels like these classes should just take one input, FunctionField(_global), which then has a hook to construct the corresponding basis (or maybe do this computation on-demand in the class itself). This would allow FunctionFieldOrder to inherit from UniqueRepresentation and maximal_order_infinite() to not be cached. I don't see how FunctionFieldOrder and subclasses are compared/hashed by default (the default Parent.__hash__ using the string representation is a horrible hash too).

I followed your suggestion partially. Now FunctionFieldMaximalOrder class inherits UniqueRepresentation. So for maximal_order() and maximal_order_infinite() are not cached.

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Equation orders can have unique representation behavior. But I leave them just to be cached. I don't see a compelling reason to avoid using @cached_method for these. Do you have?

comment:37 Changed 3 years ago by git

  • Commit changed from 9a1bbb268645c912b15ad1c610d96bbb37c211eb to d4c8e8b0405203456928e8d6ee7b85b321805576

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

d4c8e8bInherit UniqueRepresentation to MaximalOrder class

comment:38 in reply to: ↑ 36 ; follow-up: Changed 3 years ago by tscrim

Replying to klee:

Replying to tscrim:

  • Can you construct FunctionFieldMaximalOrder(Infinite)_global with having a different basis?

No.

It feels like these classes should just take one input, FunctionField(_global), which then has a hook to construct the corresponding basis (or maybe do this computation on-demand in the class itself). This would allow FunctionFieldOrder to inherit from UniqueRepresentation and maximal_order_infinite() to not be cached. I don't see how FunctionFieldOrder and subclasses are compared/hashed by default (the default Parent.__hash__ using the string representation is a horrible hash too).

I followed your suggestion partially. Now FunctionFieldMaximalOrder class inherits UniqueRepresentation. So for maximal_order() and maximal_order_infinite() are not cached.

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Thank you.

Equation orders can have unique representation behavior. But I leave them just to be cached. I don't see a compelling reason to avoid using @cached_method for these. Do you have?

They are subclasses of Parent, correct? Things work faster/better in regard to, say, coercion and equality with UniqueRepresentation. It is also faster to compare for equality and hash (just use the id in both cases). Speaking of which, because of the MRO, it is better to have UniqueRepresentation as the first class.

It also means the cache is tied with the object itself rather than a creation method. Say, someone else creates a (maybe completely separate) class that wants to use the basis classes. They would also have to implement a cache, which would either create two copies of the same object or have to make the two caches interact; both of which I think are bad.

FYI - if you do really only want cached behavior, there is a CachedRepresentation class you could use. However, I don't see a reason why not to upgrade to the UniqueRepresentation here.

comment:39 in reply to: ↑ 38 ; follow-up: Changed 3 years ago by klee

Replying to tscrim:

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Thank you.

There was a typo here. I meant:

Order_basis class does *not* have unique representation behavior. It could have cached representation behavior. But I don't see a reason to force this.

Equation orders can have unique representation behavior. But I leave them just to be cached. I don't see a compelling reason to avoid using @cached_method for these. Do you have?

They are subclasses of Parent, correct? Things work faster/better in regard to, say, coercion and equality with UniqueRepresentation. It is also faster to compare for equality and hash (just use the id in both cases). Speaking of which, because of the MRO, it is better to have UniqueRepresentation as the first class.

Ok. I will make this fix.

It also means the cache is tied with the object itself rather than a creation method. Say, someone else creates a (maybe completely separate) class that wants to use the basis classes. They would also have to implement a cache, which would either create two copies of the same object or have to make the two caches interact; both of which I think are bad.

I agree. But EquationOrder(Infinite) class is something that I do not expect to be subclassed. Anyway now it occurs to me that I can just get rid of this class, and use the superclassOrder_basis.

comment:40 in reply to: ↑ 39 Changed 3 years ago by tscrim

Replying to klee:

Replying to tscrim:

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Thank you.

There was a typo here. I meant:

Order_basis class does *not* have unique representation behavior. It could have cached representation behavior. But I don't see a reason to force this.

If you expect to create elements of this class and implement coercions between them, then it makes the mechanisms in the coercion framework work a lot better and faster. In addition to the reasons given below. However, this is only a suggestion, and I don't have a strong preference (or a stake in the outcome). If you prefer it this way, then that is fine with me.

It also means the cache is tied with the object itself rather than a creation method. Say, someone else creates a (maybe completely separate) class that wants to use the basis classes. They would also have to implement a cache, which would either create two copies of the same object or have to make the two caches interact; both of which I think are bad.

I agree. But EquationOrder(Infinite) class is something that I do not expect to be subclassed. Anyway now it occurs to me that I can just get rid of this class, and use the superclassOrder_basis.

Okay, but someone might have a completely different class that would call it. For example, someone implements a 3rd party library for function fields that we tie into Sage, but you still would want to have a method, say, equation_order from that new implementation. This would give the situation I am describing above. Granted, this is not so likely, but it is better to future-proof when there is little cost to complexity IMO.

comment:41 Changed 3 years ago by git

  • Commit changed from d4c8e8b0405203456928e8d6ee7b85b321805576 to 5ee44a2444d32f5521664edd1730d51f94bdd1e7

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

5ee44a2Inherit CachedRepresentation to Order_basis class

comment:42 in reply to: ↑ 33 ; follow-up: Changed 3 years ago by klee

Replying to tscrim:

  • I am pretty sure there is a bug in the caching of vector_space as the key is always return None, so the base parameter is ignored. Actually, you do not need to have a key here because you error out when base is not None. Is this for compatibility with something else? Does base**1 do something? I feel like it should just be base. I guess some of this is a hold-over from the old code, so it is not a big issue.

This is not my code. But it seems not a bug to me. The intention is to force base to self (a rational function field) if given, since self is the only reasonable base field for a rational function field. If F is a rational function field,

F.vector_space()  ---> Ok. The base is F.
F.vector_space(F) ---> Ok. The base is F.
F.vector_space(G) ---> Raise an error.

For the first two cases, the cache key is None. On the other hand, base**1 creates a vector space over base of dimension 1.

comment:43 Changed 3 years ago by git

  • Commit changed from 5ee44a2444d32f5521664edd1730d51f94bdd1e7 to 12a78a0e745bcf471e1f46a6660ea1a56800715d

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

12a78a0Move INPUT fields to the class docstrings

comment:44 Changed 3 years ago by git

  • Commit changed from 12a78a0e745bcf471e1f46a6660ea1a56800715d to b563d674edccf778828379dcae98c22da1ada080

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

b563d67Fix Returns to Return

comment:45 in reply to: ↑ 42 ; follow-up: Changed 3 years ago by tscrim

Replying to klee:

Replying to tscrim:

  • I am pretty sure there is a bug in the caching of vector_space as the key is always return None, so the base parameter is ignored. Actually, you do not need to have a key here because you error out when base is not None. Is this for compatibility with something else? Does base**1 do something? I feel like it should just be base. I guess some of this is a hold-over from the old code, so it is not a big issue.

This is not my code. But it seems not a bug to me. The intention is to force base to self (a rational function field) if given, since self is the only reasonable base field for a rational function field. If F is a rational function field,

F.vector_space()  ---> Ok. The base is F.
F.vector_space(F) ---> Ok. The base is F.
F.vector_space(G) ---> Raise an error.

For the first two cases, the cache key is None. On the other hand, base**1 creates a vector space over base of dimension 1.

Ah, right, that shorthand. It would definitely improve readability to have it be FreeModule(base, 1), but it is not important as it is just looks like a change because of the refactoring. I just do not see why vector_space should take an argument. Everything about that code says it should not have any arguments and you can should just replace base with self. Unless it is for some consistency or used in some other more general context?

comment:46 in reply to: ↑ 45 ; follow-up: Changed 3 years ago by klee

Replying to tscrim:

Replying to klee:

Replying to tscrim:

  • I am pretty sure there is a bug in the caching of vector_space as the key is always return None, so the base parameter is ignored. Actually, you do not need to have a key here because you error out when base is not None. Is this for compatibility with something else? Does base**1 do something? I feel like it should just be base. I guess some of this is a hold-over from the old code, so it is not a big issue.

This is not my code. But it seems not a bug to me. The intention is to force base to self (a rational function field) if given, since self is the only reasonable base field for a rational function field. If F is a rational function field,

F.vector_space()  ---> Ok. The base is F.
F.vector_space(F) ---> Ok. The base is F.
F.vector_space(G) ---> Raise an error.

For the first two cases, the cache key is None. On the other hand, base**1 creates a vector space over base of dimension 1.

Ah, right, that shorthand. It would definitely improve readability to have it be FreeModule(base, 1), but it is not important as it is just looks like a change because of the refactoring. I just do not see why vector_space should take an argument. Everything about that code says it should not have any arguments and you can should just replace base with self. Unless it is for some consistency or used in some other more general context?

It is for consistency. Note that general function fields also have vector_space, for which it is reasonable to take a base argument. Thus, perhaps, one can write generic code for function fields, rational or not. This is not my design.

comment:47 in reply to: ↑ 46 Changed 3 years ago by tscrim

Replying to klee:

It is for consistency. Note that general function fields also have vector_space, for which it is reasonable to take a base argument. Thus, perhaps, one can write generic code for function fields, rational or not. This is not my design.

Fair enough. I only really noticed it because of the refactoring.

I think the only last thing to do is to have a doctest in each of the __init__ methods that simply created the corresponding object and runs TestSuite(foo).run(). Otherwise, I think that takes care of everything. Thank you.

comment:48 Changed 3 years ago by git

  • Commit changed from b563d674edccf778828379dcae98c22da1ada080 to 8dd263994dc1a83e2f88193bd491d47018ce2d6a

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

8dd2639Add TestSuites for each __init__ method

comment:49 follow-up: Changed 3 years ago by klee

It was instructive to add TestSuites for all parents. I could finally understand the basics of the interplay of Parents, Elements, and Categories. Thank you.

I will take care of other comments after a week long national holidays.

comment:50 in reply to: ↑ 49 ; follow-up: Changed 3 years ago by tscrim

Replying to klee:

It was instructive to add TestSuites for all parents. I could finally understand the basics of the interplay of Parents, Elements, and Categories. Thank you.

I am glad to hear you were able to learn some new stuff. It looks like you were able to reduce the redundancy.

I have a few additional small comments:

Error messages should not be proper sentences (so not starting with a capital letter and ending with a period/full-stop):

-        if n != 0: raise IndexError("Only one generator.")
+        if n != 0:
+            raise IndexError("only one generator")
         return self._gen

(This is a general Python convention.) Same also for raise IndexError("Only {} generators".format(self.ngens())).

These type of changes do not seem to be correct to me:

        m = self.ideal_monoid()
        m.Element = FunctionFieldIdeal_rational

The Element attribute should be set by the corresponding parent before Parent.__init__ is called, as does the appropriate setup (e.g., constructing element_class). The thing do do would be to have a hook (via a attribute) that is looked at by IdealMonoid in its __init__ which then sets its Element attribute, e.g.:

self.Element = R._ideal_class

Also, is there a use-case for someone to pass an ideal_class to ideal or ideal_with_gens_over_base? If so, then this hook I mentioned above should be removed and the ideal_class should instead be an additional construction parameter for IdealMonoid.

Trivial formatting:

         - ``gens`` -- list of elements that are a basis for the
-              ideal over the maximal order of the base field
+          ideal over the maximal order of the base field

If you want to enforce a particular subcategory for input, you can do:

-category or IntegralDomains()
+category = IntegralDomains().or_subcategory(category)

(for None, this becomes IntegralDomains()).

I can also look into why the facade parents are not behaving well once the above is done.

I will take care of other comments after a week long national holidays.

No problem. Enjoy your holidays.

comment:51 Changed 3 years ago by git

  • Commit changed from 8dd263994dc1a83e2f88193bd491d47018ce2d6a to b255323c626de3c39a13b43c622d3f12ad3699d9

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

c722247fix error messages to start in lower case
950389ffix doctest errors; reorganize ideal_class
b255323use .or_subcategory

comment:52 in reply to: ↑ 50 Changed 3 years ago by klee

Replying to tscrim:

These type of changes do not seem to be correct to me:

        m = self.ideal_monoid()
        m.Element = FunctionFieldIdeal_rational

The Element attribute should be set by the corresponding parent before Parent.__init__ is called, as does the appropriate setup (e.g., constructing element_class). The thing to do would be to have a hook (via a attribute) that is looked at by IdealMonoid in its __init__ which then sets its Element attribute, e.g.:

self.Element = R._ideal_class

Ok.

Also, is there a use-case for someone to pass an ideal_class to ideal or ideal_with_gens_over_base? If so, then this hook I mentioned above should be removed and the ideal_class should instead be an additional construction parameter for IdealMonoid.

Perhaps not. This is a left-over from existing code. I tried to clean this up.

I can also look into why the facade parents are not behaving well once the above is done.

The function field orders are facade parents, because the parent of elements of an order is just the function field. What seems to me a bug is that some category tests intended for normal parents are still applied to facade parents. For example, _test_one, _test_zero.

comment:53 Changed 3 years ago by git

  • Commit changed from b255323c626de3c39a13b43c622d3f12ad3699d9 to 086f278aa668f6608b58bb2b90e0d9a6af9f6427

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

086f278remove unused _gens_over_base

comment:54 in reply to: ↑ 33 Changed 3 years ago by klee

Replying to tscrim:

  • I don't see the point of having _gens_over_base. It is only called from gens_over_base and could be moved into there.

I guess _gens_over_base was introduced for efficiency when I implemented "places" and "divisors" on top of orders and ideals. As that is not needed here, I removed it. I may reintroduce it in a later ticket.

comment:55 Changed 3 years ago by git

  • Commit changed from 086f278aa668f6608b58bb2b90e0d9a6af9f6427 to fe77aea269e008196e163e55d193cf7430e5ff94

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

b9baf20remove custom caches
fe77aeaset basis_matrix immutable

comment:56 Changed 3 years ago by git

  • Commit changed from fe77aea269e008196e163e55d193cf7430e5ff94 to 8e2445642e3c6510e343785c3441e6c6524fa725

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

8e24456make some docstrings clearer

comment:57 in reply to: ↑ 33 Changed 3 years ago by klee

Replying to tscrim:

  • I don't like avoiding self: it makes you have strange sentences like Return the ideal below the ideal., which I might even argue is close to ill-defined (which ideal is the ideal?).

I like to avoid self, at least to be consistent, and follow the developer manual. Anyway, I tried to remove the ambiguities you mentioned.

comment:58 Changed 3 years ago by git

  • Commit changed from 8e2445642e3c6510e343785c3441e6c6524fa725 to 01be0ebf16e0ad64422840fa98d1af98b6707858

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

01be0ebremove is_finite method

comment:59 Changed 3 years ago by git

  • Commit changed from 01be0ebf16e0ad64422840fa98d1af98b6707858 to 3329dc0696566616621c0287378da4d192e97624

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

504c9e4remove @cached_method from ideal_monoid
3329dc0Travis' various optimizations

comment:60 in reply to: ↑ 33 Changed 3 years ago by klee

Replying to tscrim:

  • Micro-optimization: in mul_vecs, you might want to move self._mtable[i] part out of the for j in range(n): loop to avoid the extra lookups.

The benefit seems negligible. I left this as it is, for readability.

  • Is there a clear benefit to having mtable a list of vectors, as opposed to a list of lists or a Matrix object?

It is a list of a list of vectors.

Perhaps there would be a benefit from cythonizing mul_vec considering how frequently it is used.

Locating parts to be cythonized is a general issue that I should tackle some day, after learning more cython.

comment:61 Changed 3 years ago by git

  • Commit changed from 3329dc0696566616621c0287378da4d192e97624 to 31434b906999be98d6d69f903c52e9f6c3e263af

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

31434b9Merge branch 'develop'

comment:62 follow-up: Changed 3 years ago by tscrim

Thank you for all of your changes. LGTM.

I don't think it is exactly fair to quote the developers manual when you were the one who rewrote that part of the developers manual on self.

comment:63 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

comment:64 in reply to: ↑ 62 Changed 3 years ago by klee

Replying to tscrim:

Thank you for all of your changes. LGTM.

I don't think it is exactly fair to quote the developers manual when you were the one who rewrote that part of the developers manual on self.

I feel sorry about that. I read the part again. It implicitly states self should be used if confusion incurs from not using it. So your recommendation above is quite legitimate, and so is my response :-)

comment:65 Changed 3 years ago by git

  • Commit changed from 31434b906999be98d6d69f903c52e9f6c3e263af to c04dd8bd8aabd9a959f3d705c1293e9e5e8828c2
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

54ae894make TestSuite(O) run better for order O
c04dd8bremove Order and Ideal classes from startup modules

comment:66 Changed 3 years ago by klee

Sorry for adding commits after review. I worked a bit more while responding to patchbot plugin failures.

comment:67 Changed 3 years ago by tscrim

That is fine. One little thing with this change:

@@ -817,12 +821,9 @@ class FunctionFieldMaximalOrder_rational(FunctionFieldMaximalOrder):
 
         TESTS:
 
-        This class defines a facade parent. Thus it does not behave well with
-        respect to elements.
-
             sage: K.<t> = FunctionField(QQ)
             sage: O = K.maximal_order()
-            sage: TestSuite(O).run(skip=['_test_euclidean_degree', '_test_gcd_vs_xgcd', '_test_one', '_test_zero'])
+            sage: TestSuite(O).run(skip='_test_gcd_vs_xgcd')
         """
         FunctionFieldMaximalOrder.__init__(self, field, ideal_class=FunctionFieldIdeal_rational,
                                            category=EuclideanDomains())

Should become TESTS::.

comment:68 Changed 3 years ago by git

  • Commit changed from c04dd8bd8aabd9a959f3d705c1293e9e5e8828c2 to 6c966072e2e89c6a483517b9721f11a74138e40c

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

6c96607fix for docbuild failure

comment:69 Changed 3 years ago by git

  • Commit changed from 6c966072e2e89c6a483517b9721f11a74138e40c to 48100b41622d43e75c263cf62b32be9b335d88f6

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

48100b4fix : to ::

comment:70 follow-up: Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

Thank you.

comment:71 in reply to: ↑ 70 ; follow-up: Changed 3 years ago by klee

Replying to tscrim:

Thank you.

Thank you for helping me step forward!

comment:72 in reply to: ↑ 71 Changed 3 years ago by tscrim

Replying to klee:

Replying to tscrim:

Thank you.

Thank you for helping me step forward!

No problem. Sorry it took so long for me to get to this.

comment:73 Changed 3 years ago by vbraun

  • Branch changed from u/klee/25435 to 48100b41622d43e75c263cf62b32be9b335d88f6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.