JuliaLinearAlgebra / ArnoldiMethod.jl

The Arnoldi Method with Krylov-Schur restart, natively in Julia.
https://julialinearalgebra.github.io/ArnoldiMethod.jl/dev
MIT License
102 stars 18 forks source link

Matrix-induced (semi-)inner product when B ≥ 0. #50

Open haampie opened 6 years ago

haampie commented 6 years ago

In the generalized eigenvalue problem Ax = λBx where B' = B and B ≥ 0 is makes sense to obtain a Schur decomp with the <x, y> = dot(x, B * y) (semi-)inner product.

Also, some care has to be taken to remove "infinite" eigenvalues: after the shift and invert transformation (A - σB)⁻¹Bx = xθ where θ = 1/(λ - σ) there are x s.t. Bx = 0; transforming back λ = σ + 1/θ would lead to λ = ∞.

Looks like ARPACK uses some daunting looking "purification" process to remove these eigenvalues, but there is also this reference [1] which seems easier.

[1] Meerbergen, Karl, and Alastair Spence. "Implicitly restarted Arnoldi with purification for the shift-invert transformation." Mathematics of Computation of the American Mathematical Society 66.218 (1997): 667-689.

haampie commented 6 years ago

Seems like [1] is a lot of words that basically come down to: apply at the end a 0 shift in implicit restart s.t. the new v₁ column is implicitly multiplied by (A - σB)⁻¹B, which filters the components in the null space. Easy enough?

haampie commented 6 years ago

Hm, actually if A is non-symmetric I don't think the B-inner product makes much sense?