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

Detailed Description

This module provides lightweight operator types for displacement-structured matrices together with fast matrix-vector products and direct solvers:

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:

References

  1. R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations, SIAM, 2007.
  2. 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.
  3. R. H. Bartels and G. W. Stewart, "Solution of the matrix equation AX + XB = C", Comm. ACM 15 (1972), 820-826.
  4. D. W. Peaceman and H. H. Rachford, "The numerical solution of parabolic and elliptic differential equations", J. SIAM 3 (1955), 28-41.
  5. P. C. Hansen, J. G. Nagy and D. P. O'Leary, Deblurring Images: Matrices, Spectra, and Filtering, SIAM, 2006.
  6. V. Simoncini, "Computational methods for linear matrix equations", SIAM Rev. 58 (2016), 377-441.
  7. D. J. Griffiths, Introduction to Quantum Mechanics, 2nd ed., Pearson Prentice Hall, 2005.
  8. G. F. Koster and J. C. Slater, "Wave functions for impurity levels", Phys. Rev. 95 (1954), 1167-1176.
  9. 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.
  10. E. R. Love, "The electrostatic field of two equal circular co-axial conducting disks", Quart. J. Mech. Appl. Math. 2 (1949), 428-451.
  11. T. F. Chan and P. C. Hansen, "A look-ahead Levinson algorithm for general Toeplitz systems", IEEE Trans. Signal Process. 40 (1992), 1079-1090.
  12. G. Strang, "A proposal for Toeplitz matrix calculations", Stud. Appl. Math. 74 (1986), 171-176.
  13. R. H. Chan and M. K. Ng, "Conjugate gradient methods for Toeplitz systems", SIAM Rev. 38 (1996), 427-482.
  14. G. A. Baker and P. Graves-Morris, Padé Approximants, 2nd ed., Cambridge University Press, 1996.
  15. C. W. Clenshaw and A. R. Curtis, "A method for numerical integration on an automatic computer", Numer. Math. 2 (1960), 197-205.
  16. Å. Björck and V. Pereyra, "Solution of Vandermonde systems of equations", Math. Comp. 24 (1970), 893-903.
  17. L. N. Trefethen and J. A. C. Weideman, "The exponentially convergent trapezoidal rule", SIAM Rev. 56 (2014), 385-458.
  18. I. Gohberg, T. Kailath and V. Olshevsky, "Fast Gaussian elimination with partial pivoting for matrices with displacement structure", Math. Comp. 64 (1995), 1557-1576.
  19. C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning, MIT Press, 2006.
  20. A. Rahimi and B. Recht, "Random features for large-scale kernel machines", Advances in Neural Information Processing Systems 20 (2007).
  21. L. N. Trefethen, Spectral Methods in MATLAB, SIAM, 2000.
  22. 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.
  23. G. R. de Prony, "Essai expérimental et analytique ...", J. de l'École Polytechnique 1 (1795), 24-76.
  24. R. E. Kalman, "A new approach to linear filtering and prediction problems", J. Basic Eng. 82 (1960), 35-45.
  25. J. J. M. Cuppen, "A divide and conquer method for the symmetric tridiagonal eigenproblem", Numer. Math. 36 (1981), 177-195.
  26. M.-D. Choi, "Tricks or treats with the Hilbert matrix", Amer. Math. Monthly 90 (1983), 301-312.
  27. C. F. Van Loan, "The ubiquitous Kronecker product", J. Comput. Appl. Math. 123 (2000), 85-100.

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

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.