linear algebra functions

[Jason Grout]

I've been working on writing eigenvalue/eigenvector functions, as
mentioned here:
http://groups.google.com/group/sage-devel/browse_thread/thread/c8d2001f2b19a9bc/2585039efd2fbd2f?lnk=gst&q=kernel#2585039efd2fbd2f

Here is the interface as it now stands. Does anyone have any comments
or questions?

* eigenspaces_left, eigenspaces_right: Like the current eigenspaces
function, but returns the algebraic multiplicity of the eigenvalue as
well in tuples like: (eigenvalue, eigenspace, algebraic multiplicity).
This way, existing code that depends on the first two elements of a
returned tuple being what they are still works. In the future, we might
consider using a dictionary like {"eigenvalue": eigenvaxill works. It
prints a deprecation warning and then calls eigenspaces_left.

Also, the even_if_inexact argument is deprecated. Instead, a warning
message is printed if the function is called with an inexact base ring.

Note that the eigenspace functions still return the eigenvalues up to
Galois conjugation, and the algebraic multiplicity applies to each
galois conjugate of the returned eigenvalue (at least, I think that's
how the math should work, right?)

* eigenvalues: This function returns all the eigenvalues as elements of
QQbar: i.e., it returns all the galois conjugates of eigenvalues
returned in eigenspaces_left. For an nxn matrix, it returns n
eigenvalues, so the algebraic multiplicity is not explicitly returned,
but is implicit in the list.

* eigenvectors_left, eigenvectors_right: These functions return tuples
of the form: (eigenvalue, list of eigenvectors, algebraic multiplicity).
The eigenvalues are elements of QQbar and are all distinct
eigenvalues. The list of eigenvectors is found by taking the basis of
the space returned in eigenspaces_* and then mapping it to QQbar^n by
the map that takes the eigenvalue to a particular galois conjugate.

* eigenmatrix_left, eigenmatrix_right: This mimics the eig command in
Matlab: it returns a matrix D and a matrix P, where D is a diagonal
matrix of eigenvalues and P is a matrix of rows or columns corresponding
eigenvectors or zero vectors so that AP=PD or PA=DP (depending on left
or right).

I'm also trying to get the kernel and image and other functions that
depend on left/right notions to signify they side they are computing.
Right now I changed them to *_left and *_right (instead of left_* and
right_*) and deprecating the left_* and right_* functions. I realize
that the *_left/right functions don't read as naturally as left/right_*
functions, but they make a lot more sense in tab completion; if someone
is looking to compute the kernel of a matrix, then it's harder to find
the function if it is called left/right_kernel than if it is called
kernel_left/right. For tab completion, I think it's better in general
to do an index-style noun_modifier than modifier_noun (as would be more
naturally spoken).

Also, to address another point: there would be a lot functions with the
above changes. I'm following the philosophy expressed, I believe, by
Nick: that each function should clearly indicate what it is returning
and that arguments should not change the mathematical content of what is
being returned. I see left eigenvectors and right eigenvectors as
fundamentally different things, i.e., I wouldn't ever want to confuse
the two (well, I guess unless the matrix was symmetric :). That's why I
have two different functions instead of one eigenvectors(left=True) or
eigenvectors(right=True).

I'm trying hard to get this done for 3.0.6 in time for an AIM workshop
on undergraduate linear algebra research that is introducing the
participants to Sage. Otherwise, I'm afraid that Sage won't be very
suitable for the workshop, not having an eigenvalues function, for example.

Thanks,

Jason

[David Joyner]

I think it's great that you are doing this. Does a patch exist yet?
I'd like to try it out.

[Jason Grout]

David Joyner wrote:
> I think it's great that you are doing this. Does a patch exist yet?
> I'd like to try it out.

Yes, on my computer. The documentation isn't there yet, though. I'll
try to put up something today.

Thanks,

Jason

[Jason Grout]

David Joyner wrote:
> I think it's great that you are doing this. Does a patch exist yet?
> I'd like to try it out.

I put up a preliminary patch at
http://trac.sagemath.org/sage_trac/ticket/2816

The patch there depends on the patch at:

http://trac.sagemath.org/sage_trac/ticket/3654

I'll work on the documentation later. I'm very interested in feedback
about the function names, though.

Thanks,

Jason

[David Joyner]

They installed fine and I'm testing it out now. Just to confirm:
in matrix2 you have
eigenspaces_left, eigenspaces_right,
eigenvalues_left, eigenvalues_right,
kernel_left, kernel_right,
image_left (= row_space), image_right (=column_space),
but in functional and matrix_rational_dense, you only have kernel_left?

[Jason Grout]

David Joyner wrote:
> They installed fine and I'm testing it out now. Just to confirm:
> in matrix2 you have
> eigenspaces_left, eigenspaces_right,
> eigenvalues_left, eigenvalues_right,

Actually, there should be only eigenvalues().

There should also be eigenvectors_right/left and eigenmatrix_right/left.

> kernel_left, kernel_right,
> image_left (= row_space), image_right (=column_space),
> but in functional and matrix_rational_dense, you only have kernel_left?

The modifications to functional.py, matrix_rational_dense, and
matrix_integer_dense are still being worked on. The main things I was
testing was the modifications in matrix2.pyx. The plan is to carry the
interface into any subclass that overrides any of these functions
(including matrices over RDF and CDF too, as well as symbolic matrices).

So the main changes:
* introduction of eigen* functions
* changing left/right_* functions to *_left/right to make tab completion
and finding the functions much easier.
* getting rid of functions which implicitly assume left/right and making
those functions explicitly say what they are returning, since, for
example, a vast majority of linear algebra people would assume kernel()
is the right kernel, while apparently a sizable contingent of number
theory/sage people assume kernel() means left kernel.

Again, comments/suggestions/complaints?

Thanks,

Jason

[Mike Hansen]

> * introduction of eigen* functions

+1 definitely.

> * changing left/right_* functions to *_left/right to make tab completion
> and finding the functions much easier.

The *_left and *_right are easier to find under tab completion, but
they are much uglier when reading code. I don't understand why not
just have both. In any case, this is mostly bikeshedding when
compared to the other changes.

> * getting rid of functions which implicitly assume left/right and making
> those functions explicitly say what they are returning, since, for
> example, a vast majority of linear algebra people would assume kernel()
> is the right kernel, while apparently a sizable contingent of number
> theory/sage people assume kernel() means left kernel.

+1 to being explicit

--Mike

[Jason Grout]

Mike Hansen wrote:
>> * introduction of eigen* functions
>
> +1 definitely.
>
>> * changing left/right_* functions to *_left/right to make tab completion
>> and finding the functions much easier.
>
> The *_left and *_right are easier to find under tab completion, but
> they are much uglier when reading code. I don't understand why not
> just have both. In any case, this is mostly bikeshedding when
> compared to the other changes.

I think you're right about the advantages and disadvantages. The reason
to have only one set is:

1. The python "way" of having only one way to do things, instead of
multiple equivalent ways. [1]

2. prevent the littering of the namespace with identical functions that
are just named differently.

3. When this was brought up on sage-devel before, people were even
against the *_left/right names since there were then two functions for
computing kernel, for example. Having 4 functions to compute the kernel
seems a bit much.

Personally, I think the ease of tab completion and finding the functions
is more important than the adjective_noun form of function names. But
in absence of other opinions, I'll make the patch just have left/right_*
synonyms to the *_left/right functions, with no deprecation notice for
the left/right_* functions. William also weighed in on IRC against the
*_left/right naming convention.

Thanks,

Jason

[1] "There should be one-- and preferably only one --obvious way to do
it.", see http://www.python.org/dev/peps/pep-0020/

[Pablo De Napoli]

> > * getting rid of functions which implicitly assume left/right and making
> > those functions explicitly say what they are returning, since, for
> > example, a vast majority of linear algebra people would assume kernel()
> > is the right kernel, while apparently a sizable contingent of number
> > theory/sage people assume kernel() means left kernel.
>
> +1 to being explicit
>

+1: I remember that slogan in the Zen of Python "explicit is better than
implicit"

Pablo