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))
Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (maxrank = 2, atol = 2.9));
size(Dtrunc, 1) <= 2 && all(>(2.9), diagview(Dtrunc))

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.

  • atol::Real : Absolute tolerance for the truncation
  • rtol::Real : Relative tolerance for the truncation
  • maxrank::Real : Maximal 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
Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = truncrank(2) & trunctol(; atol = 2.9))
size(Dtrunc, 1) <= 2 && all(>(2.9), diagview(Dtrunc))

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

Truncation strategies can be combined using the & operator to create intersection-based truncation. When strategies are combined, only the values that satisfy all conditions are kept.

combined_trunc = truncrank(10) & trunctol(; atol = 1e-6);

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.