nalgebra
nalgebra copied to clipboard
dimforge
Consider sorting eigenvalues and singular values
Currently, there are no guarantees about ordering of eigenvalues and singular vectors returned by nalgebra's decompositions. A common convention throughout mathematical literature is to assume that eigenvalues and singular values are ordered in descending order. Many other mathematical libraries also do this. By following the same convention we would ease porting efforts from other languages into nalgebra code. Recently, a user had this exact issue when porting code from numpy (see #893).
The simplest way to achieve this is to compute a permutation of the eigenvalues/singular values and then apply the permutation also to the columns/rows of the accompanying orthogonal matrices (if computed). While this should have negligible overhead for larger matrices since the decomposition itself is O(n^3), it is not clear to me if perhaps this has some non-trivial cost for small matrices. In this case, we should benchmark and perhaps consider providing means to opt out of this behavior if users are concerned about performance.
While this should have negligible overhead for larger matrices since the decomposition itself is
O(n^3)
It might have a large memory overhead if nalgebra doesn't have an in-place permutation operation.
While this should have negligible overhead for larger matrices since the decomposition itself is
O(n^3)It might have a large memory overhead if nalgebra doesn't have an in-place permutation operation.
I don't think so - computing and storing a permutation would only require O(n) memory, compared to O(n^2) for storingthe eigenvalue/singular value decomposition. Or perhaps I misunderstand you!
What we do need to take care with, however, is allocation. In particular we would need to make sure that computing/storing/applying this permutation does not require heap allocation for small matrices. That is however already similar/analogous to how we e.g. deal with permutations in LU.
@timjb: singular values are now sorted, but IIRC, eigenvalues are not yet sorted (unless I missed a PR for this!).