![]() |
Eigen-Contrib
5.0.1-dev+master
|
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.
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 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);
SparseMatrix<double> D(n, n);
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 VectorXd u = poisson.solve(f);
std::cout << "n = " << n << ": max error " << (u - exact).cwiseAbs().maxCoeff() << "\n";
}
}
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 |
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);
SparseMatrix<double> D(n, n);
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 = 24, steps = 100;
const double h = 1.0 / (n + 1), tau = 1e-3;
const SparseMatrix<double> D = secondDifference(n);
SparseMatrix<double> I(n, n);
I.setIdentity();
const auto M =
makeKroneckerSum(SparseMatrix<double>(I + tau * D), SparseMatrix<double>(tau * D), SparseMatrix<double>(tau * D));
// 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";
}
void makeCompressed() 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 |
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;
const double h = 1.0 / (n + 1);
SparseMatrix<double> A(n, n);
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 VectorXd f = VectorXd::Ones(n * n);
const VectorXd u = solver.solve(f);
A = L; // the assembled n^2 x n^2 matrix, for comparison
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 |
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);
SparseMatrix<double> D(n, n);
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);
SparseMatrix<double> I(n, n);
I.setIdentity();
const auto Id = MatrixXd::Identity(n, n);
// 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);
}
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 |
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);
SparseMatrix<double> D(n, n);
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;
}
// 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>
return m_solver.solve(b);
}
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 VectorXd f = VectorXd::Ones(n * n);
// The preconditioner gets its operator before compute(), which reads its info().
SparseMatrix<double> I(n, n);
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 Lower Upper | 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 |
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);
// 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);
MatrixXd C;
C = makeCirculant(column); // dense, for the Kronecker sum
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 |
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.
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}) {
VectorXd shifted = spectralColumn(N, 2);
shifted[0] -= 1;
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() << " "
}
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 |
\( 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();
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: "
}
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 |
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);
}
<< 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 |
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);
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
|
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 |
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:
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>
return m_circulant.solve(b);
}
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;
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 VectorXd b = VectorXd::Ones(n);
plain.setTolerance(1e-10);
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 Success | 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
|
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}.
// 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 |
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 VectorXd y = T * s;
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 |
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);
// 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);
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 Ahb = A.adjoint() * b;
for (double lambda : {1e-4, 1e-3, 1e-2, 1e-1}) {
VectorXd g = autocorrelation;
g[0] += lambda;
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 |
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.
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 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 |
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: "
}
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 |
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 |
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}) {
// 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 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;
}
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 |
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 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 |
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 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 |
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);
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 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 |