(Inverse) power method

Solves the eigenproblem $Ax = λx$ approximately where $A$ is a general linear map. By default converges towards the dominant eigenpair $(λ, x)$ such that $|λ|$ is largest. Shift-and-invert can be applied to target a specific eigenvalue near shift in the complex plane.

Usage

IterativeSolvers.powm — Function

powm(B; kwargs...) -> λ, x, [history]

See powm!. Calls powm!(B, x0; kwargs...) with x0 initialized as a random, complex unit vector.

source

IterativeSolvers.powm! — Function

powm!(B, x; shift = zero(eltype(B)), inverse::Bool = false, kwargs...) -> λ, x, [history]

By default finds the approximate eigenpair (λ, x) of B where |λ| is largest.

Arguments

B: linear map, see the note below.
x: normalized initial guess. Don't forget to use complex arithmetic when necessary.

Keywords

tol::Real = eps(real(eltype(B))) * size(B, 2) ^ 3: stopping tolerance for the residual norm;
maxiter::Integer = size(B,2): maximum number of iterations;
log::Bool: keep track of the residual norm in each iteration;
verbose::Bool: print convergence information during the iterations.

Shift-and-invert

When applying shift-and-invert to $Ax = λx$ with invert = true and shift = ..., note that the role of B * b becomes computing inv(A - shift I) * b. So rather than passing the linear map $A$ itself, pass a linear map B that has the action of shift-and-invert. The eigenvalue is transformed back to an eigenvalue of the actual matrix $A$.

Return values

if log is false

λ::Number approximate eigenvalue computed as the Rayleigh quotient;
x::Vector approximate eigenvector.

if log is true

λ::Number: approximate eigenvalue computed as the Rayleigh quotient;
x::Vector: approximate eigenvector;
history: convergence history.

ConvergenceHistory keys

:tol => ::Real: stopping tolerance;
:resnom => ::Vector: residual norm at each iteration.

Examples

using LinearMaps
σ = 1.0 + 1.3im
A = rand(ComplexF64, 50, 50)
F = lu(A - σ * I)
Fmap = LinearMap{ComplexF64}((y, x) -> ldiv!(y, F, x), 50, ismutating = true)
λ, x = powm(Fmap, inverse = true, shift = σ, tol = 1e-4, maxiter = 200)

source

IterativeSolvers.invpowm — Function

invpowm(B; shift = σ, kwargs...) -> λ, x, [history]

Find the approximate eigenpair (λ, x) of $A$ near shift, where B is a linear map that has the effect B * v = inv(A - σI) * v.

The method calls powm!(B, x0; inverse = true, shift = σ) with x0 a random, complex unit vector. See powm!

Examples

using LinearMaps
σ = 1.0 + 1.3im
A = rand(ComplexF64, 50, 50)
F = lu(A - σ * I)
Fmap = LinearMap{ComplexF64}((y, x) -> ldiv!(y, F, x), 50, ismutating = true)
λ, x = invpowm(Fmap, shift = σ, tol = 1e-4, maxiter = 200)

source

IterativeSolvers.invpowm! — Function

invpowm!(B, x0; shift = σ, kwargs...) -> λ, x, [history]

Find the approximate eigenpair (λ, x) of $A$ near shift, where B is a linear map that has the effect B * v = inv(A - σI) * v.

The method calls powm!(B, x0; inverse = true, shift = σ). See powm!.

source

Implementation details

Storage requirements are 3 vectors: the approximate eigenvector x, the residual vector r and a temporary. The residual norm lags behind one iteration, as it is computed when $Ax$ is performed. Therefore the final resdiual norm is even smaller.