GitHub

Truncations

Truncation strategies allow you to control which eigenvalues or singular values to keep when computing partial or truncated decompositions. These strategies are used in the functions eigh_trunc, eig_trunc, and svd_trunc to reduce the size of the decomposition while retaining the most important information.

Using Truncations in Decompositions

Truncation strategies can be used with truncated decomposition functions in two ways, as illustrated below. For concreteness, we use the following matrix as an example:

using MatrixAlgebraKit
using MatrixAlgebraKit: diagview

A = [2 1 0; 1 3 1; 0 1 4];
D, V = eigh_full(A);
diagview(D) ≈ [3 - √3, 3, 3 + √3]

1. Using the trunc keyword with a NamedTuple

The simplest approach is to pass a NamedTuple with the truncation parameters. For example, keeping only the largest 2 eigenvalues:

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (maxrank = 2,));
size(Dtrunc, 1) <= 2

Note however that there are no guarantees on the order of the output values:

diagview(Dtrunc) ≈ diagview(D)[[3, 2]]

You can also use tolerance-based truncation or combine multiple criteria:

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (atol = 2.9,));
all(>(2.9), diagview(Dtrunc))

Use maxrank together with a tolerance to keep at most maxrank values above the tolerance (intersection):

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (maxrank = 2, atol = 2.9));
size(Dtrunc, 1) <= 2 && all(>(2.9), diagview(Dtrunc))

Use minrank together with a tolerance to guarantee at least minrank values are kept (union):

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (atol = 3.5, minrank = 2));
size(Dtrunc, 1) >= 2

In general, the keyword arguments that are supported can be found in the TruncationStrategy docstring:

MatrixAlgebraKit.TruncationStrategy — Method
TruncationStrategy(; kwargs...)

Select a truncation strategy based on the provided keyword arguments.

Keyword arguments

The following keyword arguments are all optional, and their default value (nothing) will be ignored. It is also allowed to combine multiple of these, in which case the kept values will consist of the intersection of the different truncated strategies (except minrank, which uses union semantics to guarantee a lower bound on the number of kept values).

  • atol::Real : Absolute tolerance for the truncation
  • rtol::Real : Relative tolerance for the truncation
  • maxrank::Integer : Maximal rank for the truncation
  • minrank::Integer : Minimal rank for the truncation
  • maxerror::Real : Maximal truncation error.
  • filter : Custom filter to select truncated values.
source

2. Using explicit TruncationStrategy objects

For more control, you can construct TruncationStrategy objects directly. This is also what the previous syntax will end up calling.

Dtrunc, Vtrunc = eigh_trunc(A; trunc = truncrank(2))
size(Dtrunc, 1) <= 2

Strategies can be combined with & (intersection: keep values satisfying all conditions):

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = truncrank(2) & trunctol(; atol = 2.9))
size(Dtrunc, 1) <= 2 && all(>(2.9), diagview(Dtrunc))

Strategies can also be combined with | (union: keep values satisfying any condition). This is useful to set a lower bound on the number of kept values with minrank:

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = trunctol(; atol = 3.5) | truncrank(2))
size(Dtrunc, 1) >= 2

Truncation Strategies

MatrixAlgebraKit provides several built-in truncation strategies:

MatrixAlgebraKit.truncrank — Function
truncrank(howmany::Integer; by=abs, rev::Bool=true)

Truncation strategy to keep the first howmany values when sorted according to by or the last howmany if rev is true.

source
MatrixAlgebraKit.trunctol — Function
trunctol(; atol::Real=0, rtol::Real=0, p::Real=2, by=abs, keep_below::Bool=false)

Truncation strategy to keep the values that satisfy by(val) > max(atol, rtol * norm(values, p)). If keep_below = true, discard these values instead.

source
MatrixAlgebraKit.truncerror — Function
truncerror(; atol::Real=0, rtol::Real=0, p::Real=2)

Truncation strategy for truncating values such that the error in the factorization is smaller than max(atol, rtol * norm), where the error is determined using the p-norm.

source

Strategies can be composed using the & operator (TruncationIntersection) to keep only values satisfying all conditions, or the | operator (TruncationUnion) to keep values satisfying any condition.

MatrixAlgebraKit.TruncationIntersection — Type
TruncationIntersection(trunc::TruncationStrategy, truncs::TruncationStrategy...)

Truncation strategy that composes multiple truncation strategies, keeping values that are common between them.

source
MatrixAlgebraKit.TruncationUnion — Type
TruncationUnion(trunc::TruncationStrategy, truncs::TruncationStrategy...)

Truncation strategy that composes multiple truncation strategies, keeping values that are present in any of them.

source
# Keep at most 10 values, all above tolerance (intersection)
combined_trunc = truncrank(10) & trunctol(; atol = 1e-6);

# Keep values above tolerance, but always at least 3 (union)
combined_trunc = trunctol(; atol = 1e-6) | truncrank(3);

Truncation Error

When using truncated decompositions such as svd_trunc, eig_trunc, or eigh_trunc, an additional truncation error value is returned. This error is defined as the 2-norm of the discarded singular values or eigenvalues, providing a measure of the approximation quality. For svd_trunc and eigh_trunc, this corresponds to the 2-norm difference between the original and the truncated matrix. For the case of eig_trunc, this interpretation does not hold because the norm of the non-unitary matrix of eigenvectors and its inverse also influence the approximation quality.

For example:

using LinearAlgebra: norm
U, S, Vᴴ, ϵ = svd_trunc(A; trunc=truncrank(2))
norm(A - U * S * Vᴴ) ≈ ϵ # ϵ is the 2-norm of the discarded singular values

Truncation with SVD vs Eigenvalue Decompositions

When using truncations with different decomposition types, keep in mind:

  • svd_trunc: Singular values are always real and non-negative, sorted in descending order. Truncation by value typically keeps the largest singular values. The truncation error gives the 2-norm difference between the original and the truncated matrix.

  • eigh_trunc: Eigenvalues are real but can be negative for symmetric matrices. By default, eigenvalues are treated by absolute value, e.g. truncrank(k) keeps the k eigenvalues with largest magnitude (positive or negative). The truncation error gives the 2-norm difference between the original and the truncated matrix.

  • eig_trunc: For general (non-symmetric) matrices, eigenvalues can be complex. By default, eigenvalues are treated by absolute value. The truncation error gives an indication of the magnitude of discarded values, but is not directly related to the 2-norm difference between the original and the truncated matrix.