(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.powmFunction
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.invpowmFunction
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.