#10746: Refactor matrix kernel routines
------------------------------+---------------------------------------------
Reporter: rbeezer | Owner: jason, was
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: linear algebra | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Rob Beezer
Merged: | Dependencies:
------------------------------+---------------------------------------------
Changes (by rbeezer):
* status: needs_work => needs_review
Old description:
> 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 public `right_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.
>
> Depends #10714
>
> Apply trac_10746-matrix-kernel-refactor-v3.patch, trac_10746-matrix-
> kernel-refactor-external-v2.patch
New description:
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 public `right_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:'''
1. [attachment:trac_10746-matrix-kernel-refactor-v4.patch]
--
Comment:
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10746#comment:8>
Sage <http://www.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.
