This module provides lightweight operator types for displacement-structured matrices together with fast matrix-vector products and direct solvers:
Circulant : a circulant matrix, diagonalized by the DFT;
Toeplitz : a (possibly rectangular) Toeplitz matrix, multiplied in O(n log n) via circulant embedding, with O(n^2) square solves by the look-ahead Levinson algorithm (LookAheadLevinson);
Hankel : a (possibly rectangular) Hankel matrix – a column-reversed Toeplitz matrix – with the same O(n log n) products, and square solves through the Toeplitz equivalent;
KroneckerOperator : the Kronecker product of two dense, diagonal, sparse or identity matrices, or of nested Kronecker operators, as an implicit operator; products, solves, least squares, eigendecomposition, SVD, inverse and determinant all factor through the operands, diagonal factors are stored and applied in diagonal form, sparse factors through sparse-dense products and SparseLU, Identity() factors not at all, and the product materializes into a dense or a sparse matrix on assignment;
KroneckerSum : the Kronecker sum \( A \oplus B = A \otimes I + I \otimes B \) of square factors of the same kinds, nestable for three or more factors – the separable operators of finite-difference discretizations on tensor-product grids – with products through \( B X + X A^T \), materialization, and direct solves (BartelsStewart) through the Schur forms of the factors; either operator's sparseView() is a lazy SparseMatrixBase expression (KroneckerSparseView) iterating the stored entries from the factors;
DiagonalPlusLowRank : a diagonal matrix plus a rank-k correction, with O(nk) products and O(nk^2) Woodbury solves, closed under inversion;
Vandermonde : a Vandermonde matrix stored as its nodes, with Horner products and O(n^2) Björck-Pereyra primal/dual solves (BjorckPereyra);
Cauchy : a Cauchy matrix stored as its node vectors, solved in O(n^2) with genuine partial pivoting through the displacement structure (CauchyLU, Gohberg-Kailath-Olshevsky);
DPR1EigenSolver : the direct O(n^2) secular-equation eigensolver for real symmetric diagonal-plus-rank-one matrices D + rho*z*z^T, with LAPACK-style deflation and Gu-Eisenstat orthogonal eigenvectors;
Bccb : a block circulant matrix with circulant blocks (the matrix of a 2-D circular convolution), diagonalized by the 2-D DFT, with closed-form solves, eigendecomposition and SVD.
The operator types derive from EigenBase and store only compact generators or factors. The FFT-backed operators (Circulant, Toeplitz, Hankel and Bccb) also keep a precomputed DFT symbol that every product reuses. Because they expose operator* returning an Eigen product expression, they also plug directly into the matrix-free iterative solvers (ConjugateGradient, GMRES, MINRES, ...) without forming the dense matrix; and since they hook into the evaluator system, they can be assigned to a dense matrix when an explicit representation is needed. Like every matrix-free operator, they carry no coefficient storage the default preconditioners could read, so the iterative solvers must be instantiated with IdentityPreconditioner.
Every operator type except Vandermonde, whose transpose has no fast product, is closed under transposition (transpose(), conjugate(), adjoint() return operators of the same kind, the FFT-based ones reusing the cached symbol), which in particular feeds the least-squares solvers LSMR and LeastSquaresConjugateGradient (again with IdentityPreconditioner). Circulant and Bccb additionally expose their closed-form eigendecomposition and SVD in the Fourier basis, a pseudo-inverse (minimum-norm least-squares) solve, rank(), inverse() and determinant().
#include <contrib/Eigen/StructuredMatrices>
Applications
The worked examples apply these classes to problems from computational science, each program checking its result against a known solution or a general-purpose solver:
- partial differential equations on tensor-product grids, whose finite-difference operators are Kronecker sums of 1-D matrices [1]: the 2-D Poisson equation by fast diagonalization [2], the 3-D heat equation by implicit time stepping, convection-diffusion by the Bartels-Stewart algorithm [3], alternating-direction implicit time stepping [4], a non-separable potential with a fast Poisson preconditioner, and the screened Poisson equation on a torus through block circulant matrices [5], and Fourier spectral differentiation on a periodic grid [21] (
KroneckerSum, BartelsStewart, KroneckerOperator, KroneckerSparseView, Bccb, Circulant);
- matrix equations and spectra: the Lyapunov equation of a damped mass-spring chain [6], the 2-D quantum harmonic oscillator [7], and the bound state of a Koster-Slater impurity [8] by the secular equation [9], and the merge step of divide and conquer [25] for the symmetric tridiagonal eigenproblem (
KroneckerSum, DPR1EigenSolver);
- integral equations and Toeplitz systems: Love's integral equation of electrostatics [10] by look-ahead Levinson [11], and a large Toeplitz system by conjugate gradients with Strang's circulant preconditioner [12], [13] (
Toeplitz, LookAheadLevinson, Circulant);
- signal and image processing: deconvolution as a rectangular Toeplitz least-squares problem for LSMR [22], image deblurring with periodic boundaries by Tikhonov regularization [5], and Prony's method [23] for sums of exponentials (
Toeplitz, Bccb, Hankel, Vandermonde, BjorckPereyra);
- approximation: Padé approximants [14] through a Hankel solve, interpolatory quadrature weights [15] through the dual Björck-Pereyra solve [16], a discretized Cauchy integral [17] through the pivoted Cauchy factorization [18], polynomial least squares through the Hilbert matrix [26], and separable least squares on a grid through the Kronecker pseudo-inverse [27] (
Hankel, Vandermonde, BjorckPereyra, Cauchy, CauchyLU, KroneckerOperator);
- statistics and estimation: a Gaussian-process likelihood [19] with a low-rank Fourier-feature covariance [20], and a Kalman measurement update [24] through the Woodbury identity (
DiagonalPlusLowRank).
References
- R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations, SIAM, 2007.
- R. E. Lynch, J. R. Rice and D. H. Thomas, "Direct solution of partial
difference equations by tensor product methods", Numer. Math. 6 (1964), 185-199.
- R. H. Bartels and G. W. Stewart, "Solution of the matrix equation
AX + XB = C", Comm. ACM 15 (1972), 820-826.
- D. W. Peaceman and H. H. Rachford, "The numerical solution of parabolic
and elliptic differential equations", J. SIAM 3 (1955), 28-41.
- P. C. Hansen, J. G. Nagy and D. P. O'Leary, Deblurring Images: Matrices, Spectra, and Filtering, SIAM, 2006.
- V. Simoncini, "Computational methods for linear matrix equations", SIAM Rev. 58 (2016), 377-441.
- D. J. Griffiths, Introduction to Quantum Mechanics, 2nd ed., Pearson Prentice Hall, 2005.
- G. F. Koster and J. C. Slater, "Wave functions for impurity levels", Phys. Rev. 95 (1954), 1167-1176.
- M. Gu and S. C. Eisenstat, "A stable and efficient algorithm for the
rank-one modification of the symmetric eigenproblem", SIAM J. Matrix Anal. Appl. 15 (1994), 1266-1276.
- E. R. Love, "The electrostatic field of two equal circular co-axial
conducting disks", Quart. J. Mech. Appl. Math. 2 (1949), 428-451.
- T. F. Chan and P. C. Hansen, "A look-ahead Levinson algorithm for general
Toeplitz systems", IEEE Trans. Signal Process. 40 (1992), 1079-1090.
- G. Strang, "A proposal for Toeplitz matrix calculations", Stud. Appl. Math. 74 (1986), 171-176.
- R. H. Chan and M. K. Ng, "Conjugate gradient methods for Toeplitz
systems", SIAM Rev. 38 (1996), 427-482.
- G. A. Baker and P. Graves-Morris, Padé Approximants, 2nd ed., Cambridge University Press, 1996.
- C. W. Clenshaw and A. R. Curtis, "A method for numerical integration on
an automatic computer", Numer. Math. 2 (1960), 197-205.
- Å. Björck and V. Pereyra, "Solution of Vandermonde systems of
equations", Math. Comp. 24 (1970), 893-903.
- L. N. Trefethen and J. A. C. Weideman, "The exponentially convergent
trapezoidal rule", SIAM Rev. 56 (2014), 385-458.
- I. Gohberg, T. Kailath and V. Olshevsky, "Fast Gaussian elimination with
partial pivoting for matrices with displacement structure", Math. Comp. 64 (1995), 1557-1576.
- C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning, MIT Press, 2006.
- A. Rahimi and B. Recht, "Random features for large-scale kernel
machines", Advances in Neural Information Processing Systems 20 (2007).
- L. N. Trefethen, Spectral Methods in MATLAB, SIAM, 2000.
- D. C.-L. Fong and M. A. Saunders, "LSMR: An iterative algorithm for
sparse least-squares problems", SIAM J. Sci. Comput. 33 (2011), 2950-2971.
- G. R. de Prony, "Essai expérimental et analytique ...", J. de l'École Polytechnique 1 (1795), 24-76.
- R. E. Kalman, "A new approach to linear filtering and prediction
problems", J. Basic Eng. 82 (1960), 35-45.
- J. J. M. Cuppen, "A divide and conquer method for the symmetric
tridiagonal eigenproblem", Numer. Math. 36 (1981), 177-195.
- M.-D. Choi, "Tricks or treats with the Hilbert matrix", Amer. Math. Monthly 90 (1983), 301-312.
- C. F. Van Loan, "The ubiquitous Kronecker product", J. Comput. Appl. Math. 123 (2000), 85-100.
|
| class | Eigen::BartelsStewart< KroneckerSumType > |
| | Direct solver for Kronecker-sum systems \( (A_1 \oplus A_2 \oplus \cdots \oplus A_d)\,x = b \). More...
|
| |
| class | Eigen::Bccb< Scalar_, BlockSize_, NumBlocks_ > |
| | A block circulant matrix with circulant blocks (BCCB), the matrix of a two-dimensional circular convolution, represented by its n2 x n1 generating array. More...
|
| |
| class | Eigen::BjorckPereyra< Scalar_ > |
| | Björck-Pereyra O(n^2) solver for square Vandermonde systems. More...
|
| |
| class | Eigen::Cauchy< Scalar_, Rows_, Cols_ > |
| | An m x n Cauchy matrix represented by its two node vectors. More...
|
| |
| class | Eigen::CauchyLU< Scalar_ > |
| | Partially pivoted O(n^2) LU solver for square Cauchy systems (Gohberg-Kailath-Olshevsky). More...
|
| |
| class | Eigen::Circulant< Scalar_, Size_ > |
| | An n x n circulant matrix represented by its first column. More...
|
| |
| class | Eigen::DiagonalPlusLowRank< Scalar_, Size_, Rank_ > |
| | An n x n operator \( D + U V^H \): a diagonal matrix plus a rank-k correction, stored as its diagonal and the two n x k factors. More...
|
| |
| class | Eigen::DPR1EigenSolver< RealScalar_ > |
| | Direct O(n^2) eigensolver for real symmetric diagonal-plus-rank-one matrices \( A = D + \rho\, z z^T \), via the secular equation. More...
|
| |
| class | Eigen::Hankel< Scalar_, Rows_, Cols_ > |
| | An m x n Hankel matrix represented by its first column and last row. More...
|
| |
| class | Eigen::KroneckerOperator< LhsMatrix, RhsMatrix > |
| | The Kronecker product \( A \otimes B \) as an implicit operator that is never materialized. More...
|
| |
| class | Eigen::KroneckerSparseView< OperatorType, Options > |
| | A KroneckerOperator or KroneckerSum as a lazy sparse expression. More...
|
| |
| class | Eigen::KroneckerSum< LhsMatrix, RhsMatrix > |
| | The Kronecker sum \( A \oplus B = A \otimes I + I \otimes B \) of two square matrices as an implicit operator that is never materialized. More...
|
| |
| class | Eigen::LookAheadLevinson< Scalar_ > |
| | Look-ahead Levinson direct solver for general Toeplitz systems. More...
|
| |
| class | Eigen::Toeplitz< Scalar_, Rows_, Cols_ > |
| | An m x n Toeplitz matrix represented by its first column and row. More...
|
| |
| class | Eigen::Vandermonde< Scalar_, Rows_, Cols_ > |
| | An m x n Vandermonde matrix represented by its node vector. More...
|
| |
|
| template<typename Derived> |
| Bccb< typename Derived::Scalar, Derived::RowsAtCompileTime, Derived::ColsAtCompileTime > | Eigen::makeBccb (const MatrixBase< Derived > &generator) |
| |
| template<typename XDerived, typename YDerived> |
| Cauchy< typename XDerived::Scalar, XDerived::SizeAtCompileTime, YDerived::SizeAtCompileTime > | Eigen::makeCauchy (const MatrixBase< XDerived > &x, const MatrixBase< YDerived > &y) |
| |
| template<typename Derived> |
| Circulant< typename Derived::Scalar, Derived::SizeAtCompileTime > | Eigen::makeCirculant (const MatrixBase< Derived > &col) |
| |
| template<typename DDerived, typename UDerived, typename VDerived> |
| DiagonalPlusLowRank< typename DDerived::Scalar, DDerived::SizeAtCompileTime, UDerived::ColsAtCompileTime > | Eigen::makeDiagonalPlusLowRank (const MatrixBase< DDerived > &d, const MatrixBase< UDerived > &U, const MatrixBase< VDerived > &V) |
| |
| template<typename ColDerived, typename RowDerived> |
| Hankel< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > | Eigen::makeHankel (const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row) |
| |
| template<typename D1, typename D2, typename D3, typename... Rest> |
| auto | Eigen::makeKroneckerOperator (const EigenBase< D1 > &a, const EigenBase< D2 > &b, const EigenBase< D3 > &c, const Rest &... rest) |
| |
| template<typename LhsDerived, typename RhsDerived> |
| KroneckerOperator< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > | Eigen::makeKroneckerOperator (const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b) |
| |
| template<typename D1, typename D2, typename D3, typename... Rest> |
| auto | Eigen::makeKroneckerSum (const EigenBase< D1 > &a, const EigenBase< D2 > &b, const EigenBase< D3 > &c, const Rest &... rest) |
| |
| template<typename LhsDerived, typename RhsDerived> |
| KroneckerSum< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > | Eigen::makeKroneckerSum (const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b) |
| |
| template<typename ColDerived, typename RowDerived> |
| Toeplitz< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > | Eigen::makeToeplitz (const MatrixBase< ColDerived > &col, const MatrixBase< RowDerived > &row) |
| |
| template<typename Derived> |
| Vandermonde< typename Derived::Scalar, Derived::SizeAtCompileTime, Derived::SizeAtCompileTime > | Eigen::makeVandermonde (const MatrixBase< Derived > &nodes) |
| |
| template<typename Derived> |
| Vandermonde< typename Derived::Scalar, Derived::SizeAtCompileTime, Dynamic > | Eigen::makeVandermonde (const MatrixBase< Derived > &nodes, Index cols) |
| |
◆ makeBccb()
template<typename Derived>
| Bccb< typename Derived::Scalar, Derived::RowsAtCompileTime, Derived::ColsAtCompileTime > Eigen::makeBccb |
( |
const MatrixBase< Derived > & | generator | ) |
|
- Returns
- a Bccb operator with generating array generator. The compile-time dimensions of the operator are deduced from the array.
◆ makeCauchy()
template<typename XDerived, typename YDerived>
| Cauchy< typename XDerived::Scalar, XDerived::SizeAtCompileTime, YDerived::SizeAtCompileTime > Eigen::makeCauchy |
( |
const MatrixBase< XDerived > & | x, |
|
|
const MatrixBase< YDerived > & | y ) |
- Returns
- a Cauchy operator with row nodes x and column nodes y. The compile-time dimensions of the operator are deduced from the node vectors.
◆ makeCirculant()
template<typename Derived>
| Circulant< typename Derived::Scalar, Derived::SizeAtCompileTime > Eigen::makeCirculant |
( |
const MatrixBase< Derived > & | col | ) |
|
- Returns
- a Circulant operator with first column col. The compile-time size of the operator is deduced from col.
◆ makeDiagonalPlusLowRank()
template<typename DDerived, typename UDerived, typename VDerived>
- Returns
- a DiagonalPlusLowRank operator
diag(d) + U*V.adjoint(). The compile-time dimension and rank are deduced from the arguments.
◆ makeHankel()
template<typename ColDerived, typename RowDerived>
| Hankel< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > Eigen::makeHankel |
( |
const MatrixBase< ColDerived > & | col, |
|
|
const MatrixBase< RowDerived > & | row ) |
- Returns
- a Hankel operator with first column col and last row row. The compile-time dimensions of the operator are deduced from the generators.
◆ makeKroneckerOperator() [1/2]
template<typename D1, typename D2, typename D3, typename... Rest>
| auto Eigen::makeKroneckerOperator |
( |
const EigenBase< D1 > & | a, |
|
|
const EigenBase< D2 > & | b, |
|
|
const EigenBase< D3 > & | c, |
|
|
const Rest &... | rest ) |
- Returns
- the KroneckerOperator
a (x) b (x) c (x) ..., nested to the right: makeKroneckerOperator(a, makeKroneckerOperator(b, c, ...)).
◆ makeKroneckerOperator() [2/2]
template<typename LhsDerived, typename RhsDerived>
| KroneckerOperator< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > Eigen::makeKroneckerOperator |
( |
const EigenBase< LhsDerived > & | a, |
|
|
const EigenBase< RhsDerived > & | b ) |
- Returns
- a KroneckerOperator
a (x) b holding evaluated copies of the factors. The operator type is deduced from the types of a and b: a dense argument becomes a Matrix factor, a diagonal one an owning DiagonalMatrix, a sparse one a compressed SparseMatrix, an Identity() expression an identity factor holding its dimensions, and a KroneckerOperator is stored as it is, each exploited structurally, see KroneckerOperator.
◆ makeKroneckerSum() [1/2]
template<typename D1, typename D2, typename D3, typename... Rest>
- Returns
- the KroneckerSum
a (+) b (+) c (+) ..., nested to the right: makeKroneckerSum(a, makeKroneckerSum(b, c, ...)).
◆ makeKroneckerSum() [2/2]
template<typename LhsDerived, typename RhsDerived>
| KroneckerSum< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > Eigen::makeKroneckerSum |
( |
const EigenBase< LhsDerived > & | a, |
|
|
const EigenBase< RhsDerived > & | b ) |
◆ makeToeplitz()
template<typename ColDerived, typename RowDerived>
| Toeplitz< typename ColDerived::Scalar, ColDerived::SizeAtCompileTime, RowDerived::SizeAtCompileTime > Eigen::makeToeplitz |
( |
const MatrixBase< ColDerived > & | col, |
|
|
const MatrixBase< RowDerived > & | row ) |
- Returns
- a Toeplitz operator with first column col and first row row. The compile-time dimensions of the operator are deduced from the generators.
◆ makeVandermonde() [1/2]
template<typename Derived>
| Vandermonde< typename Derived::Scalar, Derived::SizeAtCompileTime, Derived::SizeAtCompileTime > Eigen::makeVandermonde |
( |
const MatrixBase< Derived > & | nodes | ) |
|
- Returns
- the square Vandermonde operator of the nodes nodes.
◆ makeVandermonde() [2/2]
template<typename Derived>
| Vandermonde< typename Derived::Scalar, Derived::SizeAtCompileTime, Dynamic > Eigen::makeVandermonde |
( |
const MatrixBase< Derived > & | nodes, |
|
|
Index | cols ) |
- Returns
- an
m x cols Vandermonde operator with node vector nodes; the compile-time row count is deduced from nodes.