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:

Status badges

Description (last modified by rbeezer)

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. trac_10746-matrix-kernel-refactor-v4.patch

Attachments (7)

trac_10746-matrix-kernel-refactor.patch (115.7 KB) - added by rbeezer 10 years ago.
Changes within sage/matrix
trac_10746-matrix-kernel-refactor-external.patch (2.1 KB) - added by rbeezer 10 years ago.
Changes outside sage/matrix
trac_10746-matrix-kernel-refactor-external-v2.patch (3.0 KB) - added by rbeezer 10 years ago.
Replaces previous "external" patch, still apply this second
trac_10746-matrix-kernel-refactor-v2.patch (115.1 KB) - added by rbeezer 10 years ago.
Rebased for 4.6.2.alpha4, apply first
trac_10746-matrix-kernel-refactor-v3.patch (113.9 KB) - added by rbeezer 10 years ago.
Apply first, then follow with external patch
trac_10746-matrix-kernel-refactor-v4.patch (115.4 KB) - added by rbeezer 10 years ago.
Apply only this
trac_10746-review-cs.patch (789 bytes) - added by stumpc5 10 years ago.

Download all attachments as: .zip

Change History (23)

Changed 10 years ago by rbeezer

Changes within sage/matrix

Changed 10 years ago by rbeezer

Changes outside sage/matrix

comment:1 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • 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 jason

  • Cc jason added

Changed 10 years ago by rbeezer

Replaces previous "external" patch, still apply this second

comment:3 Changed 10 years ago by rbeezer

  • 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.

Changed 10 years ago by rbeezer

Rebased for 4.6.2.alpha4, apply first

comment:4 Changed 10 years ago by rbeezer

  • 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.

Changed 10 years ago by rbeezer

Apply first, then follow with external patch

comment:5 Changed 10 years ago by rbeezer

  • 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 and left_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 rbeezer

Latest patches apply, build and test (sage/matrix) fine on 4.7.alpha1.

comment:7 Changed 10 years ago by mraum

  • 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.

Changed 10 years ago by rbeezer

Apply only this

comment:8 Changed 10 years ago by rbeezer

  • 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 rbeezer

  • Cc stumpc5 added

comment:10 follow-up: Changed 10 years ago by stumpc5

  • 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 stumpc5

comment:11 in reply to: ↑ 10 Changed 10 years ago by rbeezer

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: Changed 10 years ago by stumpc5

  • 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 rbeezer

Replying to stumpc5:

Thanks, Christian. Good luck with the upcoming new arrival!

Rob

comment:14 Changed 10 years ago by rbeezer

  • 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 jdemeyer

  • Priority changed from major to critical

comment:16 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.1.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.