#5882: [with patch; needs final review] implement general package for finitely
generated not-necessarily free R-modules
------------------------------------------+---------------------------------
Reporter: was | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.1
Component: linear algebra | Keywords:
Reviewer: Robert Miller, John Palmieri | Author: William Stein
Merged: |
------------------------------------------+---------------------------------
Comment(by was):
RESPONSE TO ALL REFEREE COMMENTS IN WHICH EVERYTHING IS ADDRESSED. A
patch will be posted in a moment too.
> in inverse_image, is there any speed gain if you check whether the rank
of the homomorphism is zero at the beginning? that is, change
DONE
> A very minor issue: In inverse_image, in the lines
> if R.is_field():
> # By solving, find lifts of each of the basis elements of V.
> # Each row of Y gives a linear combination of the basis for
the domain
> # that maps to one of the basis elements V.
> C = A.solve_left(B)
> change "Each row of Y" to "Each row of C"?
DONE
>
> *******************************************
>
> fgp_module.py:
>
> the function FGP_Module: documentation should say what it returns: V/W
as a f.g. R-module. For the inputs, V and W need to be free R-modules.
DONE
> _coerce_map_from_: I think that V/W should have a coercion from V, so
testing isinstance(S, FGP_Module_class) won't work. More generally, you
should have coercions from anything of the form V/W' to V/W, as long as W'
is contained in W: that is, you should have coercions not just from
submodules, but also from modules with canonical surjections onto V/W.
(There may be many maps from V to V/W, but there is one *canonical* map,
so I think there should be a coercion map.)
DONE
> in free_module.py, there is a __cmp__ method but not an __eq__ method,
and here it's the other way around. Is this an issue? Do we have a policy
about which one to use?
I think __eq__ is better since A < B suggest to a lot of people that
"A is contained in B", which isn't the case at all. But I don't want
to potentially break the API of the general free_module code in this
patch.
> Here's a problem with is_submodule:
>
> sage: V = FreeModule(ZZ, 1)
> sage: W = V.submodule([0*V.0])
> sage: W2 = V.submodule([2*V.0])
> sage: V/W # isomorphic to Z
> Finitely generated module V/W over Integer Ring with invariants (0)
> sage: V/W2 # isomorphic to Z/2Z
> Finitely generated module V/W over Integer Ring with invariants (2)
> sage: (V/W).is_submodule(V/W2)
> True
>
> This is because the implementation is wrong: if you want V/W to be a
submodule of V'/W', then you want V to be a submodule of V', and the
inclusion map should induce a surjection of W onto W' (hence an
isomorphism between W and W' -- given an injection V --> V' which induces
a map W --> W', the induced map must be an injection also). Should you
change the end from
>
> return self.V().is_submodule(A.V()) and
self.W().is_submodule(A.W())
>
> to
>
> return self.V().is_submodule(A.V()) and self.W() == A.W()
DONE -- good change. David Loeffler also found this issue and "fixed"
the code, but his fix was wrong too (it basically ignored the V's).
By the way, after making the above fix then running doctests, the
automated randomized testing code *did* find a bug in the image
command. I fixed that by changing
V = self._phi.image()
to
V = self._phi.image() + self.codomain().W()
in the image method in fgp_morphism.py
> The docstring should be changed to reflect this, as should the doctests;
in the existing doctests, I don't think that A is actually a submodule of
Q. In the simpler (but somewhat analogous) situation of Z/2Z and Z/4Z,
then although abstractly Z/2Z is a submodule of Z/4Z, the identity map Z
--> Z does not induce the inclusion. The identity map Z --> Z induces an
inclusion 4Z --> 2Z, which then induces a *surjection* Z/4Z --> Z/2Z.
>
> Also, the first sentence of the docstring is wrong: it says "Return True
if A is a submodule of self", and it should be "Return True if self is a
submodule of A".
DONE
>
> base_ring: delete the comment (# this will be done in __init__)?
DONE
>
> _smith_form_: document the form of the output, or at least give a
reference to smith_form from matrix2.pyx.
DONE.
Also, I changed all the smithform's to smith_form's, which David L.
introduced.
> invariants needs a docstring, not just doctests. (The term "invariants"
is used frequently in fgp_module.py, but is never defined.) Document the
argument "include_ones"?
done.
>
> gens: in the docstring, change "lements" to "elements". Change it to
"elements g0,...,gn of self"? (Add "of self"?)
DONE
>
> is it worth changing "isinstance(x, FGP_Module_class)" to
"is_FGP_Module(x)" many places in this file? (Otherwise, is
"is_FGP_Module" used anywhere? We could delete it...)
Yes, DONE.
> I'm still working on this file, and I haven't looked at fgp_morphism or
fgp_element in any detail yet (except to note that the in the docstring
for FGP_Morphism, the comment "where the morphism doesn't extend to V1"
needs to be rephrased). I'm going on a family trip tomorrow, though, so I
may not have time to work on this for a few days.
done.
> My next installment: this finishes up with the file fgp_module.py.
>
> coordinate_vector:
>
> self.optimized() # computes T as side effect -- see above
>
> Should say "see below", I think.
DONE
>
> optimize: in the comments
>
> # Compute matrix X of linear transformation from self._V to V.
> # This matrix X gives each basis element of self._V in terms
> # of our new optimized V, modulo the W's.
>
> Maybe "X" should be replaced by "T". If not, then "T" should be
described, since it's cached, and so is presumably important.
DONE. I called it X at one point, e.g., in my doodles, but changed to T.
> hom: if len(im_gens) == 0, then we can't use M.hom(...) to define the
zero map to another module. Should we be able to? That is, should we be
able to specify the codomain explicitly instead of the method using N =
im_gens.universe()?
DONE -- You're right, yes, we should be able to. I implemented hom wrong,
since hom should have an optional codomain parameter. Fixed.
> random_element: wouldn't it be better to pick a random element from
self.optimized()[0]._V?
I'm really not sure. Conceptually if one constructs A = V/W, then it
is easiest to think of random_element as "Create a random element of
self=V/W, by creating a random element of V and reducing it modulo W."
The optimized() thing doesn't seem so canonical in terms of the given
input. So I'm definitely not so sure. Why do you think that would be
better? Efficiency?
>
> right before random_fgp_module: ZZ has already been imported
DONE.
> random_fgp_module: say that R is optional, default ZZ
DONE
> ***********************
>
> A general question: What's the obstruction to implementing this for
modules over k[x], for k a field, or for general PIDs? This should be
documented somewhere so interested people know what to work on.
>
DONE - in the very top of fgp_module.py
> ***********************
>
> I hope to get to the last two files soon.
> Okay, I'm done with my review. Earlier, I discussed everything except
the files "fgp_element.py" and "fgp_morphism.py". The file
"fgp_element.py" looks good to me. The file "fgp_morphism.py" is mostly
good, but I have a few comments:
>
> FGP_Morphism: as mentioned avove, need to fix the part of the docstring
which says "where the morphism doesn't extend to V1"
DONE
> FGP_Morphism, __init__: can we delete the line
>
> from sage.matrix.all import diagonal_matrix
DONE
>
> Also in __init__: Do you expect the error messages like "domain of phi
must be V for MO" to ever appear? They are pretty cryptic -- if you
haven't read the code, you won't know what "V for MO" means.
DONE.
> In __call__: when x is an FGP_Module, should you check that x is a
submodule of self.domain() and return an appropriate error if not?
DONE, and I added some doctests.
> I note that in "image", you call FGP_Module with check=False, but you
don't have this in "kernel". Should you use check=False there, too?
DONE -- I've changed all the "internal checks" (not things passed in by
the
user) to use the DEBUG flag in fgp_module.py. Then one can uniformly
turn them all on/off. I think it is best to leave all the checks on
for now, but turn them off after the code has been out in the wild for
a while, and work has gone into optimizing it (so far 0 work has gone
into optimization).
>
> Should "preimage" be a synonym for "lift"? Or should there be a method
"preimage" which acts like "lift" on elements, but also works on
submodules?
>
Hmm. Actually, we should have at least inverse_image as a method on
morphisms of fgp modules, since that isn't there at all! It was
important to add this method to fg modules, and should be easy on fgp
modules. This provides the same functionality as preimage. I think
preimage would be good to add, but then it should be added for fg free
modules too, so it's best to wait for another ticket and do it right.
> In _coerce_map_from_: should there be a coercion from Hom(X,Y) to
Hom(X,Z) if there is a coercion from Y to Z? Should there be a coercion
from Hom(X,Y) to Hom(W,Y) if there is a coercion from W to X?
>
Yes, yes, but I don't know if this will work, since at least currently
that function returns bool rather than the actual map. Also, the same
should be added to free modules. I think this would be better to do
on another ticket.
> Overall, this is very impressive, and it will be great to have this as
part of Sage.
FOR NEW TICKETS:
* Add a method "preimage" that acts like "lift" on elements, but also
works on submodules.
* There should be a coercion from Hom(X,Y) to Hom(X,Z) if there is a
coercion from Y to Z. There should there be a coercion from Hom(X,Y)
to
Hom(W,Y) if there is a coercion from W to X.
From David Loeffler:
> I have been working on this as part of a Sage Days 16 project to
reimplement abelian groups. The above patch:
>
> - adds new methods _element_class and _subquotient_class which can be
overridden by derived classes
Looks good to me.
> - adds a new method has_canonical_map_to which does what is_submodule
previously did, and changes is_submodule so it is true if and only if the
canonical map exists *and is injective*.
good
> - adjusts some things relating to gens, so derived classes can have
generators which are not necessarily in Smith form, and made the necessary
corresponding changes to hom. There are now separate methods
smithform_gens and gens, and the "internal" uses of generators all call
smithform_gens, so it is safe for derived classes to override gens.
>
good, except I changed it to smith_form_gens (!)
> I *haven't* changed the printing code, as I threatened to do last week
-- on reflection I decided that elements comparing as equal and printing
as unequal was just too confusing.
Yep.
From John:
> adds new methods _element_class and _subquotient_class which can be
overridden by derived classes
>
> In the docstring for _element_class, should "creating subquotients" say
"creating elements"?
DONE
>
> changes is_submodule
>
> I like your change, but I would like is_submodule to have more
documentation, saying (for example) that it returns True if self.V() is a
submodule of A.V(), with self.W() equal to A.W().
DONE
> I don't have much of an opinion about this either way, but do you want
to rename smithform_gens to _smithform_gens so it's less visible?
After hearing how say Henri Cohen thinks about abelian groups, I think
it is probably a good idea having smith_form_gens be user-visible.
It's an important function, and pretty canonical, and will be used
from outside the class (that was the motivation for introducing it).
>
> For annihilator: the first line of the docstring ends a bit abruptly.
Should this method return an actual ideal, not just an element of the
ring?
DONE, and added another doctest that illustrates the case when the
annihilator is 0. Yes, it should return an ideal, and I fixed it so
it will.
David said:
> For annihilator, essentially it is just there so I can use it to do
> exponent for abelian groups, so I do want it to return an element.
Well in the docstring you wrote *ideal*. And it straightforward to
get the generator of an ideal, so I made it an ideal.
We're going to generalize all this soon enough to general commutative
base rings (singular supports this sort of thing well, actually), and
when we do so as much as possible we'll want to have a consistent API.
So we should make annihilator return an ideal.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5882#comment:43>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
