Power method

(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(Complex128, 50, 50)
F = lufact(A - σ * I)
Fmap = LinearMap{Complex128}((y, x) -> A_ldiv_B!(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(Complex128, 50, 50)
F = lufact(A - σ * I)
Fmap = LinearMap{Complex128}((y, x) -> A_ldiv_B!(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.