implement general package for finitely generated not-necessarily free R-modules

[williamstein]

I really need this for my research.

Note, I only really need the case R=ZZ, and what I'll implement is likely to be this for any R that has a Smith normal form algorithm, e.g., class number 1.

I am finding and fixing some major bugs in basic linear algebra that have to be fixed in order to implement this. Thus this patch depends on: #5886, #5887, #5972, #5974

CC: @jhpalmieri @loefflerd @antieau

Component: linear algebra

Author: William Stein, David Loeffler

Reviewer: Robert Miller, John Palmieri

Merged: sage-4.1.rc0

Issue created by migration from https://trac.sagemath.org/ticket/5882

[williamstein]

comment:3

NOTE: trac_5882-part2.patch (which I'll post soon) fixes numerous major bugs in matrix_morphism.py, e.g., in restrict_domain and restrict_codomain. I noticed these issues while reading the code and thinking about what it did...

[williamstein]

comment:6

This is likely ready for review, but I want to do some additional testing before labeling it as such.

[williamstein]

comment:8

I've changed this back to "not ready for review", since I think it's more likely to be higher quality code if I implement something nontrivial on top of it first, and fix any issues I find. So I'm doing #5969 first. Once that's done and I fixed all issues that crop up, then #5882 will be ready for review.

[williamstein]

comment:9

The one remaining problem: Some of the bug fixes in linear algebra included in this patch (or possibly, but unlikely, the dependency patches), cause a serious performance regression:

IN SAGE-3.4.1:

sage: time EllipticCurve('858k2').sha().an_padic(Integer(7))
CPU times: user 8.65 s, sys: 0.37 s, total: 9.02 s

After these patches the same takes much much longer (many minutes). Using set_verbose(2) one sees that the codepaths are different.

It's not surprising that fixing bugs would uncover other buggy code and major performance issues, since buggy code is often very fast :-).

[williamstein]

comment:11

With these patches and dependencies installed, make ptestlong:

All tests passed!
Timings have been updated.
Total time for all tests: 331.9 seconds
wstein@sage:~/build/sage-3.4.2.rc0$ 

[williamstein]

comment:12

It turns out there is a bug in 5882 still. In the following example, computing the kernel of f is wrong, because f somehow gets defined by a map on free modules V-->V that doesn't preserve the W's that we're quotienting out by. Trac 5882 is basically the ultimate generalization of that round2 problem everybody was confused by in 583 last quarter -- it's hard to get right!

sage: V = span([[1/14,3/14],[0,1/2]],ZZ); W = ZZ^2
sage: Q = V/W
sage: f = Q.hom([Q([1,11]), Q([1,3])])
sage: f
Morphism from module over Integer Ring with invariants (2, 14) to module with invariants (2, 14) that sends the generators to [(1, 11), (1, 3)]
sage: f.kernel()
Finitely generated module V/W over Integer Ring with invariants (14)
sage: f.image()
Finitely generated module V/W over Integer Ring with invariants (14)
sage: f._phi
Free module morphism defined by the matrix
[ 11 -10]
[  3  -2]
Domain: Free module of degree 2 and rank 2 over Integer Ring
User basis ...
Codomain: Free module of degree 2 and rank 2 over Integer Ring
Echelon ...
sage: R = Q.optimized()[0]; R
Finitely generated module V/W over Integer Ring with invariants (2, 14)
sage: f._phi(R.W()).is_submodule(W)
False

[JohnCremona]

comment:13

Any chance you could combine the 7 (!) patches into one? That will make it a lot easier to read & judge, and to apply, of course!

[williamstein]

comment:14

Any chance you could combine the 7 (!) patches into one? That will make it a
lot easier to read & judge, and to apply, of course!

Yes, I will, when it is ready for review.

Also, I'll rename the V, W methods to cover and relations, with C() and R() as aliases.

[antieau]

comment:17

I like what I see in this patch. Especially the ability to lift an element of a quotient. Using this, one can create the long exact sequence associated to an exact sequence of chain complexes.

[williamstein]

Attachment: trac_5882.patch.gz

this one patch is based against 4.0.2.rc3. it replaces the 8 patches from before.

[williamstein]

comment:18

OK, this should get reviewed. I think it's probably quite slow right now -- I make no claims to speed at all. But as far as I know it is right.

[rlmill]

Reviewer: Robert Miller

[rlmill]

comment:19

Since underscore methods don't show up under ReST documentation, I think all the documentation which falls under __init__ methods should be either moved or copied to the class level documentation.

[rlmill]

Author: William Stein

[rlmill]

comment:20

Some typos maybe: Should "optimization representation" be "optimized representation?"

[rlmill]

comment:21

Applied to Sage-4.0.2, all doctests pass with -long.

[rlmill]

comment:22

Maybe this is silly, but when I do:

sage: F = FreeModule(ZZ, 10)
sage: K = F.span([F.0 + 4*F.1,5*F.2,3*F.3])
sage: X = F/K
sage: X.<tab>

I don't see Hom, V and W, because they are the only capitalized methods listed at all, and so they come before all the underscore stuff, and I automatically don't look at the beginning of the list because I'm never looking for underscore methods. As far as I know, all methods of classes are lowercase. Also, V and W seem like maybe bad choices of names. As soon as you do sage: X.V?, you immediately see what it is, but if you're scanning over what you get from tab completion, you might completely ignore it...

[williamstein]

Attachment: trac_5882-full_ref_report-comments_addressed.patch.gz

[jhpalmieri]

Changed author from William Stein to William Stein, David Loeffler

[jhpalmieri]

comment:44

Okay, this is great. Positive review.

The ticket is a bit of a mess, though: davidloeffler's and was's most recent patches conflict. I've taken the liberty of creating a single patch, containing all of the others, and merging the few differences between these two conflicting patches. (I'm taking William's side on annihilator -- it should return an ideal.) My patch also includes a few trivial fixes: two typos, and a rewording of the annihilator docstring so that the second line takes into account that it returns an ideal, not an element. You can see my changes in "trac_5882_delta.patch"; this is for reference only.

I think that the "Author" and "Reviewer" fields are filled in accurately.

Apply only "trac_5882-all-in-one.patch".

[jhpalmieri]

Attachment: trac_5882-delta.patch.gz

for reference only

[jhpalmieri]

apply only this patch!

[rlmill]

comment:45

Attachment: trac_5882-all-in-one.patch.gz

There is one doctest failure:

sage -t  sage/modules/fg_pid/fgp_module.py
**********************************************************************
File "/space/rlm/sage-4.1.alpha3/devel/sage-main/sage/modules/fg_pid/fgp_module.py", line 1453:
    sage: hash(A)
Expected nothing
Got:
    -7071641102956720018
**********************************************************************

[jhpalmieri]

comment:46

Sorry, that's what I get for only doctesting on a 32-bit machine. Here's a patch.

[jhpalmieri]

Attachment: trac_5882_hash.patch.gz

[jhpalmieri]

comment:48

Re William's comments:

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?

Because when I wrote that, I was having a mathematical brain freeze. It's fine the way it is.

The documentation builds fine, by the way.

[rlmill]

Merged: sage-4.1.rc0