#5381: [with patch, needs review] Refactor matrix kernels
----------------------------+-----------------------------------------------
Reporter: rbeezer | Owner: rbeezer
Type: task | Status: new
Priority: minor | Milestone: sage-3.4.2
Component: linear algebra | Keywords: matrix kernel refactor
----------------------------+-----------------------------------------------
Description changed by rbeezer:
Old description:
> From proposal on sage-devel:
>
> Place the guts of kernel computations for each (specialized) class into a
> right_kernel() method, where it would seem to naturally belong. Mostly
> these would replace kernel() methods that are computing left kernels. A
> call to kernel() or left_kernel() should arrive at the top of the
> hierarchy where it would take a transpose and call the (specialized)
> right_kernel(). So there wouldn't be a change in behavior in routines
> currently calling kernel () or left_kernel(), and we would retain Sage's
> preference for the left by having the vanilla kernel() give back a left
> kernel. The changes would be more efficient computationally and also
> make the code more expressive of what is really happening when and where.
New description:
From proposal on sage-devel:
Place the guts of kernel computations for each (specialized) class into a
right_kernel() method, where it would seem to naturally belong. Mostly
these would replace kernel() methods that are computing left kernels. A
call to kernel() or left_kernel() should arrive at the top of the
hierarchy where it would take a transpose and call the (specialized)
right_kernel(). So there wouldn't be a change in behavior in routines
currently calling kernel() or left_kernel(), and we would retain Sage's
preference for the left by having the vanilla kernel() give back a left
kernel. The changes would be more efficient computationally and also make
the code more expressive of what is really happening when and where.
Patch submission:
This patch refactors matrix kernels: left, right, vanilla.
The primary goals were to (1) remove occurences of two consecutive
transposes, and (2) make the code easier to follow by aligning method
names with actual function. There could probably still be some small
improvements in rows versus columns, but these occurences are fairly
localized.
The matrix2 class has each of these three calls, but most of the
computation has been moved from left_kernel() to right_kernel().
Previously, two transposes were taken to get back a right kernel. The
vanilla kernel() is still synonymous with left_kernel().
In subclasses only one kernel is implemented, typically a right kernel
since the algorithms used are for right kernels. New advice in
matrix/dos.py suggests this approach for implementers of new specialized
subclasses.
In the matrix_integer_dense class the old _kernel_gens_using_pari() has
been renamed _kernel_matrix_using_pari() for consistency - it only appears
in the source nearby in this class.
Also, kernel_matrix() has been retained, but could probably be deprecated.
It has been replaced in function by the new _right_kernel_matrix().
Debatable if this should be an internal function or not.
Some doctests were added. Existing tests were mostly transposed on their
inputs, so tests checked out against pre-existing outputs.
sage -testall only returned two errors. Both seemed spurious
(environment variable, unicode complaint) and unrelated to matrix
computations.
Timings:
There was a big speed-up in transposes that was discovered in the course
of this work (changes implemented by Yann Laigle-Chapuy). So much of the
gain obtained by removing a double transpose has shrunk simply by
improving the transpose itself. Transpose speedup code is in 3.4.rc0, but
not 3.3, so the timings below are consistent when one counts up the time
devoted to transposes versus row-reducing.
{{{
n=2000
entries = [[1/(i+j+1) for i in srange(n)] for j in srange(n)]
a = matrix(QQ, entries)
time a.left_kernel()
time a.right_kernel()
}}}
{{{
Left Right
3.3: 50.09s 87.48s
3.4.rc0: 13.22s 14.06s
w/ patch: 13.47s 11.74s
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5381#comment:1>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
