StructuredMatrices module

Detailed Description

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;
• 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;
• 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.

All operator types are 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). The Circulant, Toeplitz and Hankel operators are closed under transposition (transpose(), conjugate(), adjoint() return operators of the same kind, 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>

Classes
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::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...

Functions
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)

Function Documentation

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>

DiagonalPlusLowRank< typename DDerived::Scalar, DDerived::SizeAtCompileTime, UDerived::ColsAtCompileTime > Eigen::makeDiagonalPlusLowRank	(	const MatrixBase< DDerived > &	d,
		const MatrixBase< UDerived > &	U,
		const MatrixBase< VDerived > &	V )

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>

auto Eigen::makeKroneckerSum	(	const EigenBase< D1 > &	a,
		const EigenBase< D2 > &	b,
		const EigenBase< D3 > &	c,
		const Rest &...	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 )

Returns

the KroneckerSum a (+) b, with the factor types deduced as for makeKroneckerOperator().

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.