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

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

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

source
``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
``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
``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.