Opened 10 years ago
Closed 10 years ago
#10746 closed enhancement (fixed)
Refactor matrix kernel routines
Reported by: | rbeezer | Owned by: | jason, was |
---|---|---|---|
Priority: | critical | Milestone: | sage-4.7.1 |
Component: | linear algebra | Keywords: | |
Cc: | jason, spancratz, stumpc5 | Merged in: | sage-4.7.1.alpha2 |
Authors: | Rob Beezer | Reviewers: | Christian Stump |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch reorganizes the matrix kernel code with as little change in behavior as possible.
Overview:
Raw computations and results are now separated from subsequent conversions, format choices and conveniences.
Each subclass has a new (or modified) private _right_kernel_matrix()
method, and the top-level code has several new private helper functions that have names starting with _right_kernel_matrix
. These take no input options, and return a string identifying the nature of their results, and a matrix whose rows are a basis for the right kernel. These methods are meant to impose as little overhead as possible on top of the necessary computations.
The new right_kernel_matrix
method manages which algorithms are used and if the basis is converted, such as being echelonized. This introduces the "pivot" format which is a natural way to express basis vectors for a kernel obtained from the echelon form of a matrix. Several algorithms currently in use return results in this format, or something very close. This is the original motivation for this work.
Kernels, right or left, then build vector spaces with the rows of the right kernel matrix.
Improvements:
- Caching of kernels and immutability of the matrix happens in exactly two places, once for left and once for right, ensuring consistency.
- Trivial cases (zero dimension, or full dimension) are handled in one place, again ensuring consistency.
- Adding new algorithms, or specialized behavior for new subclasses, should be easier.
- The logic of how various cases are handled should be more obvious.
- Several bugs have been corrected due to these changes.
- The
right_kernel_matrix()
method allows great flexibility for those who want easy access to a "raw" kernel, either unadorned, or massaged into one of several formats.
- Warnings via the
verbose()
system have been added to make it easy to verify the flow of the computations, and these are doctested.
Changes in behavior:
- For a matrix whose kernel is an entire vector space (ie the ambient vector space), the kernels are returned as such. Previously, they were often built as submodules that were just as big as the whole space. So this is the reason for many of the docstring changes.
_right_kernel_matrix
for integer matrices was used just once outside of the matrix code. It now behaves differently, but can be replaced by the publicright_kernel_matrix()
which behaves almost identically. The exception is that a conversion to an LLL basis is accomplished with a different keyword.
- Documentation infers that keywords can be passed to the echelon form code. This was not working properly since extra keywords, or keywords with the same name (eg
algorithm
), followed logic that was not as described in the documentation. This should be easy to add properly on a subsequent ticket as this new code was written with this in mind. See comments in the source.
- Actual code for the computations is largely unmodified from before. The very few changes needed outside of the
sage/matrix
directory is a reflection of this. These changes are all contained in the "external" patch.
Apply:
Attachments (7)
Change History (23)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_info
A failing doc-test needs attention before this can proceed. More details posted on sage-devel at
http://groups.google.com/group/sage-devel/browse_thread/thread/64b227bc9067b012
sage -t "devel/sage/sage/modular/hecke/module.py" ********************************************************************** File "/sage/dev/devel/sage/sage/modular/hecke/module.py", line 1560: sage: [A.system_of_eigenvalues(3) for A in S.decomposition()] Expected: [[1, 1, 0], [1, -1, -alpha - 1]] Got: [[1, 1, 0], [1, -1, -1/2*alpha - 1/2]] **********************************************************************
comment:2 Changed 10 years ago by
- Cc jason added
comment:3 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
#10714 now has a positive review (thanks, Jason) and the failing doctest has been updated based on advice in the sage-devel thread referenced above. So this is ready to go now, built on 4.6.2.alpha3, and I'll try to keep it updated.
comment:4 Changed 10 years ago by
- Description modified (diff)
Rebased the larger patch for 4.6.2.alpha4, the external patch didn't need it. I had the immutability of the input versus the immutability of the output a bit confused in a couple places, but that is fixed now as well. Use both v2 patches, "external" is second.
comment:5 Changed 10 years ago by
- Cc spancratz added
- Description modified (diff)
Some editing in response to suggetions (via email) by Sebastian Pancratz creates the "v3" patch for the main changes to the sage/matrix
code. Passes long tests.
- Remove unreachable code containing exception for unhandled right kernel basis format
- Clarified documentation about full-rank kernels being buildable for any ring with a one.
- Docstring text, code comments wrapped at column 79
- Docstring text pared down wherever possible
- Left kernel documentation is reduced, relying on the right kernel documentation - but still tests
kernel
andleft_kernel
as aliases, an echelon basis versus a user basis, corner (trivial) cases and caching (which differs substantially for left versus right).
comment:6 Changed 10 years ago by
Latest patches apply, build and test (sage/matrix) fine on 4.7.alpha1.
comment:7 Changed 10 years ago by
- Status changed from needs_review to needs_work
I am willing to work through this, and at first glance the changes look good.
There is one major issue: A kernel IS a subspace. Always. Even if it can be canonically identified with the whole space.
I wouldn't let this pass for a minor release like 4.7.1. Rather, since the behavior changes, we should wait for 4.8 or 5.0, until we merge this.
comment:8 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
Martin has suggested that even if a kernel is equal to the ambient space, it should be built and reported as a subspace of the ambient space. I have made that change (in the right_kernel() routine) by removing the logic that recognized when the right kernel matrix is an identity matrix.
This had the pleasant side-effect that fewer changes are needed elsewhere. So now there are exactly two changes outside the matrix code - a replacement of the private _right_kernel_matrix()
by the public right_kernel_matrix()
in the quaternion algebra code, and a documentation change.
So there is no longer a separate patch containing changes external to the sage/matrix code. Everything is now in the v4 patch. This passes long tests on 4.7.rc0.
Apply: trac_10746-matrix-kernel-refactor-v4.patch
comment:9 Changed 10 years ago by
- Cc stumpc5 added
comment:10 follow-up: ↓ 11 Changed 10 years ago by
- Reviewers set to Christian Stump
The patch looks very well organized and extensively documented.
As the latest version does not contain many changes outside of the matrix code, I think it is okay to put this patch into 4.7, and not to wait for 4.8 or even version 5.
I leave it as needs review, as maybe someone working more with linear algebra / matrices should have a look as well.
One doctest failed in 4.6.2, but I guess this doesn't happen anymore in 4.7.rc0, see the attached patch.
Christian
Changed 10 years ago by
comment:11 in reply to: ↑ 10 Changed 10 years ago by
Replying to stumpc5:
One doctest failed in 4.6.2, but I guess this doesn't happen anymore in 4.7.rc0, see the attached patch.
Thanks, Christian. Indeed, the pivots have switched to tuples instead of lists at #10752, so that failure would be expected on 4.6.2. So the trac_10746-review-cs.patch patch should not be applied.
Thanks again.
comment:12 follow-up: ↓ 13 Changed 10 years ago by
- Status changed from needs_review to positive_review
The patch definitely deserve a positive review, even at a second glance -- the organization of the matrix kernel code is much cleaner now, and the documentation and the examples are very helpful!
Best, Christian
comment:13 in reply to: ↑ 12 Changed 10 years ago by
comment:14 Changed 10 years ago by
- Milestone changed from sage-4.7 to sage-4.7.1
I have built this patch against 4.7.rc3, and tested it against a subset of the Sage library with no problems, so it should be ready to go.
comment:15 Changed 10 years ago by
- Priority changed from major to critical
comment:16 Changed 10 years ago by
- Merged in set to sage-4.7.1.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
Changes within sage/matrix