Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
StructuredMatrices examples

These programs solve problems from numerical PDEs, integral equations, signal and image processing, approximation theory, statistics, control and quantum mechanics with the StructuredMatrices module. Each one replaces a dense or sparse factorization by an algorithm that exploits a structure of the problem – a Kronecker product or sum, Toeplitz, Hankel or circulant, Vandermonde, Cauchy, or diagonal plus low rank – and checks its result against a known solution or a general-purpose solver. The bracketed numbers cite the module's references.

Separable operators on tensor-product grids

Finite differences on a tensor-product grid give Kronecker sums of 1-D matrices: with grid values stored with x as the fast index, the 2-D Laplacian is \( D_y \oplus D_x = D_y \otimes I + I \otimes D_x \). KroneckerSum applies such operators without forming them, and BartelsStewart solves them through the Schur forms or eigendecompositions of the 1-D factors. LeVeque [1] covers the discretizations.

The 2-D Poisson equation

The fast Poisson solver: two \( n \times n \) eigendecompositions instead of a factorization of the \( n^2 \times n^2 \) matrix, with the second-order convergence of the discretization: the fast diagonalization method of Lynch, Rice and Thomas [2].

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The 2-D Poisson equation -(u_xx + u_yy) = f on the unit square, u = 0 on the
// boundary, with second-order finite differences on an n x n interior grid.
// Its matrix is the Kronecker sum D (+) D of the 1-D matrix
// D = tridiag(-1, 2, -1) / h^2, which BartelsStewart solves by fast
// diagonalization: two n x n eigendecompositions instead of a sparse
// factorization of the n^2 x n^2 matrix. The error falls as O(h^2).
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
SparseMatrix<double> secondDifference(int n) {
const double h = 1.0 / (n + 1);
D.reserve(VectorXi::Constant(n, 3)); // at most 3 nonzeros per column
for (int i = 0; i < n; ++i) {
D.insert(i, i) = 2 / (h * h);
if (i > 0) D.insert(i, i - 1) = -1 / (h * h);
if (i + 1 < n) D.insert(i, i + 1) = -1 / (h * h);
}
D.makeCompressed();
return D;
}
int main() {
const double pi = std::acos(-1.0);
for (int n : {16, 32, 64, 128}) {
const double h = 1.0 / (n + 1);
// Grid values in Kronecker order: entry j*n + i belongs to (x_i, y_j).
VectorXd exact(n * n);
for (int j = 0; j < n; ++j)
for (int i = 0; i < n; ++i) exact[j * n + i] = std::sin(pi * (i + 1) * h) * std::sin(2 * pi * (j + 1) * h);
const VectorXd f = 5 * pi * pi * exact;
const SparseMatrix<double> D = secondDifference(n);
const auto L = makeKroneckerSum(D, D); // y on the left (slow index), x on the right
const BartelsStewart<std::decay_t<decltype(L)>> poisson(L);
const VectorXd u = poisson.solve(f);
std::cout << "n = " << n << ": max error " << (u - exact).cwiseAbs().maxCoeff() << "\n";
}
}
Direct solver for Kronecker-sum systems .
Definition KroneckerSum.h:578
KroneckerSum< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > makeKroneckerSum(const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b)
Definition KroneckerSum.h:496
Matrix< double, Dynamic, 1 > VectorXd
Namespace containing all symbols from the Eigen library.
n = 16: max error 0.00964497
n = 32: max error 0.00256566
n = 64: max error 0.000661721
n = 128: max error 0.000168033

Implicit time stepping of the 3-D heat equation

The decompositions are computed once and reused at every step. A shift such as the identity of \( I + \tau L \) goes into one factor, since \( I \otimes I \otimes I = I \).

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Implicit Euler for the heat equation u_t = u_xx + u_yy + u_zz on the unit
// cube: each step solves (I + tau (D (+) D (+) D)) u_new = u_old, with
// D = tridiag(-1, 2, -1) / h^2. The identity goes into one factor,
// I + tau (D (+) D (+) D) = (I + tau D) (+) tau D (+) tau D, and the solver
// computes three n x n eigendecompositions once for all steps. The initial
// state is a discrete eigenmode, so the computed decay can be checked exactly.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
SparseMatrix<double> secondDifference(int n) {
const double h = 1.0 / (n + 1);
D.reserve(VectorXi::Constant(n, 3)); // at most 3 nonzeros per column
for (int i = 0; i < n; ++i) {
D.insert(i, i) = 2 / (h * h);
if (i > 0) D.insert(i, i - 1) = -1 / (h * h);
if (i + 1 < n) D.insert(i, i + 1) = -1 / (h * h);
}
return D;
}
int main() {
const double pi = std::acos(-1.0);
const int n = 24, steps = 100;
const double h = 1.0 / (n + 1), tau = 1e-3;
const SparseMatrix<double> D = secondDifference(n);
I.setIdentity();
const auto M =
const BartelsStewart<std::decay_t<decltype(M)>> step(M);
// u0 = sin(pi x) sin(pi y) sin(pi z), an eigenvector of D (+) D (+) D.
VectorXd s(n);
for (int i = 0; i < n; ++i) s[i] = std::sin(pi * (i + 1) * h);
const MatrixXd modes = (s * s.transpose()).reshaped() * s.transpose();
const VectorXd u0 = modes.reshaped();
VectorXd u = u0;
for (int k = 0; k < steps; ++k) u = step.solve(u);
const double lambda = 3 * 4 / (h * h) * std::pow(std::sin(pi * h / 2), 2);
const double amplitude = u.dot(u0) / u0.squaredNorm();
std::cout << n * n * n << " unknowns, " << steps << " steps\n";
std::cout << "amplitude: " << amplitude << "\n";
std::cout << "implicit Euler, exact: " << std::pow(1 + tau * lambda, -steps) << "\n";
std::cout << "heat equation, exact: " << std::exp(-3 * pi * pi * tau * steps) << "\n";
}
Scalar & insert(Index row, Index col)
void reserve(const SizesType &reserveSizes)
Matrix< double, Dynamic, Dynamic > MatrixXd
13824 unknowns, 100 steps
amplitude:               0.0542522
implicit Euler, exact:   0.0542522
heat equation, exact:    0.0517733

Convection-diffusion

Nonsymmetric 1-D operators take the Schur-form path of BartelsStewart, the algorithm of Bartels and Stewart [3]; the solution agrees with SparseLU on the assembled matrix.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Steady convection-diffusion -eps (u_xx + u_yy) + b_x u_x + b_y u_y = 1 on the
// unit square, u = 0 on the boundary, with centered differences. The 1-D
// operators eps D + b G (D = tridiag(-1, 2, -1) / h^2, G = tridiag(-1, 0, 1) / 2h)
// are not symmetric, so BartelsStewart takes the Schur path; the result agrees
// with SparseLU on the assembled matrix.
#include <contrib/Eigen/StructuredMatrices>
#include <iostream>
using namespace Eigen;
SparseMatrix<double> convectionDiffusion(int n, double eps, double b) {
const double h = 1.0 / (n + 1);
A.reserve(VectorXi::Constant(n, 3)); // at most 3 nonzeros per column
for (int i = 0; i < n; ++i) {
A.insert(i, i) = 2 * eps / (h * h);
if (i > 0) A.insert(i, i - 1) = -eps / (h * h) - b / (2 * h);
if (i + 1 < n) A.insert(i, i + 1) = -eps / (h * h) + b / (2 * h);
}
A.makeCompressed();
return A;
}
int main() {
const int n = 100;
const double eps = 0.05;
const auto L = makeKroneckerSum(convectionDiffusion(n, eps, 0.5), convectionDiffusion(n, eps, 1.0));
const BartelsStewart<std::decay_t<decltype(L)>> solver(L);
const VectorXd f = VectorXd::Ones(n * n);
const VectorXd u = solver.solve(f);
A = L; // the assembled n^2 x n^2 matrix, for comparison
const VectorXd uLU = SparseLU<SparseMatrix<double>>(A).solve(f);
std::cout << "fast diagonalization: " << (solver.isHermitian() ? "yes" : "no") << "\n";
std::cout << "max u: " << u.maxCoeff() << "\n";
std::cout << "relative residual: " << (A * u - f).norm() / f.norm() << "\n";
std::cout << "|u - u_SparseLU|/|u|: " << (u - uLU).norm() / u.norm() << "\n";
}
fast diagonalization: no
max u:                0.72008
relative residual:    2.12649e-12
|u - u_SparseLU|/|u|: 8.14305e-13

Alternating-direction implicit time stepping

The Peaceman-Rachford ADI method [4] treats one direction at a time. Each half step is a KroneckerOperator with an Identity() factor, which costs nothing: the product is a sparse product with the 1-D matrix and the solve one SparseLU of a tridiagonal matrix.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Peaceman-Rachford ADI for u_t = u_xx + u_yy on the unit square. With x the
// fast grid index, the two directions are I (x) D and D (x) I, and each half
// step is an explicit product in one direction and a tridiagonal solve in the
// other:
// (I + tau/2 I (x) D) u_half = (I - tau/2 D (x) I) u_old,
// (I + tau/2 D (x) I) u_new = (I - tau/2 I (x) D) u_half.
// The Identity() factors cost nothing: the products are sparse products with D
// and the solves one SparseLU of the tridiagonal I + tau/2 D.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
SparseMatrix<double> secondDifference(int n) {
const double h = 1.0 / (n + 1);
D.reserve(VectorXi::Constant(n, 3)); // at most 3 nonzeros per column
for (int i = 0; i < n; ++i) {
D.insert(i, i) = 2 / (h * h);
if (i > 0) D.insert(i, i - 1) = -1 / (h * h);
if (i + 1 < n) D.insert(i, i + 1) = -1 / (h * h);
}
D.makeCompressed();
return D;
}
int main() {
const double pi = std::acos(-1.0);
const int n = 200, steps = 50;
const double h = 1.0 / (n + 1), tau = 1e-3;
const SparseMatrix<double> D = secondDifference(n);
I.setIdentity();
const auto Id = MatrixXd::Identity(n, n);
const auto xImplicit = makeKroneckerOperator(Id, SparseMatrix<double>(I + tau / 2 * D));
const auto yImplicit = makeKroneckerOperator(SparseMatrix<double>(I + tau / 2 * D), Id);
const auto xExplicit = makeKroneckerOperator(Id, SparseMatrix<double>(I - tau / 2 * D));
const auto yExplicit = makeKroneckerOperator(SparseMatrix<double>(I - tau / 2 * D), Id);
// u0 = sin(pi x) sin(2 pi y), an eigenvector of both directions.
VectorXd sx(n), sy(n);
for (int i = 0; i < n; ++i) {
sx[i] = std::sin(pi * (i + 1) * h);
sy[i] = std::sin(2 * pi * (i + 1) * h);
}
const VectorXd u0 = (sx * sy.transpose()).reshaped(); // entry j*n + i is (x_i, y_j)
VectorXd u = u0;
for (int k = 0; k < steps; ++k) {
const VectorXd half = xImplicit.solve(yExplicit * u);
u = yImplicit.solve(xExplicit * half);
}
const auto factor = [&](double lambda) { return (1 - tau / 2 * lambda) / (1 + tau / 2 * lambda); };
const double lx = 4 / (h * h) * std::pow(std::sin(pi * h / 2), 2), ly = 4 / (h * h) * std::pow(std::sin(pi * h), 2);
std::cout << n * n << " unknowns, " << steps << " ADI steps\n";
std::cout << "amplitude: " << u.dot(u0) / u0.squaredNorm() << "\n";
std::cout << "ADI, exact: " << std::pow(factor(lx) * factor(ly), steps) << "\n";
std::cout << "PDE, exact: " << std::exp(-5 * pi * pi * tau * steps) << "\n";
}
KroneckerOperator< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > makeKroneckerOperator(const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b)
Definition KroneckerOperator.h:1505
40000 unknowns, 50 ADI steps
amplitude:       0.0847974
ADI, exact:      0.0847974
PDE, exact:      0.084805

A non-separable potential

When a term breaks the separable structure, the separable part still helps twice: KroneckerSparseView assembles the sparse matrix in one expression, and the fast Poisson solver preconditions conjugate gradients.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// A Schroedinger-type problem (-(u_xx + u_yy) + V(x, y) u = f) whose potential
// V is not separable, so the matrix L + diag(V) is no Kronecker sum. The
// separable part is still exploited twice: L.sparseView() assembles the
// sparse matrix in one expression, and the fast Poisson solver for
// L + mean(V) I preconditions conjugate gradients.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
SparseMatrix<double> secondDifference(int n) {
const double h = 1.0 / (n + 1);
D.reserve(VectorXi::Constant(n, 3)); // at most 3 nonzeros per column
for (int i = 0; i < n; ++i) {
D.insert(i, i) = 2 / (h * h);
if (i > 0) D.insert(i, i - 1) = -1 / (h * h);
if (i + 1 < n) D.insert(i, i + 1) = -1 / (h * h);
}
return D;
}
// Applies (L + c I)^{-1} through BartelsStewart: the preconditioner interface
// the iterative solvers expect.
class SeparablePreconditioner {
public:
void setOperator(const Laplacian& shifted) { m_solver.compute(shifted); }
template <typename MatrixType>
SeparablePreconditioner& analyzePattern(const MatrixType&) {
return *this;
}
template <typename MatrixType>
SeparablePreconditioner& factorize(const MatrixType&) {
return *this;
}
template <typename MatrixType>
SeparablePreconditioner& compute(const MatrixType&) {
return *this;
}
template <typename Rhs>
VectorXd solve(const MatrixBase<Rhs>& b) const {
return m_solver.solve(b);
}
ComputationInfo info() const { return m_solver.info(); }
private:
BartelsStewart<Laplacian> m_solver;
};
int main() {
const int n = 128;
const double h = 1.0 / (n + 1);
const SparseMatrix<double> D = secondDifference(n);
const Laplacian L = makeKroneckerSum(D, D);
// A Gaussian well, centered off the grid's symmetry axes.
VectorXd V(n * n);
for (int j = 0; j < n; ++j)
for (int i = 0; i < n; ++i) {
const double x = (i + 1) * h - 0.4, y = (j + 1) * h - 0.6;
V[j * n + i] = 2000 * std::exp(-(x * x + y * y) / 0.01);
}
SparseMatrix<double> Vd(n * n, n * n);
Vd.setIdentity();
Vd = Vd * V.asDiagonal();
const SparseMatrix<double> H = L.sparseView() + Vd; // assembled without materializing L
const VectorXd f = VectorXd::Ones(n * n);
// The preconditioner gets its operator before compute(), which reads its info().
ConjugateGradient<SparseMatrix<double>, Lower | Upper, SeparablePreconditioner> separable;
I.setIdentity();
separable.preconditioner().setOperator(makeKroneckerSum(SparseMatrix<double>(D + V.mean() * I), D));
separable.compute(H);
const VectorXd u0 = plain.solve(f), u1 = jacobi.solve(f), u2 = separable.solve(f);
std::cout << n * n << " unknowns, CG iterations to relative residual " << plain.tolerance() << ":\n";
std::cout << " no preconditioner: " << plain.iterations() << "\n";
std::cout << " Jacobi: " << jacobi.iterations() << "\n";
std::cout << " separable (fast Poisson): " << separable.iterations() << "\n";
std::cout << "max |u_separable - u_Jacobi| / max |u|: " << (u2 - u1).cwiseAbs().maxCoeff() / u1.cwiseAbs().maxCoeff()
<< "\n";
}
The Kronecker sum of two square matrices as an implicit operator that is never materialized.
Definition KroneckerSum.h:243
ComputationInfo
16384 unknowns, CG iterations to relative residual 2.22045e-16:
  no preconditioner:       531
  Jacobi:                  533
  separable (fast Poisson): 27
max |u_separable - u_Jacobi| / max |u|: 5.76249e-15

Periodic boundaries: the screened Poisson equation on a torus

With periodic boundaries the five-point stencil is a block circulant with circulant blocks, solved by Bccb through the 2-D FFT [5]. It is also the Kronecker sum of two 1-D periodic second-difference circulants, and the two solvers agree.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The screened Poisson equation -(u_xx + u_yy) + kappa^2 u = f on the periodic
// unit square, five-point stencil on an n x n grid. Periodic boundaries make
// the matrix a block circulant with circulant blocks, solved by Bccb in
// O(N log N) through the 2-D FFT. The same matrix is the Kronecker sum
// (C + kappa^2 I) (+) C of the 1-D periodic second-difference circulant C,
// which BartelsStewart solves by fast diagonalization; the two agree.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
int main() {
const double pi = std::acos(-1.0), kappa = 2.0;
const int n = 64;
const double h = 1.0 / n;
// Stencil generator: column k holds the first column of block k.
MatrixXd G = MatrixXd::Zero(n, n);
G(0, 0) = 4 / (h * h) + kappa * kappa;
G(1, 0) = G(n - 1, 0) = G(0, 1) = G(0, n - 1) = -1 / (h * h);
const auto A = makeBccb(G);
// u = cos(2 pi x) sin(4 pi y) is exact up to the O(h^2) stencil error.
VectorXd exact(n * n), f(n * n);
for (int j = 0; j < n; ++j)
for (int i = 0; i < n; ++i) {
exact[j * n + i] = std::cos(2 * pi * i * h) * std::sin(4 * pi * j * h);
f[j * n + i] = (20 * pi * pi + kappa * kappa) * exact[j * n + i];
}
const VectorXd u = A.solve(f);
std::cout << "Bccb: max error " << (u - exact).cwiseAbs().maxCoeff() << "\n";
VectorXd column = VectorXd::Zero(n);
column[0] = 2 / (h * h);
column[1] = column[n - 1] = -1 / (h * h);
C = makeCirculant(column); // dense, for the Kronecker sum
const auto L = makeKroneckerSum(MatrixXd(C + kappa * kappa * MatrixXd::Identity(n, n)), C);
const VectorXd v = L.solve(f);
std::cout << "KroneckerSum: max error " << (v - exact).cwiseAbs().maxCoeff() << "\n";
std::cout << "max |u_Bccb - u_KroneckerSum|: " << (u - v).cwiseAbs().maxCoeff() << "\n";
}
Circulant< typename Derived::Scalar, Derived::SizeAtCompileTime > makeCirculant(const MatrixBase< Derived > &col)
Definition Circulant.h:546
Bccb< typename Derived::Scalar, Derived::RowsAtCompileTime, Derived::ColsAtCompileTime > makeBccb(const MatrixBase< Derived > &generator)
Definition Bccb.h:638
Bccb:               max error 0.00268049
KroneckerSum:       max error 0.00268049
max |u_Bccb - u_KroneckerSum|: 5.61773e-14

Fourier spectral differentiation

On a periodic grid the spectral differentiation matrices are circulants [21], and their spectra are the wavenumbers: Circulant::eigenvalues returns \( ik \), Circulant::rank counts the \( N - 2 \) nonzero ones (the constant and the sawtooth mode are annihilated), and the pseudo-inverse Circulant::solve integrates a periodic function with zero mean. Derivatives and the periodic boundary value problem \( u'' - u = f \) converge geometrically for smooth \( u \).

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Fourier spectral differentiation on the periodic grid x_j = j h, h = 2 pi / N,
// N even. The differentiation matrix is the circulant with first column
// D_0 = 0, D_j = (-1)^j / (2 tan(j h / 2)), j = 1, ..., N-1,
// and the second-derivative matrix the circulant with
// D2_0 = -pi^2 / (3 h^2) - 1/6, D2_j = -(-1)^j / (2 sin^2(j h / 2)).
// Their eigenvalues are the wavenumbers: D has i k for |k| < N/2 and 0 for the
// constant and for the sawtooth mode k = N/2, so it is singular of rank N - 2,
// and Circulant::solve returns the minimum-norm antiderivative, the one with
// zero mean and no sawtooth component. The derivatives, the antiderivative and
// the periodic boundary value problem u'' - u = f all converge geometrically
// for u = exp(sin x).
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace Eigen;
// First column of the N x N spectral differentiation matrix of the given order.
VectorXd spectralColumn(int N, int order) {
const double pi = std::acos(-1.0), h = 2 * pi / N;
VectorXd column(N);
column[0] = order == 1 ? 0 : -pi * pi / (3 * h * h) - 1.0 / 6;
for (int j = 1; j < N; ++j) {
const double sign = j % 2 == 0 ? 1 : -1;
column[j] = order == 1 ? sign / (2 * std::tan(j * h / 2)) : -sign / (2 * std::pow(std::sin(j * h / 2), 2));
}
return column;
}
int main() {
const double pi = std::acos(-1.0);
const double mean = 1.2660658777520084; // mean of exp(sin x) over a period, the Bessel function I_0(1)
std::cout << " N rank error of u' error of u'' antiderivative u'' - u = f\n";
for (int N : {8, 16, 24, 32}) {
const auto D = makeCirculant(spectralColumn(N, 1));
const auto D2 = makeCirculant(spectralColumn(N, 2));
VectorXd shifted = spectralColumn(N, 2);
shifted[0] -= 1;
const auto D2mI = makeCirculant(shifted); // D2 - I
const ArrayXd x = ArrayXd::LinSpaced(N, 0, 2 * pi * (N - 1) / N), s = x.sin(), c = x.cos();
const VectorXd u = s.exp(), du = c * s.exp(), d2u = (c * c - s) * s.exp();
std::cout << std::setw(2) << N << std::setw(5) << D.rank() << " " << std::setw(11)
<< (D * u - du).cwiseAbs().maxCoeff() << " " << std::setw(12) << (D2 * u - d2u).cwiseAbs().maxCoeff()
<< " " << std::setw(14) << (D.solve(du).array() + mean - s.exp()).abs().maxCoeff() << " "
<< (D2mI.solve(VectorXd(d2u - u)) - u).cwiseAbs().maxCoeff() << "\n";
}
const auto D = makeCirculant(spectralColumn(8, 1));
std::cout << "N = 8, eigenvalues / i: " << D.eigenvalues().imag().array().round().cast<int>().transpose() << "\n";
}
const CwiseUnaryOp< internal::scalar_abs_op< Scalar >, const Derived > cwiseAbs() const
constexpr NonConstImagReturnType imag()
 N  rank  error of u'  error of u''  antiderivative  u'' - u = f
 8    6   0.00431791     0.0102933      0.00712765  0.0012465
16   14  1.76189e-07   3.90952e-07     2.25992e-07  8.11658e-09
24   22  9.69891e-13   2.38165e-12     1.13376e-12  3.41061e-13
32   30  2.32037e-14   5.45342e-13     9.54792e-15  3.45501e-13
N = 8, eigenvalues / i:  0  1  2  3  0 -3 -2 -1

Matrix equations and spectra

The Lyapunov equation of a mass-spring chain

\( A X + X A^T = C \) is \( (A \oplus A)\,\mathrm{vec}(X) = \mathrm{vec}(C) \), and the Sylvester equation \( A X + X B = C \) is \( (B^T \oplus A)\,\mathrm{vec}(X) = \mathrm{vec}(C) \). This example computes the controllability Gramian of a damped chain, whose system matrix has complex eigenvalue pairs; Simoncini [6] surveys the methods for such matrix equations.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The controllability Gramian X of a damped mass-spring chain x' = A x + B w,
// forced at the last mass, solves the Lyapunov equation A X + X A^T + B B^T = 0.
// With vec stacking columns, vec(A X + X A^T) = (A (+) A) vec(X), so the
// equation is one Kronecker-sum solve. A is not symmetric and has complex
// eigenvalue pairs (an underdamped chain); X is symmetric positive definite
// when the chain is controllable.
#include <contrib/Eigen/StructuredMatrices>
#include <iostream>
using namespace Eigen;
int main() {
const int masses = 20, n = 2 * masses;
const double damping = 0.1;
// State (positions, velocities): A = [0 I; -K -c I] with K = tridiag(-1, 2, -1).
MatrixXd A = MatrixXd::Zero(n, n);
A.topRightCorner(masses, masses).setIdentity();
for (int i = 0; i < masses; ++i) {
A(masses + i, i) = -2;
if (i > 0) A(masses + i, i - 1) = 1;
if (i + 1 < masses) A(masses + i, i + 1) = 1;
A(masses + i, masses + i) = -damping;
}
VectorXd B = VectorXd::Zero(n);
B[n - 1] = 1;
const MatrixXd Q = B * B.transpose();
const MatrixXd X = makeKroneckerSum(A, A).solve(-Q.reshaped()).reshaped(n, n);
std::cout << "residual |AX + XA^T + BB^T| / |BB^T|: " << (A * X + X * A.transpose() + Q).norm() / Q.norm() << "\n";
std::cout << "asymmetry |X - X^T| / |X|: " << (X - X.transpose()).norm() / X.norm() << "\n";
std::cout << "smallest eigenvalue of X: "
<< SelfAdjointEigenSolver<MatrixXd>((X + X.transpose()) / 2).eigenvalues()[0] << "\n";
}
const RealVectorType & eigenvalues() const
residual |AX + XA^T + BB^T| / |BB^T|: 9.27326e-15
asymmetry |X - X^T| / |X|:            4.3799e-16
smallest eigenvalue of X:             8.4712e-07

The 2-D quantum harmonic oscillator

A separable Hamiltonian \( H_x \oplus H_y \) has the pairwise sums of the 1-D energies as its spectrum, which KroneckerSum::eigenvalues returns without forming the 2-D matrix [7].

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The 2-D quantum harmonic oscillator H = -(d_xx + d_yy) / 2 + (x^2 + y^2) / 2
// separates as H = H_1 (+) H_1 with the 1-D Hamiltonian H_1, so its spectrum
// is the set of pairwise sums of the 1-D energies -- here from a
// finite-difference H_1 on [-8, 8], without ever forming the 2-D matrix. The
// exact energies are n_x + n_y + 1, with degeneracy n_x + n_y + 1.
#include <contrib/Eigen/StructuredMatrices>
#include <algorithm>
#include <iostream>
using namespace Eigen;
int main() {
const int n = 400;
const double a = 8, h = 2 * a / (n + 1);
MatrixXd H1 = MatrixXd::Zero(n, n);
for (int i = 0; i < n; ++i) {
const double x = -a + (i + 1) * h;
H1(i, i) = 1 / (h * h) + x * x / 2;
if (i + 1 < n) H1(i, i + 1) = H1(i + 1, i) = -1 / (2 * h * h);
}
const auto H = makeKroneckerSum(H1, H1);
VectorXd energies = H.eigenvalues().real();
std::sort(energies.data(), energies.data() + energies.size());
std::cout << H.rows() << " x " << H.cols() << " Hamiltonian, lowest energies:\n"
<< energies.head(10).transpose() << "\n";
}
constexpr Scalar * data()
constexpr NonConstRealReturnType real()
Index cols() const
Index rows() const
160000 x 160000 Hamiltonian, lowest energies:
 0.9999  1.9997  1.9997  2.9993  2.9993  2.9995 3.99871 3.99871  3.9991  3.9991

An impurity bound state

A localized perturbation of a diagonal band Hamiltonian is a rank-one update, the Koster-Slater model [8]. DPR1EigenSolver finds the whole spectrum in \( O(N^2) \) from the secular equation [9], including the bound state that splits off below the band.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// A Koster-Slater impurity: a tight-binding ring of N sites with hopping t and
// one site shifted by V < 0. In the Bloch basis the band is diagonal,
// e_k = -2t cos(2 pi k / N), and the impurity is the rank-one update
// V z z^T with z_k = 1/sqrt(N), so H = D + V z z^T is diagonal plus rank one.
// DPR1EigenSolver finds all N eigenvalues in O(N^2) from the secular equation;
// one of them splits off below the band, approaching the infinite-chain bound
// state -sqrt(V^2 + 4 t^2).
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace Eigen;
int main() {
const double pi = std::acos(-1.0), t = 1.0, V = -1.5;
std::cout << " N lowest eigenvalue band bottom\n";
for (int N : {16, 64, 256, 1024}) {
VectorXd d(N);
for (int k = 0; k < N; ++k) d[k] = -2 * t * std::cos(2 * pi * k / N);
const VectorXd z = VectorXd::Constant(N, 1 / std::sqrt(double(N)));
const DPR1EigenSolver<double> es(d, V, z, /*options=*/0);
std::cout << std::setw(6) << N << " " << std::setw(16) << es.eigenvalues()[0] << " " << d.minCoeff() << "\n";
}
std::cout << "infinite chain: " << -std::sqrt(V * V + 4 * t * t) << "\n";
}
Direct O(n^2) eigensolver for real symmetric diagonal-plus-rank-one matrices , via the secular equati...
Definition DPR1EigenSolver.h:78
     N  lowest eigenvalue  band bottom
    16          -2.50003  -2
    64              -2.5  -2
   256              -2.5  -2
  1024              -2.5  -2
infinite chain: -2.5

The merge step of divide and conquer

Cuppen's method [25] tears a symmetric tridiagonal matrix into two halves plus a rank-one coupling; after the halves are diagonalized, what remains is the diagonal-plus-rank-one eigenproblem that DPR1EigenSolver solves from the secular equation, with eigenvectors orthogonal to working accuracy by the construction of Gu and Eisenstat [9]. The example performs one such merge and compares with SelfAdjointEigenSolver.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The merge step of Cuppen's divide-and-conquer eigensolver. A symmetric
// tridiagonal T splits at the coupling b = T(m, m-1) into
// T = diag(T_1, T_2) + b v v^T, v = e_{m-1} + e_m,
// where T_1 and T_2 are the two halves with b subtracted from their diagonal
// entries at the cut. With T_i = Q_i L_i Q_i^T and Q = diag(Q_1, Q_2),
// T = Q (D + b z z^T) Q^T, D = diag(L_1, L_2), z = Q^T v,
// a diagonal-plus-rank-one eigenproblem that DPR1EigenSolver solves in O(n^2)
// from the secular equation, with eigenvectors orthogonal to working accuracy;
// those of T are Q times them. In the real algorithm the halves recurse; here
// SelfAdjointEigenSolver stands in for the recursion.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
int main() {
const int n = 200, m = n / 2;
// T = tridiag(-1, 2 + cos(i), -1).
MatrixXd T = MatrixXd::Zero(n, n);
for (int i = 0; i < n; ++i) T(i, i) = 2 + std::cos(i);
T.diagonal(1).setConstant(-1);
T.diagonal(-1).setConstant(-1);
const double b = T(m, m - 1);
MatrixXd T1 = T.topLeftCorner(m, m), T2 = T.bottomRightCorner(n - m, n - m);
T1(m - 1, m - 1) -= b;
T2(0, 0) -= b;
const SelfAdjointEigenSolver<MatrixXd> half1(T1), half2(T2);
VectorXd d(n), z(n);
d << half1.eigenvalues(), half2.eigenvalues();
z << half1.eigenvectors().row(m - 1).transpose(), half2.eigenvectors().row(0).transpose();
const DPR1EigenSolver<double> merged(d, b, z);
const VectorXd& lambda = merged.eigenvalues();
MatrixXd V(n, n);
V.topRows(m) = half1.eigenvectors() * merged.eigenvectors().topRows(m);
V.bottomRows(n - m) = half2.eigenvectors() * merged.eigenvectors().bottomRows(n - m);
std::cout << "residual |T V - V L| / |T|: " << (T * V - V * lambda.asDiagonal()).norm() / T.norm()
<< "\n";
std::cout << "orthogonality |V^T V - I|: " << (V.transpose() * V - MatrixXd::Identity(n, n)).norm()
<< "\n";
std::cout << "max difference to SelfAdjointEigenSolver: "
<< (lambda - SelfAdjointEigenSolver<MatrixXd>(T, EigenvaluesOnly).eigenvalues()).cwiseAbs().maxCoeff()
<< "\n";
}
EigenvaluesOnly
residual |T V - V L| / |T|:               1.6971e-15
orthogonality |V^T V - I|:                4.16067e-14
max difference to SelfAdjointEigenSolver: 9.76996e-15

Toeplitz, circulant and Hankel systems

Love's integral equation and a preconditioned Toeplitz system

A translation-invariant kernel discretized on a uniform grid gives a Toeplitz matrix. Love's equation [10] is solved directly by LookAheadLevinson [11] in \( O(n^2) \). For large systems, conjugate gradients use the FFT-based Toeplitz product and Strang's Circulant preconditioner [12], [13], \( O(n \log n) \) per iteration.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Two Toeplitz problems.
//
// Love's integral equation for the field between two coaxial disks at unit
// distance (a classical test problem of electrostatics),
// u(x) - (1/pi) \int_{-1}^{1} u(t) / (1 + (x - t)^2) dt = 1, -1 <= x <= 1.
// The midpoint rule on n equal cells gives (I - K) u = 1 with a symmetric
// Toeplitz K, K_ij = h / (pi (1 + (x_i - x_j)^2)), which LookAheadLevinson
// solves directly in O(n^2).
//
// A large dense Toeplitz system, T_ij = (1 + |i - j|)^(-1.1), solved
// by conjugate gradients: the Toeplitz product costs O(n log n) through the
// FFT, and the Strang preconditioner -- the central diagonals of T wrapped into
// a circulant C, inverted by Circulant::solve in O(n log n) -- clusters the
// spectrum of C^{-1} T around 1.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace Eigen;
// The iterative solvers' preconditioner interface around Circulant::solve.
class StrangPreconditioner {
public:
void setToeplitzColumn(const VectorXd& t) {
const Index n = t.size();
VectorXd c(n);
for (Index k = 0; k < n; ++k) c[k] = t[k <= n / 2 ? k : n - k];
m_circulant = Circulant<double>(c);
}
template <typename MatrixType>
StrangPreconditioner& analyzePattern(const MatrixType&) {
return *this;
}
template <typename MatrixType>
StrangPreconditioner& factorize(const MatrixType&) {
return *this;
}
template <typename MatrixType>
StrangPreconditioner& compute(const MatrixType&) {
return *this;
}
template <typename Rhs>
VectorXd solve(const MatrixBase<Rhs>& b) const {
return m_circulant.solve(b);
}
ComputationInfo info() const { return Success; }
private:
Circulant<double> m_circulant{VectorXd::Ones(1)};
};
int main() {
const double pi = std::acos(-1.0);
std::cout << "Love's equation:\n n u(0)\n";
for (int n : {64, 128, 256, 512}) {
const double h = 2.0 / n;
VectorXd c(n);
for (int k = 0; k < n; ++k) c[k] = -h / (pi * (1 + (k * h) * (k * h)));
c[0] += 1;
const VectorXd u = LookAheadLevinson<double>(makeToeplitz(c, c)).solve(VectorXd::Ones(n));
std::cout << std::setw(6) << n << " " << std::setprecision(8) << (u[n / 2 - 1] + u[n / 2]) / 2 << "\n";
}
const int n = 1 << 16;
VectorXd t(n);
for (int k = 0; k < n; ++k) t[k] = std::pow(1.0 + k, -1.1);
const auto T = makeToeplitz(t, t);
const VectorXd b = VectorXd::Ones(n);
ConjugateGradient<std::decay_t<decltype(T)>, Lower | Upper, IdentityPreconditioner> plain(T);
plain.setTolerance(1e-10);
ConjugateGradient<std::decay_t<decltype(T)>, Lower | Upper, StrangPreconditioner> strang;
strang.setTolerance(1e-10);
strang.preconditioner().setToeplitzColumn(t);
strang.compute(T);
const VectorXd x0 = plain.solve(b), x1 = strang.solve(b);
std::cout << "Toeplitz system, n = " << n << ", CG iterations to a 1e-10 residual:\n";
std::cout << " no preconditioner: " << plain.iterations() << "\n";
std::cout << " Strang circulant: " << strang.iterations() << "\n";
}
An n x n circulant matrix represented by its first column.
Definition Circulant.h:103
Look-ahead Levinson direct solver for general Toeplitz systems.
Definition LookAheadLevinson.h:87
const Solve< LookAheadLevinson, Rhs > solve(const MatrixBase< Rhs > &b) const
Toeplitz< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > makeToeplitz(const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row)
Definition Toeplitz.h:337
Love's equation:
     n  u(0)
    64  1.9190057
   128  1.9190254
   256  1.9190303
   512  1.9190316
Toeplitz system, n = 65536, CG iterations to a 1e-10 residual:
  no preconditioner: 44
  Strang circulant:  6

Pade approximation

The denominator of a Pade approximant [14] solves a Hankel system in the Taylor coefficients, solved in \( O(n^2) \) through its Toeplitz equivalent. Rescaling the variable equilibrates the coefficients and keeps the system Hankel.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The [m/m] Pade approximant p(x)/q(x) of exp(x), q(0) = 1, from its Taylor
// coefficients. Matching the series through degree 2m gives the denominator
// from a Hankel system in the coefficients c_k,
// sum_{j=1}^{m} c_{m+i-j} q_j = -c_{m+i}, i = 1..m,
// written with H(i,j) = c_{i+j+1} (j reversed), and the numerator by a
// truncated convolution p_i = sum_{j<=i} c_{i-j} q_j.
//
// The raw coefficients 1/k! fall from 1 to 1/(2m)! across H, which leaves it
// badly scaled: kappa(H) ~ 7e15 at m = 8. Approximating exp(t y) instead, with
// coefficients c_k = t^k / k!, scales H to t D H D, D = diag(t^i) -- still
// Hankel -- and t = m equilibrates it: kappa(H) ~ 5e7 at m = 8. The
// approximant of exp(x) is then p(x/t) / q(x/t), since the substitution
// preserves both the degrees and the order of contact.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace Eigen;
int main() {
std::cout << " m |r(1) - e| |r(-2) - e^-2|\n";
for (int m : {2, 4, 6, 8, 10}) {
const double t = m;
VectorXd c(2 * m + 1);
c[0] = 1;
for (int k = 1; k <= 2 * m; ++k) c[k] = c[k - 1] * t / k;
// H(i, j) = c_{i+j+1} for i, j = 0..m-1: first column c_1..c_m, last row c_m..c_{2m-1}.
const auto H = makeHankel(c.segment(1, m), c.segment(m, m));
// The unknowns are q_m, ..., q_1 (reversed): row i reads c_{i+1} q_m + ... + c_{m+i} q_1.
const VectorXd reversed = H.solve(-c.segment(m + 1, m));
VectorXd q(m + 1), p(m + 1);
q[0] = 1;
q.tail(m) = reversed.reverse();
for (int i = 0; i <= m; ++i) p[i] = c.head(i + 1).reverse().dot(q.head(i + 1));
const auto r = [&](double x) {
const double y = x / t;
double num = 0, den = 0;
for (int i = m; i >= 0; --i) {
num = num * y + p[i];
den = den * y + q[i];
}
return num / den;
};
std::cout << std::setw(2) << m << " " << std::setw(15) << std::abs(r(1) - std::exp(1.0)) << " "
<< std::abs(r(-2) - std::exp(-2.0)) << "\n";
}
}
Hankel< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > makeHankel(const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row)
Definition Hankel.h:412
 m  |r(1) - e|      |r(-2) - e^-2|
 2       0.00399611  0.00752186
 4      1.10177e-07  3.06263e-06
 6      4.82281e-13  2.0842e-10
 8      4.44089e-16  4.02456e-15
10                0  1.11022e-16

Signal and image processing

Deconvolution by Toeplitz least squares

The full convolution of a signal with a kernel is a rectangular Toeplitz matrix. LSMR [22] solves the least-squares problem without forming it: products with the matrix and, through Toeplitz::adjoint, its transpose cost \( O(p \log p) \) each by circulant embedding [13]. The matrix-free solution agrees with the dense QR of the materialized matrix.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Deconvolution as a rectangular Toeplitz least-squares problem. A signal s of
// length n recorded through a causal kernel h of length k is the full
// convolution y = T s, with T the (n + k - 1) x n Toeplitz matrix whose first
// column holds h. LSMR recovers s from y without forming T: every iteration
// applies T and T^T through the FFT, in O(p log p) for the embedding length
// p >= n + k - 1, the adjoint reusing the embedding symbol. For the kernel
// h_j = a^j, |a| < 1, the system is well conditioned, kappa ~ (1 + a)/(1 - a),
// so noise in y passes into s amplified by at most that factor. The dense QR
// of the materialized matrix gives the same solution at O(m n^2).
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
#include <random>
using namespace Eigen;
int main() {
const int n = 1000, k = 50, m = n + k - 1;
const double a = 0.9;
// The signal: two Gaussian pulses and a step.
VectorXd s(n);
for (int i = 0; i < n; ++i)
s[i] = std::exp(-std::pow((i - 300) / 20.0, 2)) + 0.5 * std::exp(-std::pow((i - 450) / 10.0, 2)) +
(i > 700 && i < 850 ? 0.8 : 0.0);
VectorXd column = VectorXd::Zero(m), row = VectorXd::Zero(n);
for (int j = 0; j < k; ++j) column[j] = std::pow(a, j);
row[0] = column[0];
const auto T = makeToeplitz(column, row); // m x n
const VectorXd y = T * s;
LSMR<std::decay_t<decltype(T)>, IdentityPreconditioner> lsmr(T);
lsmr.setTolerance(1e-12);
const VectorXd recovered = lsmr.solve(y);
std::cout << "LSMR, exact data: " << lsmr.iterations() << " iterations, max error "
<< (recovered - s).cwiseAbs().maxCoeff() << "\n";
// 1% noise from a generator whose sequence the C++ standard fixes.
std::minstd_rand generator(1);
VectorXd noisy = y;
for (int i = 0; i < m; ++i) noisy[i] += 0.01 * (2.0 * generator() / generator.max() - 1);
const VectorXd fromNoisy = lsmr.solve(noisy);
std::cout << "LSMR, noisy data: " << lsmr.iterations() << " iterations, max error "
<< (fromNoisy - s).cwiseAbs().maxCoeff() << "\n";
const MatrixXd dense = T;
std::cout << "dense QR of the " << m << " x " << n << " matrix, noisy data: max error "
<< (dense.householderQr().solve(noisy) - s).cwiseAbs().maxCoeff() << "\n";
}
LSMR, exact data:  178 iterations, max error 3.59591e-10
LSMR, noisy data:  219 iterations, max error 0.0182915
dense QR of the 1049 x 1000 matrix, noisy data: max error 0.0182915

Image deblurring with periodic boundaries

A blur with periodic boundary conditions is a Bccb matrix [5]. A motion blur annihilates whole frequency lines, which Bccb::rank counts exactly, so the pseudo-inverse Bccb::solve cannot undo it and amplifies the noise next to those lines. Tikhonov regularization stays within the class: \( A^H A + \lambda I \) is the Bccb generated by the autocorrelation of the point spread function, computed with two products, and each \( \lambda \) costs one \( O(N \log N) \) solve.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Image deblurring with periodic boundary conditions. Blurring an n x n image
// X with a point spread function G is the 2-D circular convolution G (*) X, so
// the blur matrix A is a Bccb. For a motion blur over L pixels, the box filter,
// the symbol vanishes on the L - 1 frequency lines k = j n / L: A is exactly
// rank deficient, Bccb::rank counts the retained modes, and the pseudo-inverse
// A.solve recovers nothing on those lines while amplifying the noise of the
// recorded image on the lines next to them. Tikhonov regularization,
// x_lambda = (A^H A + lambda I)^{-1} A^H b,
// keeps the structure: A^H A + lambda I is the Bccb whose generator is the
// autocorrelation A^H (A e_0) of the PSF plus lambda at the origin, so each
// candidate lambda costs one O(N log N) solve.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
#include <random>
using namespace Eigen;
int main() {
const int n = 128, N = n * n;
const int L = 8; // the camera moves L pixels along the columns during the exposure
MatrixXd G = MatrixXd::Zero(n, n);
G.col(0).head(L).setConstant(1.0 / L);
const auto A = makeBccb(G);
// The image: a bright rectangle and a disc on a dark background.
MatrixXd X = MatrixXd::Constant(n, n, 0.1);
X.block(32, 40, 32, 48).setConstant(1.0);
for (int j = 0; j < n; ++j)
for (int i = 0; i < n; ++i)
if ((i - 90) * (i - 90) + (j - 40) * (j - 40) < 400) X(i, j) = 0.6;
const VectorXd x = X.reshaped();
// Blur and add 1% noise from a generator whose sequence the C++ standard fixes.
std::minstd_rand generator(1);
VectorXd b = A * x;
for (int i = 0; i < N; ++i) b[i] += 0.01 * (2.0 * generator() / generator.max() - 1);
const VectorXd s = A.singularValues(); // decreasing
std::cout << "rank " << A.rank() << " of " << N << ", smallest retained singular value " << s[A.rank() - 1] << "\n";
std::cout << "relative error of the blurred image: " << (b - x).norm() / x.norm() << "\n";
std::cout << "relative error of the pseudo-inverse: " << (A.solve(b) - x).norm() / x.norm() << "\n";
VectorXd e0 = VectorXd::Zero(N);
e0[0] = 1;
const VectorXd autocorrelation = A.adjoint() * VectorXd(A * e0); // first column of A^H A
const VectorXd Ahb = A.adjoint() * b;
for (double lambda : {1e-4, 1e-3, 1e-2, 1e-1}) {
VectorXd g = autocorrelation;
g[0] += lambda;
const VectorXd xl = makeBccb(g.reshaped(n, n)).solve(Ahb);
std::cout << "Tikhonov, lambda = " << lambda << ": relative error " << (xl - x).norm() / x.norm() << "\n";
}
}
Derived & setConstant(Index rows, Index cols, const Scalar &val)
rank 15488 of 16384, smallest retained singular value 0.0243936
relative error of the blurred image:  0.317085
relative error of the pseudo-inverse: 0.214809
Tikhonov, lambda = 0.0001: relative error 0.198827
Tikhonov, lambda = 0.001: relative error 0.140999
Tikhonov, lambda = 0.01: relative error 0.0999269
Tikhonov, lambda = 0.1: relative error 0.16459

Prony's method

A sum of exponentials obeys a linear recurrence whose coefficients solve a Hankel system in the samples [23]; the roots of its characteristic polynomial are the damping rates and frequencies, and the amplitudes solve the dual Vandermonde system with complex nodes, which BjorckPereyra handles in Leja order. The recurrence residual over all samples is a rectangular Hankel product.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Prony's method fits a sum of r complex exponentials, f_t = sum_j c_j z_j^t,
// to equally spaced samples f_0, ..., f_{m-1}. Every such sequence obeys the
// linear recurrence whose characteristic polynomial has the z_j as roots,
// f_{t+r} + a_{r-1} f_{t+r-1} + ... + a_0 f_t = 0,
// so the coefficients a solve a Hankel system in the samples, H(t, k) = f_{t+k},
// and the recurrence residual over all samples is a rectangular Hankel product.
// The roots are the nodes z_j, with damping -log|z_j| and frequency arg z_j; the
// amplitudes solve the dual Vandermonde system V^T c = f, V(j, t) = z_j^t, with
// complex nodes, by Bjorck-Pereyra. A real signal gives conjugate pairs.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <complex>
#include <iomanip>
#include <iostream>
using namespace Eigen;
int main() {
const int r = 4, m = 64;
// Two damped sinusoids A exp(-alpha t) cos(omega t + phi): four exponentials.
const double alpha[2] = {0.02, 0.05}, omega[2] = {0.3, 1.1}, A[2] = {1.0, 0.5}, phi[2] = {0.0, 0.7};
VectorXd f = VectorXd::Zero(m);
for (int t = 0; t < m; ++t)
for (int j = 0; j < 2; ++j) f[t] += A[j] * std::exp(-alpha[j] * t) * std::cos(omega[j] * t + phi[j]);
// The r x r Hankel system on the first 2r samples, and the recurrence on all m.
const VectorXd a = makeHankel(f.head(r), f.segment(r - 1, r)).solve(-f.segment(r, r));
const auto H = makeHankel(f.head(m - r), f.segment(m - r - 1, r));
std::cout << "recurrence residual over " << m << " samples: " << (H * a + f.tail(m - r)).norm() << "\n";
// The roots of z^r + a_{r-1} z^{r-1} + ... + a_0 are the eigenvalues of its companion matrix.
MatrixXd companion = MatrixXd::Zero(r, r);
companion.bottomLeftCorner(r - 1, r - 1).setIdentity();
companion.col(r - 1) = -a;
const VectorXcd z = EigenSolver<MatrixXd>(companion, false).eigenvalues();
const VectorXcd c = amplitudes.transpose().solve(f.head(r).cast<std::complex<double>>());
std::cout << std::fixed << std::setprecision(4) << " damping frequency amplitude phase\n";
for (int j = 0; j < r; ++j)
if (z[j].imag() > 0) // one root of each conjugate pair; c_j = (A / 2) exp(i phi)
std::cout << std::setw(9) << -std::log(std::abs(z[j])) << std::setw(11) << std::arg(z[j]) << std::setw(11)
<< 2 * std::abs(c[j]) << std::setw(8) << std::arg(c[j]) << "\n";
}
Björck-Pereyra O(n^2) solver for square Vandermonde systems.
Definition Vandermonde.h:401
const EigenvalueType & eigenvalues() const
Vandermonde< typename Derived::Scalar, Derived::SizeAtCompileTime, Dynamic > makeVandermonde(const MatrixBase< Derived > &nodes, Index cols)
Definition Vandermonde.h:347
Matrix< std::complex< double >, Dynamic, 1 > VectorXcd
recurrence residual over 64 samples: 3.14091e-14
  damping  frequency  amplitude  phase
   0.0500     1.1000     0.5000  0.7000
   0.0200     0.3000     1.0000  0.0000

Interpolation and approximation

Interpolatory quadrature

The weights of an interpolatory quadrature rule solve the transposed Vandermonde system, the dual problem that BjorckPereyra [16] solves in \( O(n^2) \); on Chebyshev extreme points they are the Clenshaw-Curtis weights [15]. The primal solve gives interpolation coefficients.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Interpolatory quadrature: the weights w of a rule sum_i w_i f(x_i) that is
// exact for polynomials of degree < n solve the transposed Vandermonde system
// V^T w = m with the moments m_k = \int_{-1}^{1} x^k dx. Bjorck-Pereyra solves
// it (the dual system) in O(n^2); on Chebyshev extreme points the weights are
// those of Clenshaw-Curtis quadrature. The primal system V a = f gives the
// monomial coefficients of the interpolating polynomial.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace Eigen;
int main() {
const double pi = std::acos(-1.0);
const double exact = 2 * std::sinh(1.0); // \int_{-1}^{1} e^x dx
std::cout << " n sum(w) error on e^x\n";
for (int n : {5, 9, 13, 17}) {
VectorXd x(n), moments(n);
for (int i = 0; i < n; ++i) x[i] = -std::cos(pi * i / (n - 1)); // increasing nodes
for (int k = 0; k < n; ++k) moments[k] = k % 2 == 0 ? 2.0 / (k + 1) : 0.0;
const VectorXd w = bp.transpose().solve(moments);
std::cout << std::setw(3) << n << " " << std::setw(6) << w.sum() << " "
<< std::abs(w.dot(x.array().exp().matrix()) - exact) << "\n";
}
// Interpolation: the cubic through four samples of x^3 - 2x + 1.
const Vector4d x(-1, 0, 0.5, 2);
const Vector4d f = x.array().cube() - 2 * x.array() + 1;
std::cout << "monomial coefficients of the interpolant: "
<< BjorckPereyra<double>(makeVandermonde(x)).solve(f).transpose() << "\n";
}
const Solve< BjorckPereyra, Rhs > solve(const MatrixBase< Rhs > &f) const
Matrix< double, 4, 1 > Vector4d
  n  sum(w)  error on e^x
  5       2  2.70104e-05
  9       2  2.04636e-11
 13       2  0
 17       2  4.44089e-16
monomial coefficients of the interpolant:  1 -2  0  1

A discretized Cauchy integral

Representing an analytic function by point charges outside its domain leads to a Cauchy system, factored with pivoting in \( O(n^2) \) by CauchyLU [18]; the error decays geometrically, as for the trapezoidal rule on a circle [17].

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The Cauchy integral formula f(z) = (1/2 pi i) \int_{|w|=rho} f(w) / (w - z) dw
// discretized: a function analytic in |z| < R is represented on the unit disk
// by n point charges, r(z) = sum_j c_j / (z - w_j), on the circle |w| = rho
// between 1 and R. Fitting r to f at n points z_i of the unit circle is a
// square Cauchy system with entries 1/(z_i - w_j), factored in O(n^2) by
// CauchyLU; the error decays like (R/rho)^-n + rho^-n, fastest for
// rho = sqrt(R). Here f(z) = exp(z) / (z - 1.5), so R = 1.5.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <complex>
#include <iomanip>
#include <iostream>
using namespace Eigen;
using Complex = std::complex<double>;
int main() {
const double pi = std::acos(-1.0), R = 1.5, rho = std::sqrt(R);
const auto f = [R](const Complex& z) { return std::exp(z) / (z - R); };
std::cout << " n max |r(z) - f(z)| on |z| = 1\n";
for (int n : {16, 32, 64, 128}) {
VectorXcd z(n), w(n), fz(n);
for (int j = 0; j < n; ++j) {
z[j] = std::polar(1.0, 2 * pi * j / n);
w[j] = std::polar(rho, 2 * pi * (j + 0.5) / n);
fz[j] = f(z[j]);
}
// By the maximum principle the error on the circle bounds it on the disk.
double error = 0;
for (int k = 0; k < 1000; ++k) {
const Complex t = std::polar(1.0, 2 * pi * (k + 0.37) / 1000);
error = std::max(error, std::abs((c.array() / (t - w.array())).sum() - f(t)));
}
std::cout << std::setw(4) << n << " " << error << "\n";
}
}
Partially pivoted O(n^2) LU solver for square Cauchy systems (Gohberg-Kailath-Olshevsky).
Definition Cauchy.h:333
const Solve< CauchyLU, Rhs > solve(const MatrixBase< Rhs > &b) const
Cauchy< typename XDerived::Scalar, XDerived::SizeAtCompileTime, YDerived::SizeAtCompileTime > makeCauchy(const MatrixBase< XDerived > &x, const MatrixBase< YDerived > &y)
Definition Cauchy.h:289
   n  max |r(z) - f(z)| on |z| = 1
  16  0.419978
  32  0.016094
  64  2.49846e-05
 128  5.79478e-11

Polynomial least squares and the Hilbert matrix

The normal equations of continuous least-squares approximation in the monomial basis have the Hilbert matrix, a Cauchy matrix [26]: CauchyLU solves them in \( O(n^2) \) and Cauchy::determinant gives \( \det H_n \) in closed form where dense LU loses digits. The fitted polynomial is far less sensitive to \( \kappa(H_n) \) than its coefficients, and matches the discrete fit by a dense QR of the rectangular Vandermonde matrix; Vandermonde products evaluate both.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Least-squares polynomial approximation in the monomial basis. The normal
// equations of the continuous problem, min \int_0^1 (f - sum_j c_j x^j)^2 dx,
// have the Hilbert matrix H_ij = 1/(i + j + 1), the Cauchy matrix with nodes
// x_i = i + 1 and y_j = -j, and the moments m_i = \int_0^1 x^i f dx on the right.
// CauchyLU solves them in O(n^2), and Cauchy::determinant evaluates det H in
// closed form where dense LU, at kappa(H_n) ~ e^{3.5 n}, loses digits. The
// coefficients inherit the conditioning, the fitted polynomial much less: the
// coefficient error d = H^{-1} r of a residual r = H c - m perturbs the fit by
// (d^T H d)^{1/2} = (r^T H^{-1} r)^{1/2} in L^2, so the fit loses at most about
// sqrt(kappa) eps where the coefficients can lose kappa eps. The discrete
// least-squares fit -- a dense QR of the rectangular Vandermonde matrix of 200
// sample points -- is the reference; Vandermonde products (Horner's rule)
// evaluate both fits.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace Eigen;
int main() {
const double e = std::exp(1.0);
const ArrayXd samples = ArrayXd::LinSpaced(200, 0, 1), fine = ArrayXd::LinSpaced(1001, 0, 1);
std::cout << " n det H: Cauchy dense LU exact fit error: Hilbert QR\n";
for (int n : {4, 6, 8, 10}) {
const auto H = makeCauchy(VectorXd::LinSpaced(n, 1, n), -VectorXd::LinSpaced(n, 0, n - 1));
// m_i = e - i m_{i-1}, run backwards from m_40 ~ e / 41: the forward recurrence amplifies errors by i!.
VectorXd moments(n);
double mi = e / 41;
for (int i = 40; i > 0; --i) {
mi = (e - mi) / i;
if (i <= n) moments[i - 1] = mi;
}
const VectorXd c = CauchyLU<double>(H).solve(moments);
const MatrixXd V = makeVandermonde(samples.matrix(), n); // 200 x n
const VectorXd cq = V.colPivHouseholderQr().solve(samples.exp().matrix());
// det H_n = c_n^4 / c_{2n} with c_n = prod_{i<n} i!
double cn = 1, c2n = 1, factorial = 1;
for (int i = 1; i < 2 * n; ++i) {
factorial *= i;
if (i < n) cn *= factorial;
c2n *= factorial;
}
const auto E = makeVandermonde(fine.matrix(), n);
std::cout << std::setw(2) << n << std::setprecision(8) << std::setw(16) << H.determinant() << std::setw(15)
<< MatrixXd(H).determinant() << std::setw(15) << std::pow(cn, 4) / c2n << std::setprecision(3)
<< std::setw(16) << (E * c - fine.exp().matrix()).cwiseAbs().maxCoeff() << std::setw(13)
<< (E * cq - fine.exp().matrix()).cwiseAbs().maxCoeff() << "\n";
}
}
 n  det H: Cauchy      dense LU       exact          fit error: Hilbert  QR
 4   1.6534392e-07  1.6534392e-07  1.6534392e-07         0.00105      0.00102
 6   5.3672999e-18  5.3672999e-18  5.3672999e-18         2.6e-06     2.41e-06
 8   2.7370501e-33  2.7370501e-33  2.7370501e-33        3.28e-09     2.85e-09
10   2.1641792e-53  2.1644017e-53  2.1641792e-53        3.47e-11     2.01e-12

Separable least squares on a grid

The design matrix of a tensor-product polynomial fit on a grid is the Kronecker product of two rectangular Vandermonde matrices. KroneckerOperator::leastSquaresSolve applies \( (A \otimes B)^+ = A^+ \otimes B^+ \) [27] with one complete orthogonal decomposition per factor, and KroneckerOperator::rank and KroneckerOperator::singularValues come from the factors too; the dense decomposition of the assembled matrix agrees.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// Least-squares fitting of a surface sampled on a grid by a tensor-product
// polynomial sum_{p,q} c_pq x^p y^q. With the samples F(x_i, y_j) stored with x
// as the fast index, the design matrix is the Kronecker product V_y (x) V_x of
// the two rectangular Vandermonde matrices, and KroneckerOperator solves the
// least-squares problem through one complete orthogonal decomposition per
// factor, (A (x) B)^+ = A^+ (x) B^+: for m points per direction and degrees
// P, Q, the two decompositions cost O(m (P^2 + Q^2)) and applying them
// O(m^2 (P + Q)), against O(m^2 P^2 Q^2) for the assembled m^2 x (P+1)(Q+1)
// matrix. Its rank and singular values also come from the factors.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
int main() {
const int m = 60; // grid points per direction
const ArrayXd x = ArrayXd::LinSpaced(m, -1, 1), y = ArrayXd::LinSpaced(m, -1, 1);
MatrixXd F(m, m); // F(i, j) = exp(x_i y_j), with x the fast index of vec(F)
for (int j = 0; j < m; ++j)
for (int i = 0; i < m; ++i) F(i, j) = std::exp(x[i] * y[j]);
std::cout << "degree rank kappa max fit error |c - c_dense|\n";
for (int degree : {2, 4, 6, 8}) {
const MatrixXd Vx = makeVandermonde(x.matrix(), degree + 1), Vy = makeVandermonde(y.matrix(), degree + 1);
const auto design = makeKroneckerOperator(Vy, Vx); // m^2 x (degree + 1)^2
const VectorXd c = design.leastSquaresSolve(F.reshaped());
const VectorXd s = design.singularValues();
const MatrixXd dense = design;
const VectorXd reference = dense.completeOrthogonalDecomposition().solve(F.reshaped());
std::cout << " " << degree << " " << design.rank() << " " << s.maxCoeff() / s.minCoeff() << " "
<< (F.reshaped() - design * c).cwiseAbs().maxCoeff() << " " << (c - reference).cwiseAbs().maxCoeff()
<< "\n";
}
}
degree  rank  kappa        max fit error  |c - c_dense|
  2     9    13.4419  0.125548    8.88178e-16
  4     25    330.266  0.00190687    3.10862e-15
  6     49    9183.62  1.1042e-05    5.21805e-14
  8     81    270808  3.26594e-08    2.07241e-13

Statistics and estimation

A Gaussian-process likelihood

A covariance that is noise plus a low-rank feature model [19], [20] is a DiagonalPlusLowRank operator. Its solve (Woodbury identity) and determinant (matrix determinant lemma) cost \( O(n k^2) \), the price of evaluating the log-likelihood.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The log-likelihood of observations y under a Gaussian process with k Fourier
// features on a fixed frequency grid and noise variance s^2,
// log N(y | 0, S) = -(y^T S^{-1} y + log det S + n log(2 pi)) / 2,
// S = s^2 I + U U^T, U = (n x k feature matrix),
// costs O(n k^2) with DiagonalPlusLowRank: the Woodbury identity for the solve
// and the matrix determinant lemma for the determinant, instead of the O(n^3)
// Cholesky factorization of the dense covariance.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iostream>
using namespace Eigen;
int main() {
const double pi = std::acos(-1.0), noise = 1.0;
const int n = 1000, k = 20;
VectorXd t(n), y(n);
for (int i = 0; i < n; ++i) {
t[i] = 10.0 * i / n;
y[i] = std::sin(t[i]) + 0.3 * std::cos(3 * t[i]);
}
// Features sqrt(2/k) cos(omega_j t + phase_j) on a fixed frequency grid.
MatrixXd U(n, k);
for (int j = 0; j < k; ++j)
for (int i = 0; i < n; ++i) U(i, j) = std::sqrt(2.0 / k) * std::cos(0.25 * j * t[i] + 0.5 * j);
const auto S = makeDiagonalPlusLowRank(VectorXd::Constant(n, noise * noise), U, U);
const double logLikelihood = -(y.dot(S.solve(y)) + std::log(S.determinant()) + n * std::log(2 * pi)) / 2;
const MatrixXd dense = noise * noise * MatrixXd::Identity(n, n) + U * U.transpose();
const LLT<MatrixXd> llt(dense);
const double logDet = 2 * llt.matrixL().toDenseMatrix().diagonal().array().log().sum();
const double reference = -(y.dot(llt.solve(y)) + logDet + n * std::log(2 * pi)) / 2;
std::cout << "log-likelihood, Woodbury: " << logLikelihood << "\n";
std::cout << "log-likelihood, dense: " << reference << "\n";
}
DiagonalPlusLowRank< typename DDerived::Scalar, DDerived::SizeAtCompileTime, UDerived::ColsAtCompileTime > makeDiagonalPlusLowRank(const MatrixBase< DDerived > &d, const MatrixBase< UDerived > &U, const MatrixBase< VDerived > &V)
Definition DiagonalPlusLowRank.h:352
log-likelihood, Woodbury: -957.439
log-likelihood, dense:    -957.439

A Kalman measurement update

With a diagonal prior and \( k \) measurements, the posterior precision is diagonal plus rank \( k \), and DiagonalPlusLowRank::inverse returns the posterior covariance as another DiagonalPlusLowRank, since the Woodbury identity is the Kalman update [24]. The posterior mean is one \( O(nk) \) product and the posterior variances are read off the diagonal; the dense \( n \times n \) computation agrees.

Example:Output:
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
// The measurement update of a Kalman filter in information form. A field x on
// n grid points has the prior N(0, tau^2 I); k sensors record weighted sums
// y = H x + e over short footprints, with noise e ~ N(0, s^2 I). The posterior
// precision
// P^{-1} = tau^{-2} I + s^{-2} H^T H
// is diagonal plus rank k, and DiagonalPlusLowRank::inverse returns the
// posterior covariance P as another DiagonalPlusLowRank: the Woodbury identity,
// which is the Kalman update. The posterior mean P H^T y / s^2 is then one O(nk)
// product and the posterior variances are the diagonal of P, with no n x n
// matrix anywhere.
#include <contrib/Eigen/StructuredMatrices>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <random>
using namespace Eigen;
int main() {
const int n = 400, k = 40, width = 4;
const double tau = 1.0, s = 0.05;
// Sensor j averages the points [100 + 2 j, 100 + 2 j + width); neighboring footprints overlap.
MatrixXd H = MatrixXd::Zero(k, n);
for (int j = 0; j < k; ++j) H.row(j).segment(100 + 2 * j, width).setConstant(1.0 / width);
VectorXd x(n);
for (int i = 0; i < n; ++i) x[i] = std::sin(0.05 * i) + 0.5 * std::cos(0.2 * i);
std::minstd_rand generator(1);
VectorXd y = H * x;
for (int j = 0; j < k; ++j) y[j] += s * (2.0 * generator() / generator.max() - 1);
const auto information = makeDiagonalPlusLowRank(VectorXd::Constant(n, 1 / (tau * tau)), H.transpose() / (s * s),
H.transpose()); // P^{-1}
const auto P = information.inverse();
const VectorXd mean = P * VectorXd(H.transpose() * y / (s * s));
const MatrixXd dense = (MatrixXd::Identity(n, n) / (tau * tau) + H.transpose() * H / (s * s)).inverse();
const VectorXd denseMean = dense * H.transpose() * y / (s * s);
double varianceError = 0;
for (int i = 0; i < n; ++i) varianceError = std::max(varianceError, std::abs(P.coeff(i, i) - dense(i, i)));
std::cout << "point footprints truth posterior mean posterior std\n";
for (int i : {50, 100, 101, 140, 179, 250}) {
const int footprints = int((H.col(i).array() != 0).count());
std::cout << std::setw(5) << i << std::setw(12) << footprints << std::setw(7) << std::setprecision(3) << x[i]
<< std::setw(16) << mean[i] << std::setw(15) << std::sqrt(P.coeff(i, i)) << "\n";
}
std::cout << std::setprecision(6) << "max |mean - dense|: " << (mean - denseMean).cwiseAbs().maxCoeff()
<< ", max |variance - dense|: " << varianceError << "\n";
}
point  footprints  truth    posterior mean  posterior std
   50           0  0.179               0              1
  100           1 -0.755          -0.771          0.752
  101           1 -0.834          -0.771          0.752
  140           2  0.176           0.246          0.732
  179           2  0.296           0.287          0.747
  250           0  0.416               0              1
max |mean - dense|: 4.5941e-13, max |variance - dense|: 8.88178e-16