Compute dimensions of individual generalized eigenspaces

kedlaya commented 8 years ago

Given a square matrix M over a field and an element t of the field, it is easy to compute the dimension of the left eigenspace of M with eigenvalue t, by computing the rank of M-t and subtracting it from the dimension of M. There should be a method for this.

Computing the multiplicity of the generalized eigenspace is slightly more involved, but also not difficult. There should be a method for this too; I already have it written and will get it onto this ticket soon.

It would also be useful to have methods returning eigenspaces and generalized eigenspaces for individual eigenvalues, without computing all of them.

CC: @sagetrac-gregorybard

Component: linear algebra

Keywords: matrices, eigenspaces, dimension, days88, IMA coding sprints

Author: Kiran Kedlaya

Branch/Commit: 675cc94

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/20788

kedlaya commented 8 years ago

Commit: 567e5dd

kedlaya commented 8 years ago

comment:1

Here is a patch with the function I proposed. I could use some more robust doctests; any suggestions?

New commits:

567e5dd Create function to compute eigenspace multiplicities

kedlaya commented 8 years ago

Branch: u/kedlaya/compute_dimensions_of_individual_generalized_eigenspaces

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

48f84b0 Add test for square matrices

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 567e5dd to 48f84b0

kedlaya commented 8 years ago

comment:3

Some experimental evidence suggests that this function leaks memory in a serious way; presumably one of the steps is at fault, but I haven't been able to isolate which one. Might be a job for valgrind here.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

f99e384 Add squaring step

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 48f84b0 to f99e384

kedlaya commented 8 years ago

comment:5

I added a step to square the matrix at each iteration; this reduces the dependence on the nilpotency index from linear to logarithmic. I think this is a win on average: the only issue is doing extra matrix mults when the index is small, but this isn't too costly compared to the echelonization anyway.

fchapoton commented 7 years ago

Changed commit from f99e384 to f3ec6e0

fchapoton commented 7 years ago

comment:6

I added a few doctests.

New commits:

`ecb86cd`	`Merge branch 'u/kedlaya/compute_dimensions_of_individual_generalized_eigenspaces' in 8.0.b2`
`f3ec6e0`	`trac 20788 some details`

fchapoton commented 7 years ago

Changed branch from u/kedlaya/compute_dimensions_of_individual_generalized_eigenspaces to public/20788

kedlaya commented 7 years ago

comment:8

Those doctests look good to me.

kedlaya commented 7 years ago

Author: Kiran Kedlaya

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from f3ec6e0 to a4be0de

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

a4be0de Merge branch 'public/20788' in 8.1.b3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`ba32987`	`Resolve trivial merge conflict`
`fe830a5`	`Merge branch 'public/20788' of git://trac.sagemath.org/sage into t/20788/kedlaya`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from a4be0de to fe830a5

tscrim commented 7 years ago

comment:11

One trivial thing: `s` -> ``s`` since the s is considered in that as code. Once done, you can set a positive review on my behalf.

tscrim commented 7 years ago

Changed keywords from matrices, eigenspaces, dimension to matrices, eigenspaces, dimension, days88, IME coding sprints

tscrim commented 7 years ago

Reviewer: Travis Scrimshaw

tscrim commented 7 years ago

Changed keywords from matrices, eigenspaces, dimension, days88, IME coding sprints to matrices, eigenspaces, dimension, days88, IMA coding sprints

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

675cc94 Corrected backticks typo in docstring

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from fe830a5 to 675cc94

kedlaya commented 7 years ago

comment:14

Replying to @tscrim:

One trivial thing: `s` -> ``s`` since the s is considered in that as code. Once done, you can set a positive review on my behalf.

Done and done.

vbraun commented 7 years ago

Changed branch from public/20788 to 675cc94

sagemath / sage

Compute dimensions of individual generalized eigenspaces #20788