Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Sorting order of eigvals #47

Closed
baggepinnen opened this issue Apr 11, 2019 · 9 comments · Fixed by #56
Closed

Sorting order of eigvals #47

baggepinnen opened this issue Apr 11, 2019 · 9 comments · Fixed by #56

Comments

@baggepinnen
Copy link

In julia v1.2, the order of eigenvalues are sorted differently
From NEWS.md

Eigenvalues λ of general matrices are now sorted lexicographically by (Re λ, Im λ) (#21598).

It would be great if GenericLinearAlgebra followed the same convention.

@ericphanson
Copy link
Contributor

I think this is because in

LinearAlgebra.eigvals!(A::StridedMatrix; kwargs...) = _eigvals!(A; kwargs...)
LinearAlgebra.eigvals!(H::HessenbergMatrix; kwargs...) = _eigvals!(H, kwargs...)
LinearAlgebra.eigvals!(H::HessenbergFactorization; kwargs...) = _eigvals!(H, kwargs...)

default values aren't given to the keyword arguments, whereas in Base, e.g.

https://github.com/JuliaLang/julia/blob/c6da87ff4bc7a855e217856757ad3413cf6d1f79/stdlib/LinearAlgebra/src/eigen.jl#L198

they are. So I guess the fix would be to just use the same default values. One catch though is that the default sorting keyword argument in Base is Base. eigsortby which was introduced in 1.2 (JuliaLang/julia#21598), so I guess that function would need to be copied in to GenericLinearAlgebra to get the functionality on 1.1 too.

@ericphanson
Copy link
Contributor

Hmm, well it's not just the default keyword arguments, the sorting would need to be implemented too, because in GenericLinearAlgebra the keyword arguments get passed to

function _eigvals!(S::Schur{T}; tol = eps(real(T))) where T

which only currently accepts tol. But it should be easy enough to copy the Base implementation, at least for sorting.

@baggepinnen
Copy link
Author

Base has a function for sorting eigenvalues, this could be used straight up I believe

@ericphanson
Copy link
Contributor

Base has a function for sorting eigenvalues, this could be used straight up I believe

This one?
https://github.com/JuliaLang/julia/blob/c6da87ff4bc7a855e217856757ad3413cf6d1f79/stdlib/LinearAlgebra/src/eigen.jl#L42

Yes, but that was only added in 1.2 (in this PR: JuliaLang/julia#21598), so I think it's probably better to copy it into GenericLinearAlgebra so GenericLinearAlgebra can be used on 1.1 and 1.0

@ericphanson
Copy link
Contributor

Oh, I guess it can be used as

@static if VERSION > v"1.2.0-DEV.0" # Sort one more time to handle GenericLinearAlgebra not being updated
        sort!(roots, by=LinearAlgebra.eigsortby)
    end

like in what you linked. I think there's still one more problem though: even Julia 1.0 and 1.1 sort eigenvalues of Hermitian matrices automatically, but GenericLinearAlgebra doesn't sort those eigenvalues either. So gating the sorting behind a 1.2 check would fix the complex-eigenvalue case but not the real eigenvalue case.

@baggepinnen
Copy link
Author

Perhaps, but the sorting was only convention in Julia 1.2 and onwards, so the most compatible strategy would be to conditionally sort the eigenvalues based on the Julia version, like on the link I pasted above. A bit of a hassle though, I admit

@ericphanson
Copy link
Contributor

I think we wrote at the same time, haha. Yeah, I guess maximum agreement with Base would be to only sort in the non-Hermitian/non-symmetric case if the version is at least 1.2, but add a separate sorting for the real eigenvalues of Hermitian/symmetric matrices for 1.0 and 1.1 (which Julia would do on those versions because that's what the underlying LAPACK would do in that case).

But since the in 1.0 and 1.1, in the non-Hermitian case the sorting is allowed to be anything, it seems fine to just sort in all cases the same way, and resolve both problems at once (the Hermitian and non-Hermitian case).

@ericphanson
Copy link
Contributor

I made a PR to fix this, and ended up going with what you suggested @baggepinnen, using the VERSION check.

It turns out GenericLinearAlgebra already sorts the eigenvalues in the self-adjoint case; what I was seeing was that if a matrix is not wrapped in Hermitian but satisfies ishermitian(A)==true, then it wasn't getting dispatched to the Hermitian-specialized methods the way LinearAlgebra does, and that caused a difference in the sorting behavior on 1.0 and 1.1. So I fixed that by adding the same kind of redirect.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants