search

JuliaLang / LinearAlgebra.jl

Julia Linear Algebra standard library
Other
17 stars 4 forks source link

Support arbitrary multiple-cluster sorting in `ordschur` #1047

Open mbauman opened 11 months ago

mbauman commented 11 months ago

Some applications require an arbitrary sorting of eigenvalues in a Schur decomposition. Currently, ordschur supports re-ordering with a logical select vector that effectively groups the eigenvalues into two clusters using the LAPACK t[rg]sen. I believe LAPACK also supports moving an individual eigenvalue around with trexc.

However, newer blocked algorithms exist that outperform LAPACK's naive bubble-sort-like algorithm here and can facilitate sorting eigenvalues into multiple clusters more efficiently. See, e.g., Kressner, Daniel (2006). Block algorithms for reordering standard and generalized Schur forms. ACM Transactions on Mathematical Software, 32(4), 521–532. doi:10.1145/1186785.1186787.

I do not believe any open-source project has incorporated this functionality to date. There is an open issue in scipy requesting its addition: https://github.com/scipy/scipy/issues/10872.

aravindh-krishnamoorthy commented 8 months ago

I'll try to implement it here first and if it works out, discuss about integrating it into stdlib. However, I'll be slow as I do this during my free time. Please feel free to overtake me in case you're interested, or better yet, work together with me :)