StructuredMatrices: Worked examples from PDEs, signal processing, approximation, statistics and physics libeigen/eigen!3287 Co-authored-by: Rasmus Munk Larsen <rmlarsen@gmail.com>
diff --git a/contrib/Eigen/StructuredMatrices b/contrib/Eigen/StructuredMatrices index 1ac02b9..6a52b7d 100644 --- a/contrib/Eigen/StructuredMatrices +++ b/contrib/Eigen/StructuredMatrices
@@ -90,6 +90,131 @@ * \code * #include <contrib/Eigen/StructuredMatrices> * \endcode + * + * \section StructuredMatricesApplications Applications + * + * The \ref StructuredMatricesExamples "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 + * \ref StructuredExamplePoisson2D "2-D Poisson equation" by fast + * diagonalization [2], the + * \ref StructuredExampleHeat3D "3-D heat equation" by implicit time + * stepping, \ref StructuredExampleConvectionDiffusion "convection-diffusion" + * by the Bartels-Stewart algorithm [3], + * \ref StructuredExampleADI "alternating-direction implicit time stepping" [4], + * a \ref StructuredExamplePreconditioner "non-separable potential" with a + * fast Poisson preconditioner, and the + * \ref StructuredExampleTorusHelmholtz "screened Poisson equation on a torus" + * through block circulant matrices [5], and + * \ref StructuredExampleSpectralDifferentiation "Fourier spectral differentiation" + * on a periodic grid [21] + * (\c KroneckerSum, \c BartelsStewart, \c KroneckerOperator, + * \c KroneckerSparseView, \c Bccb, \c Circulant); + * - matrix equations and spectra: the + * \ref StructuredExampleLyapunov "Lyapunov equation" of a damped + * mass-spring chain [6], the + * \ref StructuredExampleHarmonicOscillator "2-D quantum harmonic oscillator" [7], + * and the bound state of a + * \ref StructuredExampleImpurity "Koster-Slater impurity" [8] by the + * secular equation [9], and the + * \ref StructuredExampleDivideAndConquer "merge step of divide and conquer" [25] + * for the symmetric tridiagonal eigenproblem (\c KroneckerSum, + * \c DPR1EigenSolver); + * - integral equations and Toeplitz systems: + * \ref StructuredExampleLoveEquation "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] (\c Toeplitz, \c LookAheadLevinson, \c Circulant); + * - signal and image processing: + * \ref StructuredExampleDeconvolution "deconvolution" as a rectangular + * Toeplitz least-squares problem for LSMR [22], + * \ref StructuredExampleDeblurring "image deblurring" with periodic + * boundaries by Tikhonov regularization [5], and + * \ref StructuredExampleProny "Prony's method" [23] for sums of + * exponentials (\c Toeplitz, \c Bccb, \c Hankel, \c Vandermonde, + * \c BjorckPereyra); + * - approximation: \ref StructuredExamplePade "Padé approximants" [14] + * through a Hankel solve, + * \ref StructuredExampleQuadrature "interpolatory quadrature weights" [15] + * through the dual Björck-Pereyra solve [16], a + * \ref StructuredExampleRationalApproximation "discretized Cauchy integral" [17] + * through the pivoted Cauchy factorization [18], + * \ref StructuredExamplePolynomialFit "polynomial least squares" through + * the Hilbert matrix [26], and + * \ref StructuredExampleSeparableLeastSquares "separable least squares" + * on a grid through the Kronecker pseudo-inverse [27] (\c Hankel, + * \c Vandermonde, \c BjorckPereyra, \c Cauchy, \c CauchyLU, + * \c KroneckerOperator); + * - statistics and estimation: a + * \ref StructuredExampleGaussianProcess "Gaussian-process likelihood" [19] + * with a low-rank Fourier-feature covariance [20], and a + * \ref StructuredExampleKalmanUpdate "Kalman measurement update" [24] + * through the Woodbury identity (\c DiagonalPlusLowRank). + * + * \section StructuredMatricesReferences References + * + * -# R. J. LeVeque, <em>Finite Difference Methods for Ordinary and Partial + * Differential Equations</em>, SIAM, 2007. + * -# R. E. Lynch, J. R. Rice and D. H. Thomas, "Direct solution of partial + * difference equations by tensor product methods", <em>Numer. Math.</em> + * 6 (1964), 185-199. + * -# R. H. Bartels and G. W. Stewart, "Solution of the matrix equation + * AX + XB = C", <em>Comm. ACM</em> 15 (1972), 820-826. + * -# D. W. Peaceman and H. H. Rachford, "The numerical solution of parabolic + * and elliptic differential equations", <em>J. SIAM</em> 3 (1955), 28-41. + * -# P. C. Hansen, J. G. Nagy and D. P. O'Leary, <em>Deblurring Images: + * Matrices, Spectra, and Filtering</em>, SIAM, 2006. + * -# V. Simoncini, "Computational methods for linear matrix equations", + * <em>SIAM Rev.</em> 58 (2016), 377-441. + * -# D. J. Griffiths, <em>Introduction to Quantum Mechanics</em>, 2nd ed., + * Pearson Prentice Hall, 2005. + * -# G. F. Koster and J. C. Slater, "Wave functions for impurity levels", + * <em>Phys. Rev.</em> 95 (1954), 1167-1176. + * -# M. Gu and S. C. Eisenstat, "A stable and efficient algorithm for the + * rank-one modification of the symmetric eigenproblem", + * <em>SIAM J. Matrix Anal. Appl.</em> 15 (1994), 1266-1276. + * -# E. R. Love, "The electrostatic field of two equal circular co-axial + * conducting disks", <em>Quart. J. Mech. Appl. Math.</em> 2 (1949), + * 428-451. + * -# T. F. Chan and P. C. Hansen, "A look-ahead Levinson algorithm for general + * Toeplitz systems", <em>IEEE Trans. Signal Process.</em> 40 (1992), + * 1079-1090. + * -# G. Strang, "A proposal for Toeplitz matrix calculations", + * <em>Stud. Appl. Math.</em> 74 (1986), 171-176. + * -# R. H. Chan and M. K. Ng, "Conjugate gradient methods for Toeplitz + * systems", <em>SIAM Rev.</em> 38 (1996), 427-482. + * -# G. A. Baker and P. Graves-Morris, <em>Padé Approximants</em>, 2nd ed., + * Cambridge University Press, 1996. + * -# C. W. Clenshaw and A. R. Curtis, "A method for numerical integration on + * an automatic computer", <em>Numer. Math.</em> 2 (1960), 197-205. + * -# Å. Björck and V. Pereyra, "Solution of Vandermonde systems of + * equations", <em>Math. Comp.</em> 24 (1970), 893-903. + * -# L. N. Trefethen and J. A. C. Weideman, "The exponentially convergent + * trapezoidal rule", <em>SIAM Rev.</em> 56 (2014), 385-458. + * -# I. Gohberg, T. Kailath and V. Olshevsky, "Fast Gaussian elimination with + * partial pivoting for matrices with displacement structure", + * <em>Math. Comp.</em> 64 (1995), 1557-1576. + * -# C. E. Rasmussen and C. K. I. Williams, <em>Gaussian Processes for + * Machine Learning</em>, MIT Press, 2006. + * -# A. Rahimi and B. Recht, "Random features for large-scale kernel + * machines", <em>Advances in Neural Information Processing Systems</em> 20 + * (2007). + * -# L. N. Trefethen, <em>Spectral Methods in MATLAB</em>, SIAM, 2000. + * -# D. C.-L. Fong and M. A. Saunders, "LSMR: An iterative algorithm for + * sparse least-squares problems", <em>SIAM J. Sci. Comput.</em> 33 (2011), + * 2950-2971. + * -# G. R. de Prony, "Essai expérimental et analytique ...", + * <em>J. de l'École Polytechnique</em> 1 (1795), 24-76. + * -# R. E. Kalman, "A new approach to linear filtering and prediction + * problems", <em>J. Basic Eng.</em> 82 (1960), 35-45. + * -# J. J. M. Cuppen, "A divide and conquer method for the symmetric + * tridiagonal eigenproblem", <em>Numer. Math.</em> 36 (1981), 177-195. + * -# M.-D. Choi, "Tricks or treats with the Hilbert matrix", + * <em>Amer. Math. Monthly</em> 90 (1983), 301-312. + * -# C. F. Van Loan, "The ubiquitous Kronecker product", + * <em>J. Comput. Appl. Math.</em> 123 (2000), 85-100. */ } // namespace Eigen
diff --git a/contrib/Eigen/src/StructuredMatrices/Bccb.h b/contrib/Eigen/src/StructuredMatrices/Bccb.h index a95eb31..f2e228c 100644 --- a/contrib/Eigen/src/StructuredMatrices/Bccb.h +++ b/contrib/Eigen/src/StructuredMatrices/Bccb.h
@@ -120,6 +120,10 @@ * \tparam NumBlocks_ the number of blocks \c n1 at compile time, or \c Dynamic * (the default). * + * \par Examples + * \ref StructuredExampleTorusHelmholtz "the screened Poisson equation on a torus", + * \ref StructuredExampleDeblurring "image deblurring". + * * \sa class Circulant, makeBccb() */ template <typename Scalar_, int BlockSize_, int NumBlocks_>
diff --git a/contrib/Eigen/src/StructuredMatrices/Cauchy.h b/contrib/Eigen/src/StructuredMatrices/Cauchy.h index f6f5019..f1e3e62 100644 --- a/contrib/Eigen/src/StructuredMatrices/Cauchy.h +++ b/contrib/Eigen/src/StructuredMatrices/Cauchy.h
@@ -104,6 +104,10 @@ * \tparam Rows_ the number of rows at compile time, or \c Dynamic (the default). * \tparam Cols_ the number of columns at compile time, or \c Dynamic (the default). * + * \par Examples + * \ref StructuredExampleRationalApproximation "a discretized Cauchy integral", + * \ref StructuredExamplePolynomialFit "polynomial least squares". + * * \sa class CauchyLU, makeCauchy() */ template <typename Scalar_, int Rows_, int Cols_> @@ -319,6 +323,10 @@ * * \tparam Scalar_ the scalar type, real or complex. * + * \par Examples + * \ref StructuredExampleRationalApproximation "a discretized Cauchy integral", + * \ref StructuredExamplePolynomialFit "polynomial least squares". + * * \sa class Cauchy */ template <typename Scalar_>
diff --git a/contrib/Eigen/src/StructuredMatrices/Circulant.h b/contrib/Eigen/src/StructuredMatrices/Circulant.h index e078899..43ab2d1 100644 --- a/contrib/Eigen/src/StructuredMatrices/Circulant.h +++ b/contrib/Eigen/src/StructuredMatrices/Circulant.h
@@ -92,6 +92,11 @@ * \tparam Scalar_ the scalar type, real or complex. * \tparam Size_ the dimension at compile time, or \c Dynamic (the default). * + * \par Examples + * \ref StructuredExampleLoveEquation "Love's integral equation and a preconditioned Toeplitz system", + * \ref StructuredExampleTorusHelmholtz "the screened Poisson equation on a torus", + * \ref StructuredExampleSpectralDifferentiation "Fourier spectral differentiation". + * * \sa class Toeplitz, makeCirculant() */ template <typename Scalar_, int Size_>
diff --git a/contrib/Eigen/src/StructuredMatrices/DPR1EigenSolver.h b/contrib/Eigen/src/StructuredMatrices/DPR1EigenSolver.h index daa1b43..27069bb 100644 --- a/contrib/Eigen/src/StructuredMatrices/DPR1EigenSolver.h +++ b/contrib/Eigen/src/StructuredMatrices/DPR1EigenSolver.h
@@ -68,6 +68,10 @@ * Scaling by a power of two is exact, the property the problem scaling * relies on. * + * \par Examples + * \ref StructuredExampleImpurity "an impurity bound state", + * \ref StructuredExampleDivideAndConquer "the merge step of divide and conquer". + * * \sa class SelfAdjointEigenSolver */ template <typename RealScalar_>
diff --git a/contrib/Eigen/src/StructuredMatrices/DiagonalPlusLowRank.h b/contrib/Eigen/src/StructuredMatrices/DiagonalPlusLowRank.h index c8b45d3..12461fc 100644 --- a/contrib/Eigen/src/StructuredMatrices/DiagonalPlusLowRank.h +++ b/contrib/Eigen/src/StructuredMatrices/DiagonalPlusLowRank.h
@@ -143,6 +143,10 @@ * \tparam Size_ the dimension at compile time, or \c Dynamic (the default). * \tparam Rank_ the correction rank at compile time, or \c Dynamic (the default). * + * \par Examples + * \ref StructuredExampleGaussianProcess "a Gaussian-process likelihood", + * \ref StructuredExampleKalmanUpdate "a Kalman measurement update". + * * \sa makeDiagonalPlusLowRank() */ template <typename Scalar_, int Size_, int Rank_>
diff --git a/contrib/Eigen/src/StructuredMatrices/Hankel.h b/contrib/Eigen/src/StructuredMatrices/Hankel.h index 38a8b2f..9162150 100644 --- a/contrib/Eigen/src/StructuredMatrices/Hankel.h +++ b/contrib/Eigen/src/StructuredMatrices/Hankel.h
@@ -92,6 +92,10 @@ * \tparam Rows_ the number of rows at compile time, or \c Dynamic (the default). * \tparam Cols_ the number of columns at compile time, or \c Dynamic (the default). * + * \par Examples + * \ref StructuredExamplePade "Pade approximation", + * \ref StructuredExampleProny "Prony's method". + * * \sa class Toeplitz, class Circulant, makeHankel() */ template <typename Scalar_, int Rows_, int Cols_>
diff --git a/contrib/Eigen/src/StructuredMatrices/KroneckerOperator.h b/contrib/Eigen/src/StructuredMatrices/KroneckerOperator.h index 1a937e7..2da2b3e 100644 --- a/contrib/Eigen/src/StructuredMatrices/KroneckerOperator.h +++ b/contrib/Eigen/src/StructuredMatrices/KroneckerOperator.h
@@ -906,6 +906,10 @@ * \tparam RhsMatrix the type of the right factor \c B, under the same * convention; its scalar type must match that of \c LhsMatrix. * + * \par Examples + * \ref StructuredExampleADI "ADI time stepping", + * \ref StructuredExampleSeparableLeastSquares "separable least squares". + * * \sa makeKroneckerOperator(), class Circulant, class Toeplitz */ template <typename LhsMatrix, typename RhsMatrix>
diff --git a/contrib/Eigen/src/StructuredMatrices/KroneckerSparseView.h b/contrib/Eigen/src/StructuredMatrices/KroneckerSparseView.h index 1d583b3..cdc6366 100644 --- a/contrib/Eigen/src/StructuredMatrices/KroneckerSparseView.h +++ b/contrib/Eigen/src/StructuredMatrices/KroneckerSparseView.h
@@ -333,6 +333,9 @@ * \tparam OperatorType the \ref KroneckerOperator or \ref KroneckerSum type. * \tparam Options \c ColMajor or \c RowMajor, the storage order of the view. * + * \par Examples + * \ref StructuredExamplePreconditioner "a non-separable potential". + * * \sa KroneckerOperator::sparseView(), KroneckerSum::sparseView() */ template <typename OperatorType, int Options>
diff --git a/contrib/Eigen/src/StructuredMatrices/KroneckerSum.h b/contrib/Eigen/src/StructuredMatrices/KroneckerSum.h index 9302981..1375979 100644 --- a/contrib/Eigen/src/StructuredMatrices/KroneckerSum.h +++ b/contrib/Eigen/src/StructuredMatrices/KroneckerSum.h
@@ -228,6 +228,15 @@ * \tparam RhsMatrix the type of the right factor \c B, under the same * convention; its scalar type must match that of \c LhsMatrix. * + * \par Examples + * \ref StructuredExamplePoisson2D "the 2-D Poisson equation", + * \ref StructuredExampleHeat3D "the 3-D heat equation", + * \ref StructuredExampleConvectionDiffusion "convection-diffusion", + * \ref StructuredExamplePreconditioner "a non-separable potential", + * \ref StructuredExampleTorusHelmholtz "the screened Poisson equation on a torus", + * \ref StructuredExampleLyapunov "the Lyapunov equation", + * \ref StructuredExampleHarmonicOscillator "the 2-D quantum harmonic oscillator". + * * \sa makeKroneckerSum(), class BartelsStewart, class KroneckerOperator */ template <typename LhsMatrix, typename RhsMatrix> @@ -556,6 +565,13 @@ * * \tparam KroneckerSumType the \ref KroneckerSum type to solve with. * + * \par Examples + * \ref StructuredExamplePoisson2D "the 2-D Poisson equation", + * \ref StructuredExampleHeat3D "the 3-D heat equation", + * \ref StructuredExampleConvectionDiffusion "convection-diffusion", + * \ref StructuredExamplePreconditioner "a non-separable potential", + * \ref StructuredExampleLyapunov "the Lyapunov equation". + * * \sa class KroneckerSum */ template <typename KroneckerSumType>
diff --git a/contrib/Eigen/src/StructuredMatrices/LookAheadLevinson.h b/contrib/Eigen/src/StructuredMatrices/LookAheadLevinson.h index f37c4c8..d122a9d 100644 --- a/contrib/Eigen/src/StructuredMatrices/LookAheadLevinson.h +++ b/contrib/Eigen/src/StructuredMatrices/LookAheadLevinson.h
@@ -78,6 +78,9 @@ * - T. F. Chan and P. C. Hansen, "A look-ahead Levinson algorithm for indefinite * Toeplitz systems," SIAM J. Matrix Anal. Appl., 13(2):490-506, 1992. * + * \par Examples + * \ref StructuredExampleLoveEquation "Love's integral equation and a preconditioned Toeplitz system". + * * \sa class Toeplitz */ template <typename Scalar_>
diff --git a/contrib/Eigen/src/StructuredMatrices/Toeplitz.h b/contrib/Eigen/src/StructuredMatrices/Toeplitz.h index 235912d..a056ce6 100644 --- a/contrib/Eigen/src/StructuredMatrices/Toeplitz.h +++ b/contrib/Eigen/src/StructuredMatrices/Toeplitz.h
@@ -75,6 +75,10 @@ * \tparam Rows_ the number of rows at compile time, or \c Dynamic (the default). * \tparam Cols_ the number of columns at compile time, or \c Dynamic (the default). * + * \par Examples + * \ref StructuredExampleLoveEquation "Love's integral equation and a preconditioned Toeplitz system", + * \ref StructuredExampleDeconvolution "deconvolution by Toeplitz least squares". + * * \sa class Circulant, makeToeplitz() */ template <typename Scalar_, int Rows_, int Cols_>
diff --git a/contrib/Eigen/src/StructuredMatrices/Vandermonde.h b/contrib/Eigen/src/StructuredMatrices/Vandermonde.h index 40d011c..701cbbb 100644 --- a/contrib/Eigen/src/StructuredMatrices/Vandermonde.h +++ b/contrib/Eigen/src/StructuredMatrices/Vandermonde.h
@@ -152,6 +152,12 @@ * \tparam Rows_ the number of rows (nodes) at compile time, or \c Dynamic. * \tparam Cols_ the number of columns (powers) at compile time, or \c Dynamic. * + * \par Examples + * \ref StructuredExampleQuadrature "interpolatory quadrature", + * \ref StructuredExampleProny "Prony's method", + * \ref StructuredExamplePolynomialFit "polynomial least squares", + * \ref StructuredExampleSeparableLeastSquares "separable least squares". + * * \sa class BjorckPereyra, makeVandermonde() */ template <typename Scalar_, int Rows_, int Cols_> @@ -387,6 +393,10 @@ * Eigen's scalar math hooks, including \c isfinite (and \c abs and \c log for * complex node ordering). Integer types are rejected. * + * \par Examples + * \ref StructuredExampleQuadrature "interpolatory quadrature", + * \ref StructuredExampleProny "Prony's method". + * * \sa class Vandermonde */ template <typename Scalar_>
diff --git a/contrib/doc/Overview.dox b/contrib/doc/Overview.dox index 14228d1..c1e7253 100644 --- a/contrib/doc/Overview.dox +++ b/contrib/doc/Overview.dox
@@ -13,6 +13,8 @@ \subpage AutoDiffExamples "AutoDiff examples" + \subpage StructuredMatricesExamples "StructuredMatrices examples" + \subpage SYCL_EIGEN "SYCL backend for Eigen" */
diff --git a/contrib/doc/StructuredMatrices.dox b/contrib/doc/StructuredMatrices.dox new file mode 100644 index 0000000..7acffe0 --- /dev/null +++ b/contrib/doc/StructuredMatrices.dox
@@ -0,0 +1,371 @@ +namespace Eigen { + +/** \page StructuredMatricesExamples StructuredMatrices examples + +These programs solve problems from numerical PDEs, integral equations, signal and image processing, approximation +theory, statistics, control and quantum mechanics with the \ref 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 +\ref StructuredMatricesReferences "references". + +\tableofcontents + +\section StructuredExamplesGrids Separable operators on tensor-product grids + +Finite differences on a tensor-product grid give Kronecker sums of 1-D matrices: with grid values stored with x as the +fast index, the 2-D Laplacian is \f$ D_y \oplus D_x = D_y \otimes I + I \otimes D_x \f$. \ref KroneckerSum applies +such operators without forming them, and \ref BartelsStewart solves them through the Schur forms or +eigendecompositions of the 1-D factors. LeVeque [1] covers the discretizations. + +\subsection StructuredExamplePoisson2D The 2-D Poisson equation + +The fast Poisson solver: two \f$ n \times n \f$ eigendecompositions instead of a factorization of the +\f$ n^2 \times n^2 \f$ matrix, with the second-order convergence of the discretization: the fast diagonalization +method of Lynch, Rice and Thomas [2]. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredPoisson2D.cpp +</td> +<td> +\verbinclude StructuredPoisson2D.out +</td></tr></table> + +\subsection StructuredExampleHeat3D Implicit time stepping of the 3-D heat equation + +The decompositions are computed once and reused at every step. A shift such as the identity of +\f$ I + \tau L \f$ goes into one factor, since \f$ I \otimes I \otimes I = I \f$. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredHeat3D.cpp +</td> +<td> +\verbinclude StructuredHeat3D.out +</td></tr></table> + +\subsection StructuredExampleConvectionDiffusion Convection-diffusion + +Nonsymmetric 1-D operators take the Schur-form path of \ref BartelsStewart, the algorithm of Bartels and Stewart [3]; +the solution agrees with \c SparseLU on the assembled matrix. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredConvectionDiffusion.cpp +</td> +<td> +\verbinclude StructuredConvectionDiffusion.out +</td></tr></table> + +\subsection StructuredExampleADI Alternating-direction implicit time stepping + +The Peaceman-Rachford ADI method [4] treats one direction at a time. Each half step is a \ref KroneckerOperator with an +\c Identity() factor, which costs nothing: the product is a sparse product with the 1-D matrix and the solve one +\c SparseLU of a tridiagonal matrix. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredADI.cpp +</td> +<td> +\verbinclude StructuredADI.out +</td></tr></table> + +\subsection StructuredExamplePreconditioner A non-separable potential + +When a term breaks the separable structure, the separable part still helps twice: \ref KroneckerSparseView +assembles the sparse matrix in one expression, and the fast Poisson solver preconditions conjugate gradients. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredPreconditioner.cpp +</td> +<td> +\verbinclude StructuredPreconditioner.out +</td></tr></table> + +\subsection StructuredExampleTorusHelmholtz Periodic boundaries: the screened Poisson equation on a torus + +With periodic boundaries the five-point stencil is a block circulant with circulant blocks, solved by \ref 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. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredTorusHelmholtz.cpp +</td> +<td> +\verbinclude StructuredTorusHelmholtz.out +</td></tr></table> + +\subsection StructuredExampleSpectralDifferentiation Fourier spectral differentiation + +On a periodic grid the spectral differentiation matrices are circulants [21], and their spectra are the wavenumbers: +\ref Circulant::eigenvalues returns \f$ ik \f$, \ref Circulant::rank counts the \f$ N - 2 \f$ nonzero ones (the +constant and the sawtooth mode are annihilated), and the pseudo-inverse \ref Circulant::solve integrates a periodic +function with zero mean. Derivatives and the periodic boundary value problem \f$ u'' - u = f \f$ converge +geometrically for smooth \f$ u \f$. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredSpectralDifferentiation.cpp +</td> +<td> +\verbinclude StructuredSpectralDifferentiation.out +</td></tr></table> + +\section StructuredExamplesSpectra Matrix equations and spectra + +\subsection StructuredExampleLyapunov The Lyapunov equation of a mass-spring chain + +\f$ A X + X A^T = C \f$ is \f$ (A \oplus A)\,\mathrm{vec}(X) = \mathrm{vec}(C) \f$, and the Sylvester equation +\f$ A X + X B = C \f$ is \f$ (B^T \oplus A)\,\mathrm{vec}(X) = \mathrm{vec}(C) \f$. 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. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredLyapunov.cpp +</td> +<td> +\verbinclude StructuredLyapunov.out +</td></tr></table> + +\subsection StructuredExampleHarmonicOscillator The 2-D quantum harmonic oscillator + +A separable Hamiltonian \f$ H_x \oplus H_y \f$ has the pairwise sums of the 1-D energies as its spectrum, which +\ref KroneckerSum::eigenvalues returns without forming the 2-D matrix [7]. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredHarmonicOscillator.cpp +</td> +<td> +\verbinclude StructuredHarmonicOscillator.out +</td></tr></table> + +\subsection StructuredExampleImpurity An impurity bound state + +A localized perturbation of a diagonal band Hamiltonian is a rank-one update, the Koster-Slater model [8]. \ref DPR1EigenSolver finds the whole +spectrum in \f$ O(N^2) \f$ from the secular equation [9], including the bound state that splits off below the band. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredImpurity.cpp +</td> +<td> +\verbinclude StructuredImpurity.out +</td></tr></table> + +\subsection StructuredExampleDivideAndConquer The merge step of divide and conquer + +Cuppen's method [25] tears a symmetric tridiagonal matrix into two halves plus a rank-one coupling; after the halves +are diagonalized, what remains is the diagonal-plus-rank-one eigenproblem that \ref 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 \c SelfAdjointEigenSolver. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredDivideAndConquer.cpp +</td> +<td> +\verbinclude StructuredDivideAndConquer.out +</td></tr></table> + +\section StructuredExamplesToeplitz Toeplitz, circulant and Hankel systems + +\subsection StructuredExampleLoveEquation Love's integral equation and a preconditioned Toeplitz system + +A translation-invariant kernel discretized on a uniform grid gives a \ref Toeplitz matrix. Love's equation [10] is solved +directly by \ref LookAheadLevinson [11] in \f$ O(n^2) \f$. For large systems, conjugate gradients use the FFT-based +Toeplitz product and Strang's \ref Circulant preconditioner [12], [13], \f$ O(n \log n) \f$ per iteration. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredLoveEquation.cpp +</td> +<td> +\verbinclude StructuredLoveEquation.out +</td></tr></table> + +\subsection StructuredExamplePade Pade approximation + +The denominator of a Pade approximant [14] solves a \ref Hankel system in the Taylor coefficients, solved in +\f$ O(n^2) \f$ through its Toeplitz equivalent. Rescaling the variable equilibrates the coefficients and keeps the +system Hankel. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredPade.cpp +</td> +<td> +\verbinclude StructuredPade.out +</td></tr></table> + +\section StructuredExamplesSignals Signal and image processing + +\subsection StructuredExampleDeconvolution Deconvolution by Toeplitz least squares + +The full convolution of a signal with a kernel is a rectangular \ref Toeplitz matrix. \c LSMR [22] solves the +least-squares problem without forming it: products with the matrix and, through \ref Toeplitz::adjoint, its transpose +cost \f$ O(p \log p) \f$ each by circulant embedding [13]. The matrix-free solution agrees with the dense QR of the +materialized matrix. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredDeconvolution.cpp +</td> +<td> +\verbinclude StructuredDeconvolution.out +</td></tr></table> + +\subsection StructuredExampleDeblurring Image deblurring with periodic boundaries + +A blur with periodic boundary conditions is a \ref Bccb matrix [5]. A motion blur annihilates whole frequency lines, +which \ref Bccb::rank counts exactly, so the pseudo-inverse \ref Bccb::solve cannot undo it and amplifies the noise +next to those lines. Tikhonov regularization stays within the class: \f$ A^H A + \lambda I \f$ is the Bccb generated by +the autocorrelation of the point spread function, computed with two products, and each \f$ \lambda \f$ costs one +\f$ O(N \log N) \f$ solve. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredDeblurring.cpp +</td> +<td> +\verbinclude StructuredDeblurring.out +</td></tr></table> + +\subsection StructuredExampleProny Prony's method + +A sum of exponentials obeys a linear recurrence whose coefficients solve a \ref Hankel system in the samples [23]; the +roots of its characteristic polynomial are the damping rates and frequencies, and the amplitudes solve the dual +\ref Vandermonde system with complex nodes, which \ref BjorckPereyra handles in Leja order. The recurrence residual +over all samples is a rectangular Hankel product. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredProny.cpp +</td> +<td> +\verbinclude StructuredProny.out +</td></tr></table> + +\section StructuredExamplesApproximation Interpolation and approximation + +\subsection StructuredExampleQuadrature Interpolatory quadrature + +The weights of an interpolatory quadrature rule solve the transposed \ref Vandermonde system, the dual problem that +\ref BjorckPereyra [16] solves in \f$ O(n^2) \f$; on Chebyshev extreme points they are the Clenshaw-Curtis weights +[15]. The primal solve gives interpolation coefficients. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredQuadrature.cpp +</td> +<td> +\verbinclude StructuredQuadrature.out +</td></tr></table> + +\subsection StructuredExampleRationalApproximation A discretized Cauchy integral + +Representing an analytic function by point charges outside its domain leads to a \ref Cauchy system, factored with +pivoting in \f$ O(n^2) \f$ by \ref CauchyLU [18]; the error decays geometrically, as for the trapezoidal rule on a +circle [17]. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredRationalApproximation.cpp +</td> +<td> +\verbinclude StructuredRationalApproximation.out +</td></tr></table> + +\subsection StructuredExamplePolynomialFit Polynomial least squares and the Hilbert matrix + +The normal equations of continuous least-squares approximation in the monomial basis have the Hilbert matrix, a +\ref Cauchy matrix [26]: \ref CauchyLU solves them in \f$ O(n^2) \f$ and \ref Cauchy::determinant gives +\f$ \det H_n \f$ in closed form where dense LU loses digits. The fitted polynomial is far less sensitive to +\f$ \kappa(H_n) \f$ than its coefficients, and matches the discrete fit by a dense QR of the rectangular +\ref Vandermonde matrix; Vandermonde products evaluate both. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredPolynomialFit.cpp +</td> +<td> +\verbinclude StructuredPolynomialFit.out +</td></tr></table> + +\subsection StructuredExampleSeparableLeastSquares Separable least squares on a grid + +The design matrix of a tensor-product polynomial fit on a grid is the Kronecker product of two rectangular Vandermonde +matrices. \ref KroneckerOperator::leastSquaresSolve applies \f$ (A \otimes B)^+ = A^+ \otimes B^+ \f$ [27] with one +complete orthogonal decomposition per factor, and \ref KroneckerOperator::rank and +\ref KroneckerOperator::singularValues come from the factors too; the dense decomposition of the assembled matrix +agrees. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredSeparableLeastSquares.cpp +</td> +<td> +\verbinclude StructuredSeparableLeastSquares.out +</td></tr></table> + +\section StructuredExamplesStatistics Statistics and estimation + +\subsection StructuredExampleGaussianProcess A Gaussian-process likelihood + +A covariance that is noise plus a low-rank feature model [19], [20] is a \ref DiagonalPlusLowRank operator. Its solve +(Woodbury identity) and determinant (matrix determinant lemma) cost \f$ O(n k^2) \f$, the price of evaluating the +log-likelihood. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredGaussianProcess.cpp +</td> +<td> +\verbinclude StructuredGaussianProcess.out +</td></tr></table> + +\subsection StructuredExampleKalmanUpdate A Kalman measurement update + +With a diagonal prior and \f$ k \f$ measurements, the posterior precision is diagonal plus rank \f$ k \f$, and +\ref DiagonalPlusLowRank::inverse returns the posterior covariance as another \ref DiagonalPlusLowRank, since the +Woodbury identity is the Kalman update [24]. The posterior mean is one \f$ O(nk) \f$ product and the posterior variances are +read off the diagonal; the dense \f$ n \times n \f$ computation agrees. + +<table class="example"> +<tr><th>Example:</th><th>Output:</th></tr> +<tr><td> +\include StructuredKalmanUpdate.cpp +</td> +<td> +\verbinclude StructuredKalmanUpdate.out +</td></tr></table> + +*/ + +} // namespace Eigen
diff --git a/contrib/doc/examples/StructuredADI.cpp b/contrib/doc/examples/StructuredADI.cpp new file mode 100644 index 0000000..a6d36e2 --- /dev/null +++ b/contrib/doc/examples/StructuredADI.cpp
@@ -0,0 +1,63 @@ +// 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); + const auto xImplicit = makeKroneckerOperator(Id, SparseMatrix<double>(I + tau / 2 * D)); + const auto yImplicit = makeKroneckerOperator(SparseMatrix<double>(I + tau / 2 * D), Id); + const auto xExplicit = makeKroneckerOperator(Id, SparseMatrix<double>(I - tau / 2 * D)); + const auto yExplicit = makeKroneckerOperator(SparseMatrix<double>(I - tau / 2 * D), Id); + + // u0 = sin(pi x) sin(2 pi y), an eigenvector of both directions. + VectorXd sx(n), sy(n); + for (int i = 0; i < n; ++i) { + sx[i] = std::sin(pi * (i + 1) * h); + sy[i] = std::sin(2 * pi * (i + 1) * h); + } + const VectorXd u0 = (sx * sy.transpose()).reshaped(); // entry j*n + i is (x_i, y_j) + VectorXd u = u0; + for (int k = 0; k < steps; ++k) { + const VectorXd half = xImplicit.solve(yExplicit * u); + u = yImplicit.solve(xExplicit * half); + } + const auto factor = [&](double lambda) { return (1 - tau / 2 * lambda) / (1 + tau / 2 * lambda); }; + const double lx = 4 / (h * h) * std::pow(std::sin(pi * h / 2), 2), ly = 4 / (h * h) * std::pow(std::sin(pi * h), 2); + std::cout << n * n << " unknowns, " << steps << " ADI steps\n"; + std::cout << "amplitude: " << u.dot(u0) / u0.squaredNorm() << "\n"; + std::cout << "ADI, exact: " << std::pow(factor(lx) * factor(ly), steps) << "\n"; + std::cout << "PDE, exact: " << std::exp(-5 * pi * pi * tau * steps) << "\n"; +}
diff --git a/contrib/doc/examples/StructuredConvectionDiffusion.cpp b/contrib/doc/examples/StructuredConvectionDiffusion.cpp new file mode 100644 index 0000000..b46b04e --- /dev/null +++ b/contrib/doc/examples/StructuredConvectionDiffusion.cpp
@@ -0,0 +1,43 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Steady convection-diffusion -eps (u_xx + u_yy) + b_x u_x + b_y u_y = 1 on the +// unit square, u = 0 on the boundary, with centered differences. The 1-D +// operators eps D + b G (D = tridiag(-1, 2, -1) / h^2, G = tridiag(-1, 0, 1) / 2h) +// are not symmetric, so BartelsStewart takes the Schur path; the result agrees +// with SparseLU on the assembled matrix. + +#include <contrib/Eigen/StructuredMatrices> +#include <iostream> + +using namespace Eigen; + +SparseMatrix<double> convectionDiffusion(int n, double eps, double b) { + const double h = 1.0 / (n + 1); + 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 BartelsStewart<std::decay_t<decltype(L)>> solver(L); + const VectorXd f = VectorXd::Ones(n * n); + const VectorXd u = solver.solve(f); + + SparseMatrix<double> A; + A = L; // the assembled n^2 x n^2 matrix, for comparison + const VectorXd uLU = SparseLU<SparseMatrix<double>>(A).solve(f); + std::cout << "fast diagonalization: " << (solver.isHermitian() ? "yes" : "no") << "\n"; + std::cout << "max u: " << u.maxCoeff() << "\n"; + std::cout << "relative residual: " << (A * u - f).norm() / f.norm() << "\n"; + std::cout << "|u - u_SparseLU|/|u|: " << (u - uLU).norm() / u.norm() << "\n"; +}
diff --git a/contrib/doc/examples/StructuredDeblurring.cpp b/contrib/doc/examples/StructuredDeblurring.cpp new file mode 100644 index 0000000..eb052fc --- /dev/null +++ b/contrib/doc/examples/StructuredDeblurring.cpp
@@ -0,0 +1,58 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Image deblurring with periodic boundary conditions. Blurring an n x n image +// X with a point spread function G is the 2-D circular convolution G (*) X, so +// the blur matrix A is a Bccb. For a motion blur over L pixels, the box filter, +// the symbol vanishes on the L - 1 frequency lines k = j n / L: A is exactly +// rank deficient, Bccb::rank counts the retained modes, and the pseudo-inverse +// A.solve recovers nothing on those lines while amplifying the noise of the +// recorded image on the lines next to them. Tikhonov regularization, +// x_lambda = (A^H A + lambda I)^{-1} A^H b, +// keeps the structure: A^H A + lambda I is the Bccb whose generator is the +// autocorrelation A^H (A e_0) of the PSF plus lambda at the origin, so each +// candidate lambda costs one O(N log N) solve. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iostream> +#include <random> + +using namespace Eigen; + +int main() { + const int n = 128, N = n * n; + const int L = 8; // the camera moves L pixels along the columns during the exposure + MatrixXd G = MatrixXd::Zero(n, n); + G.col(0).head(L).setConstant(1.0 / L); + const auto A = makeBccb(G); + + // The image: a bright rectangle and a disc on a dark background. + MatrixXd X = MatrixXd::Constant(n, n, 0.1); + X.block(32, 40, 32, 48).setConstant(1.0); + for (int j = 0; j < n; ++j) + for (int i = 0; i < n; ++i) + if ((i - 90) * (i - 90) + (j - 40) * (j - 40) < 400) X(i, j) = 0.6; + const VectorXd x = X.reshaped(); + + // Blur and add 1% noise from a generator whose sequence the C++ standard fixes. + std::minstd_rand generator(1); + VectorXd b = A * x; + for (int i = 0; i < N; ++i) b[i] += 0.01 * (2.0 * generator() / generator.max() - 1); + + const VectorXd s = A.singularValues(); // decreasing + std::cout << "rank " << A.rank() << " of " << N << ", smallest retained singular value " << s[A.rank() - 1] << "\n"; + std::cout << "relative error of the blurred image: " << (b - x).norm() / x.norm() << "\n"; + std::cout << "relative error of the pseudo-inverse: " << (A.solve(b) - x).norm() / x.norm() << "\n"; + + VectorXd e0 = VectorXd::Zero(N); + e0[0] = 1; + const VectorXd autocorrelation = A.adjoint() * VectorXd(A * e0); // first column of A^H A + const VectorXd Ahb = A.adjoint() * b; + for (double lambda : {1e-4, 1e-3, 1e-2, 1e-1}) { + VectorXd g = autocorrelation; + g[0] += lambda; + const VectorXd xl = makeBccb(g.reshaped(n, n)).solve(Ahb); + std::cout << "Tikhonov, lambda = " << lambda << ": relative error " << (xl - x).norm() / x.norm() << "\n"; + } +}
diff --git a/contrib/doc/examples/StructuredDeconvolution.cpp b/contrib/doc/examples/StructuredDeconvolution.cpp new file mode 100644 index 0000000..265cb29 --- /dev/null +++ b/contrib/doc/examples/StructuredDeconvolution.cpp
@@ -0,0 +1,52 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Deconvolution as a rectangular Toeplitz least-squares problem. A signal s of +// length n recorded through a causal kernel h of length k is the full +// convolution y = T s, with T the (n + k - 1) x n Toeplitz matrix whose first +// column holds h. LSMR recovers s from y without forming T: every iteration +// applies T and T^T through the FFT, in O(p log p) for the embedding length +// p >= n + k - 1, the adjoint reusing the embedding symbol. For the kernel +// h_j = a^j, |a| < 1, the system is well conditioned, kappa ~ (1 + a)/(1 - a), +// so noise in y passes into s amplified by at most that factor. The dense QR +// of the materialized matrix gives the same solution at O(m n^2). + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iostream> +#include <random> + +using namespace Eigen; + +int main() { + const int n = 1000, k = 50, m = n + k - 1; + const double a = 0.9; + // The signal: two Gaussian pulses and a step. + VectorXd s(n); + for (int i = 0; i < n; ++i) + s[i] = std::exp(-std::pow((i - 300) / 20.0, 2)) + 0.5 * std::exp(-std::pow((i - 450) / 10.0, 2)) + + (i > 700 && i < 850 ? 0.8 : 0.0); + VectorXd column = VectorXd::Zero(m), row = VectorXd::Zero(n); + for (int j = 0; j < k; ++j) column[j] = std::pow(a, j); + row[0] = column[0]; + const auto T = makeToeplitz(column, row); // m x n + const VectorXd y = T * s; + + LSMR<std::decay_t<decltype(T)>, IdentityPreconditioner> lsmr(T); + lsmr.setTolerance(1e-12); + const VectorXd recovered = lsmr.solve(y); + std::cout << "LSMR, exact data: " << lsmr.iterations() << " iterations, max error " + << (recovered - s).cwiseAbs().maxCoeff() << "\n"; + + // 1% noise from a generator whose sequence the C++ standard fixes. + std::minstd_rand generator(1); + VectorXd noisy = y; + for (int i = 0; i < m; ++i) noisy[i] += 0.01 * (2.0 * generator() / generator.max() - 1); + const VectorXd fromNoisy = lsmr.solve(noisy); + std::cout << "LSMR, noisy data: " << lsmr.iterations() << " iterations, max error " + << (fromNoisy - s).cwiseAbs().maxCoeff() << "\n"; + + const MatrixXd dense = T; + std::cout << "dense QR of the " << m << " x " << n << " matrix, noisy data: max error " + << (dense.householderQr().solve(noisy) - s).cwiseAbs().maxCoeff() << "\n"; +}
diff --git a/contrib/doc/examples/StructuredDivideAndConquer.cpp b/contrib/doc/examples/StructuredDivideAndConquer.cpp new file mode 100644 index 0000000..8b446ae --- /dev/null +++ b/contrib/doc/examples/StructuredDivideAndConquer.cpp
@@ -0,0 +1,51 @@ +// 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"; +}
diff --git a/contrib/doc/examples/StructuredGaussianProcess.cpp b/contrib/doc/examples/StructuredGaussianProcess.cpp new file mode 100644 index 0000000..d38ab39 --- /dev/null +++ b/contrib/doc/examples/StructuredGaussianProcess.cpp
@@ -0,0 +1,40 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// The log-likelihood of observations y under a Gaussian process with k Fourier +// features on a fixed frequency grid and noise variance s^2, +// log N(y | 0, S) = -(y^T S^{-1} y + log det S + n log(2 pi)) / 2, +// S = s^2 I + U U^T, U = (n x k feature matrix), +// costs O(n k^2) with DiagonalPlusLowRank: the Woodbury identity for the solve +// and the matrix determinant lemma for the determinant, instead of the O(n^3) +// Cholesky factorization of the dense covariance. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iostream> + +using namespace Eigen; + +int main() { + const double pi = std::acos(-1.0), noise = 1.0; + const int n = 1000, k = 20; + VectorXd t(n), y(n); + for (int i = 0; i < n; ++i) { + t[i] = 10.0 * i / n; + y[i] = std::sin(t[i]) + 0.3 * std::cos(3 * t[i]); + } + // Features sqrt(2/k) cos(omega_j t + phase_j) on a fixed frequency grid. + MatrixXd U(n, k); + for (int j = 0; j < k; ++j) + for (int i = 0; i < n; ++i) U(i, j) = std::sqrt(2.0 / k) * std::cos(0.25 * j * t[i] + 0.5 * j); + + const auto S = makeDiagonalPlusLowRank(VectorXd::Constant(n, noise * noise), U, U); + const double logLikelihood = -(y.dot(S.solve(y)) + std::log(S.determinant()) + n * std::log(2 * pi)) / 2; + + const MatrixXd dense = noise * noise * MatrixXd::Identity(n, n) + U * U.transpose(); + const LLT<MatrixXd> llt(dense); + const double logDet = 2 * llt.matrixL().toDenseMatrix().diagonal().array().log().sum(); + const double reference = -(y.dot(llt.solve(y)) + logDet + n * std::log(2 * pi)) / 2; + std::cout << "log-likelihood, Woodbury: " << logLikelihood << "\n"; + std::cout << "log-likelihood, dense: " << reference << "\n"; +}
diff --git a/contrib/doc/examples/StructuredHarmonicOscillator.cpp b/contrib/doc/examples/StructuredHarmonicOscillator.cpp new file mode 100644 index 0000000..323c342 --- /dev/null +++ b/contrib/doc/examples/StructuredHarmonicOscillator.cpp
@@ -0,0 +1,30 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// The 2-D quantum harmonic oscillator H = -(d_xx + d_yy) / 2 + (x^2 + y^2) / 2 +// separates as H = H_1 (+) H_1 with the 1-D Hamiltonian H_1, so its spectrum +// is the set of pairwise sums of the 1-D energies -- here from a +// finite-difference H_1 on [-8, 8], without ever forming the 2-D matrix. The +// exact energies are n_x + n_y + 1, with degeneracy n_x + n_y + 1. + +#include <contrib/Eigen/StructuredMatrices> +#include <algorithm> +#include <iostream> + +using namespace Eigen; + +int main() { + const int n = 400; + const double a = 8, h = 2 * a / (n + 1); + MatrixXd H1 = MatrixXd::Zero(n, n); + for (int i = 0; i < n; ++i) { + const double x = -a + (i + 1) * h; + H1(i, i) = 1 / (h * h) + x * x / 2; + if (i + 1 < n) H1(i, i + 1) = H1(i + 1, i) = -1 / (2 * h * h); + } + const auto H = makeKroneckerSum(H1, H1); + VectorXd energies = H.eigenvalues().real(); + std::sort(energies.data(), energies.data() + energies.size()); + std::cout << H.rows() << " x " << H.cols() << " Hamiltonian, lowest energies:\n" + << energies.head(10).transpose() << "\n"; +}
diff --git a/contrib/doc/examples/StructuredHeat3D.cpp b/contrib/doc/examples/StructuredHeat3D.cpp new file mode 100644 index 0000000..f88498b --- /dev/null +++ b/contrib/doc/examples/StructuredHeat3D.cpp
@@ -0,0 +1,55 @@ +// 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)); + const BartelsStewart<std::decay_t<decltype(M)>> step(M); + + // u0 = sin(pi x) sin(pi y) sin(pi z), an eigenvector of D (+) D (+) D. + VectorXd s(n); + for (int i = 0; i < n; ++i) s[i] = std::sin(pi * (i + 1) * h); + const MatrixXd modes = (s * s.transpose()).reshaped() * s.transpose(); + const VectorXd u0 = modes.reshaped(); + VectorXd u = u0; + for (int k = 0; k < steps; ++k) u = step.solve(u); + + const double lambda = 3 * 4 / (h * h) * std::pow(std::sin(pi * h / 2), 2); + const double amplitude = u.dot(u0) / u0.squaredNorm(); + std::cout << n * n * n << " unknowns, " << steps << " steps\n"; + std::cout << "amplitude: " << amplitude << "\n"; + std::cout << "implicit Euler, exact: " << std::pow(1 + tau * lambda, -steps) << "\n"; + std::cout << "heat equation, exact: " << std::exp(-3 * pi * pi * tau * steps) << "\n"; +}
diff --git a/contrib/doc/examples/StructuredImpurity.cpp b/contrib/doc/examples/StructuredImpurity.cpp new file mode 100644 index 0000000..9877501 --- /dev/null +++ b/contrib/doc/examples/StructuredImpurity.cpp
@@ -0,0 +1,30 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// A Koster-Slater impurity: a tight-binding ring of N sites with hopping t and +// one site shifted by V < 0. In the Bloch basis the band is diagonal, +// e_k = -2t cos(2 pi k / N), and the impurity is the rank-one update +// V z z^T with z_k = 1/sqrt(N), so H = D + V z z^T is diagonal plus rank one. +// DPR1EigenSolver finds all N eigenvalues in O(N^2) from the secular equation; +// one of them splits off below the band, approaching the infinite-chain bound +// state -sqrt(V^2 + 4 t^2). + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iomanip> +#include <iostream> + +using namespace Eigen; + +int main() { + const double pi = std::acos(-1.0), t = 1.0, V = -1.5; + std::cout << " N lowest eigenvalue band bottom\n"; + for (int N : {16, 64, 256, 1024}) { + VectorXd d(N); + for (int k = 0; k < N; ++k) d[k] = -2 * t * std::cos(2 * pi * k / N); + const VectorXd z = VectorXd::Constant(N, 1 / std::sqrt(double(N))); + const DPR1EigenSolver<double> es(d, V, z, /*options=*/0); + std::cout << std::setw(6) << N << " " << std::setw(16) << es.eigenvalues()[0] << " " << d.minCoeff() << "\n"; + } + std::cout << "infinite chain: " << -std::sqrt(V * V + 4 * t * t) << "\n"; +}
diff --git a/contrib/doc/examples/StructuredKalmanUpdate.cpp b/contrib/doc/examples/StructuredKalmanUpdate.cpp new file mode 100644 index 0000000..0c80145 --- /dev/null +++ b/contrib/doc/examples/StructuredKalmanUpdate.cpp
@@ -0,0 +1,53 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// The measurement update of a Kalman filter in information form. A field x on +// n grid points has the prior N(0, tau^2 I); k sensors record weighted sums +// y = H x + e over short footprints, with noise e ~ N(0, s^2 I). The posterior +// precision +// P^{-1} = tau^{-2} I + s^{-2} H^T H +// is diagonal plus rank k, and DiagonalPlusLowRank::inverse returns the +// posterior covariance P as another DiagonalPlusLowRank: the Woodbury identity, +// which is the Kalman update. The posterior mean P H^T y / s^2 is then one O(nk) +// product and the posterior variances are the diagonal of P, with no n x n +// matrix anywhere. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iomanip> +#include <iostream> +#include <random> + +using namespace Eigen; + +int main() { + const int n = 400, k = 40, width = 4; + const double tau = 1.0, s = 0.05; + // Sensor j averages the points [100 + 2 j, 100 + 2 j + width); neighboring footprints overlap. + MatrixXd H = MatrixXd::Zero(k, n); + for (int j = 0; j < k; ++j) H.row(j).segment(100 + 2 * j, width).setConstant(1.0 / width); + VectorXd x(n); + for (int i = 0; i < n; ++i) x[i] = std::sin(0.05 * i) + 0.5 * std::cos(0.2 * i); + std::minstd_rand generator(1); + VectorXd y = H * x; + for (int j = 0; j < k; ++j) y[j] += s * (2.0 * generator() / generator.max() - 1); + + const auto information = makeDiagonalPlusLowRank(VectorXd::Constant(n, 1 / (tau * tau)), H.transpose() / (s * s), + H.transpose()); // P^{-1} + const auto P = information.inverse(); + const VectorXd mean = P * VectorXd(H.transpose() * y / (s * s)); + + const MatrixXd dense = (MatrixXd::Identity(n, n) / (tau * tau) + H.transpose() * H / (s * s)).inverse(); + const VectorXd denseMean = dense * H.transpose() * y / (s * s); + double varianceError = 0; + for (int i = 0; i < n; ++i) varianceError = std::max(varianceError, std::abs(P.coeff(i, i) - dense(i, i))); + + std::cout << "point footprints truth posterior mean posterior std\n"; + for (int i : {50, 100, 101, 140, 179, 250}) { + const int footprints = int((H.col(i).array() != 0).count()); + std::cout << std::setw(5) << i << std::setw(12) << footprints << std::setw(7) << std::setprecision(3) << x[i] + << std::setw(16) << mean[i] << std::setw(15) << std::sqrt(P.coeff(i, i)) << "\n"; + } + std::cout << std::setprecision(6) << "max |mean - dense|: " << (mean - denseMean).cwiseAbs().maxCoeff() + << ", max |variance - dense|: " << varianceError << "\n"; +}
diff --git a/contrib/doc/examples/StructuredLoveEquation.cpp b/contrib/doc/examples/StructuredLoveEquation.cpp new file mode 100644 index 0000000..adb3c38 --- /dev/null +++ b/contrib/doc/examples/StructuredLoveEquation.cpp
@@ -0,0 +1,84 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Two Toeplitz problems. +// +// Love's integral equation for the field between two coaxial disks at unit +// distance (a classical test problem of electrostatics), +// u(x) - (1/pi) \int_{-1}^{1} u(t) / (1 + (x - t)^2) dt = 1, -1 <= x <= 1. +// The midpoint rule on n equal cells gives (I - K) u = 1 with a symmetric +// Toeplitz K, K_ij = h / (pi (1 + (x_i - x_j)^2)), which LookAheadLevinson +// solves directly in O(n^2). +// +// A large dense Toeplitz system, T_ij = (1 + |i - j|)^(-1.1), solved +// by conjugate gradients: the Toeplitz product costs O(n log n) through the +// FFT, and the Strang preconditioner -- the central diagonals of T wrapped into +// a circulant C, inverted by Circulant::solve in O(n log n) -- clusters the +// spectrum of C^{-1} T around 1. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iomanip> +#include <iostream> + +using namespace Eigen; + +// The iterative solvers' preconditioner interface around Circulant::solve. +class StrangPreconditioner { + public: + void setToeplitzColumn(const VectorXd& t) { + const Index n = t.size(); + VectorXd c(n); + for (Index k = 0; k < n; ++k) c[k] = t[k <= n / 2 ? k : n - k]; + m_circulant = Circulant<double>(c); + } + template <typename MatrixType> + StrangPreconditioner& analyzePattern(const MatrixType&) { + return *this; + } + template <typename MatrixType> + StrangPreconditioner& factorize(const MatrixType&) { + return *this; + } + template <typename MatrixType> + StrangPreconditioner& compute(const MatrixType&) { + return *this; + } + template <typename Rhs> + VectorXd solve(const MatrixBase<Rhs>& b) const { + return m_circulant.solve(b); + } + ComputationInfo info() const { return Success; } + + private: + Circulant<double> m_circulant{VectorXd::Ones(1)}; +}; + +int main() { + const double pi = std::acos(-1.0); + std::cout << "Love's equation:\n n u(0)\n"; + for (int n : {64, 128, 256, 512}) { + const double h = 2.0 / n; + VectorXd c(n); + for (int k = 0; k < n; ++k) c[k] = -h / (pi * (1 + (k * h) * (k * h))); + c[0] += 1; + const VectorXd u = LookAheadLevinson<double>(makeToeplitz(c, c)).solve(VectorXd::Ones(n)); + std::cout << std::setw(6) << n << " " << std::setprecision(8) << (u[n / 2 - 1] + u[n / 2]) / 2 << "\n"; + } + + const int n = 1 << 16; + VectorXd t(n); + for (int k = 0; k < n; ++k) t[k] = std::pow(1.0 + k, -1.1); + const auto T = makeToeplitz(t, t); + const VectorXd b = VectorXd::Ones(n); + ConjugateGradient<std::decay_t<decltype(T)>, Lower | Upper, IdentityPreconditioner> plain(T); + plain.setTolerance(1e-10); + ConjugateGradient<std::decay_t<decltype(T)>, Lower | Upper, StrangPreconditioner> strang; + strang.setTolerance(1e-10); + strang.preconditioner().setToeplitzColumn(t); + strang.compute(T); + const VectorXd x0 = plain.solve(b), x1 = strang.solve(b); + std::cout << "Toeplitz system, n = " << n << ", CG iterations to a 1e-10 residual:\n"; + std::cout << " no preconditioner: " << plain.iterations() << "\n"; + std::cout << " Strang circulant: " << strang.iterations() << "\n"; +}
diff --git a/contrib/doc/examples/StructuredLyapunov.cpp b/contrib/doc/examples/StructuredLyapunov.cpp new file mode 100644 index 0000000..6a3e9e3 --- /dev/null +++ b/contrib/doc/examples/StructuredLyapunov.cpp
@@ -0,0 +1,37 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// The controllability Gramian X of a damped mass-spring chain x' = A x + B w, +// forced at the last mass, solves the Lyapunov equation A X + X A^T + B B^T = 0. +// With vec stacking columns, vec(A X + X A^T) = (A (+) A) vec(X), so the +// equation is one Kronecker-sum solve. A is not symmetric and has complex +// eigenvalue pairs (an underdamped chain); X is symmetric positive definite +// when the chain is controllable. + +#include <contrib/Eigen/StructuredMatrices> +#include <iostream> + +using namespace Eigen; + +int main() { + const int masses = 20, n = 2 * masses; + const double damping = 0.1; + // State (positions, velocities): A = [0 I; -K -c I] with K = tridiag(-1, 2, -1). + MatrixXd A = MatrixXd::Zero(n, n); + A.topRightCorner(masses, masses).setIdentity(); + for (int i = 0; i < masses; ++i) { + A(masses + i, i) = -2; + if (i > 0) A(masses + i, i - 1) = 1; + if (i + 1 < masses) A(masses + i, i + 1) = 1; + A(masses + i, masses + i) = -damping; + } + VectorXd B = VectorXd::Zero(n); + B[n - 1] = 1; + const MatrixXd Q = B * B.transpose(); + + const MatrixXd X = makeKroneckerSum(A, A).solve(-Q.reshaped()).reshaped(n, n); + std::cout << "residual |AX + XA^T + BB^T| / |BB^T|: " << (A * X + X * A.transpose() + Q).norm() / Q.norm() << "\n"; + std::cout << "asymmetry |X - X^T| / |X|: " << (X - X.transpose()).norm() / X.norm() << "\n"; + std::cout << "smallest eigenvalue of X: " + << SelfAdjointEigenSolver<MatrixXd>((X + X.transpose()) / 2).eigenvalues()[0] << "\n"; +}
diff --git a/contrib/doc/examples/StructuredPade.cpp b/contrib/doc/examples/StructuredPade.cpp new file mode 100644 index 0000000..d3486f3 --- /dev/null +++ b/contrib/doc/examples/StructuredPade.cpp
@@ -0,0 +1,52 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// The [m/m] Pade approximant p(x)/q(x) of exp(x), q(0) = 1, from its Taylor +// coefficients. Matching the series through degree 2m gives the denominator +// from a Hankel system in the coefficients c_k, +// sum_{j=1}^{m} c_{m+i-j} q_j = -c_{m+i}, i = 1..m, +// written with H(i,j) = c_{i+j+1} (j reversed), and the numerator by a +// truncated convolution p_i = sum_{j<=i} c_{i-j} q_j. +// +// The raw coefficients 1/k! fall from 1 to 1/(2m)! across H, which leaves it +// badly scaled: kappa(H) ~ 7e15 at m = 8. Approximating exp(t y) instead, with +// coefficients c_k = t^k / k!, scales H to t D H D, D = diag(t^i) -- still +// Hankel -- and t = m equilibrates it: kappa(H) ~ 5e7 at m = 8. The +// approximant of exp(x) is then p(x/t) / q(x/t), since the substitution +// preserves both the degrees and the order of contact. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iomanip> +#include <iostream> + +using namespace Eigen; + +int main() { + std::cout << " m |r(1) - e| |r(-2) - e^-2|\n"; + for (int m : {2, 4, 6, 8, 10}) { + const double t = m; + VectorXd c(2 * m + 1); + c[0] = 1; + for (int k = 1; k <= 2 * m; ++k) c[k] = c[k - 1] * t / k; + // H(i, j) = c_{i+j+1} for i, j = 0..m-1: first column c_1..c_m, last row c_m..c_{2m-1}. + const auto H = makeHankel(c.segment(1, m), c.segment(m, m)); + // The unknowns are q_m, ..., q_1 (reversed): row i reads c_{i+1} q_m + ... + c_{m+i} q_1. + const VectorXd reversed = H.solve(-c.segment(m + 1, m)); + VectorXd q(m + 1), p(m + 1); + q[0] = 1; + q.tail(m) = reversed.reverse(); + for (int i = 0; i <= m; ++i) p[i] = c.head(i + 1).reverse().dot(q.head(i + 1)); + const auto r = [&](double x) { + const double y = x / t; + double num = 0, den = 0; + for (int i = m; i >= 0; --i) { + num = num * y + p[i]; + den = den * y + q[i]; + } + return num / den; + }; + std::cout << std::setw(2) << m << " " << std::setw(15) << std::abs(r(1) - std::exp(1.0)) << " " + << std::abs(r(-2) - std::exp(-2.0)) << "\n"; + } +}
diff --git a/contrib/doc/examples/StructuredPoisson2D.cpp b/contrib/doc/examples/StructuredPoisson2D.cpp new file mode 100644 index 0000000..7779d54 --- /dev/null +++ b/contrib/doc/examples/StructuredPoisson2D.cpp
@@ -0,0 +1,46 @@ +// 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 auto L = makeKroneckerSum(D, D); // y on the left (slow index), x on the right + const BartelsStewart<std::decay_t<decltype(L)>> poisson(L); + const VectorXd u = poisson.solve(f); + std::cout << "n = " << n << ": max error " << (u - exact).cwiseAbs().maxCoeff() << "\n"; + } +}
diff --git a/contrib/doc/examples/StructuredPolynomialFit.cpp b/contrib/doc/examples/StructuredPolynomialFit.cpp new file mode 100644 index 0000000..5238f58 --- /dev/null +++ b/contrib/doc/examples/StructuredPolynomialFit.cpp
@@ -0,0 +1,56 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Least-squares polynomial approximation in the monomial basis. The normal +// equations of the continuous problem, min \int_0^1 (f - sum_j c_j x^j)^2 dx, +// have the Hilbert matrix H_ij = 1/(i + j + 1), the Cauchy matrix with nodes +// x_i = i + 1 and y_j = -j, and the moments m_i = \int_0^1 x^i f dx on the right. +// CauchyLU solves them in O(n^2), and Cauchy::determinant evaluates det H in +// closed form where dense LU, at kappa(H_n) ~ e^{3.5 n}, loses digits. The +// coefficients inherit the conditioning, the fitted polynomial much less: the +// coefficient error d = H^{-1} r of a residual r = H c - m perturbs the fit by +// (d^T H d)^{1/2} = (r^T H^{-1} r)^{1/2} in L^2, so the fit loses at most about +// sqrt(kappa) eps where the coefficients can lose kappa eps. The discrete +// least-squares fit -- a dense QR of the rectangular Vandermonde matrix of 200 +// sample points -- is the reference; Vandermonde products (Horner's rule) +// evaluate both fits. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iomanip> +#include <iostream> + +using namespace Eigen; + +int main() { + const double e = std::exp(1.0); + const ArrayXd samples = ArrayXd::LinSpaced(200, 0, 1), fine = ArrayXd::LinSpaced(1001, 0, 1); + std::cout << " n det H: Cauchy dense LU exact fit error: Hilbert QR\n"; + for (int n : {4, 6, 8, 10}) { + const auto H = makeCauchy(VectorXd::LinSpaced(n, 1, n), -VectorXd::LinSpaced(n, 0, n - 1)); + // m_i = e - i m_{i-1}, run backwards from m_40 ~ e / 41: the forward recurrence amplifies errors by i!. + VectorXd moments(n); + double mi = e / 41; + for (int i = 40; i > 0; --i) { + mi = (e - mi) / i; + if (i <= n) moments[i - 1] = mi; + } + const VectorXd c = CauchyLU<double>(H).solve(moments); + + const MatrixXd V = makeVandermonde(samples.matrix(), n); // 200 x n + const VectorXd cq = V.colPivHouseholderQr().solve(samples.exp().matrix()); + + // det H_n = c_n^4 / c_{2n} with c_n = prod_{i<n} i! + double cn = 1, c2n = 1, factorial = 1; + for (int i = 1; i < 2 * n; ++i) { + factorial *= i; + if (i < n) cn *= factorial; + c2n *= factorial; + } + const auto E = makeVandermonde(fine.matrix(), n); + std::cout << std::setw(2) << n << std::setprecision(8) << std::setw(16) << H.determinant() << std::setw(15) + << MatrixXd(H).determinant() << std::setw(15) << std::pow(cn, 4) / c2n << std::setprecision(3) + << std::setw(16) << (E * c - fine.exp().matrix()).cwiseAbs().maxCoeff() << std::setw(13) + << (E * cq - fine.exp().matrix()).cwiseAbs().maxCoeff() << "\n"; + } +}
diff --git a/contrib/doc/examples/StructuredPreconditioner.cpp b/contrib/doc/examples/StructuredPreconditioner.cpp new file mode 100644 index 0000000..a6245d5 --- /dev/null +++ b/contrib/doc/examples/StructuredPreconditioner.cpp
@@ -0,0 +1,93 @@ +// 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; +} + +using Laplacian = KroneckerSum<SparseMatrix<double>, SparseMatrix<double>>; + +// Applies (L + c I)^{-1} through BartelsStewart: the preconditioner interface +// the iterative solvers expect. +class SeparablePreconditioner { + public: + void setOperator(const Laplacian& shifted) { m_solver.compute(shifted); } + template <typename MatrixType> + SeparablePreconditioner& analyzePattern(const MatrixType&) { + return *this; + } + template <typename MatrixType> + SeparablePreconditioner& factorize(const MatrixType&) { + return *this; + } + template <typename MatrixType> + SeparablePreconditioner& compute(const MatrixType&) { + return *this; + } + template <typename Rhs> + VectorXd solve(const MatrixBase<Rhs>& b) const { + return m_solver.solve(b); + } + ComputationInfo info() const { return m_solver.info(); } + + private: + BartelsStewart<Laplacian> m_solver; +}; + +int main() { + const int n = 128; + const double h = 1.0 / (n + 1); + const SparseMatrix<double> D = secondDifference(n); + const Laplacian L = makeKroneckerSum(D, D); + + // A Gaussian well, centered off the grid's symmetry axes. + VectorXd V(n * n); + for (int j = 0; j < n; ++j) + for (int i = 0; i < n; ++i) { + const double x = (i + 1) * h - 0.4, y = (j + 1) * h - 0.6; + V[j * n + i] = 2000 * std::exp(-(x * x + y * y) / 0.01); + } + SparseMatrix<double> Vd(n * n, n * n); + Vd.setIdentity(); + Vd = Vd * V.asDiagonal(); + const SparseMatrix<double> H = L.sparseView() + Vd; // assembled without materializing L + const VectorXd f = VectorXd::Ones(n * n); + + ConjugateGradient<SparseMatrix<double>, Lower | Upper, IdentityPreconditioner> plain(H); + ConjugateGradient<SparseMatrix<double>, Lower | Upper, DiagonalPreconditioner<double>> jacobi(H); + // The preconditioner gets its operator before compute(), which reads its info(). + ConjugateGradient<SparseMatrix<double>, Lower | Upper, SeparablePreconditioner> separable; + 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"; +}
diff --git a/contrib/doc/examples/StructuredProny.cpp b/contrib/doc/examples/StructuredProny.cpp new file mode 100644 index 0000000..72056ad --- /dev/null +++ b/contrib/doc/examples/StructuredProny.cpp
@@ -0,0 +1,48 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Prony's method fits a sum of r complex exponentials, f_t = sum_j c_j z_j^t, +// to equally spaced samples f_0, ..., f_{m-1}. Every such sequence obeys the +// linear recurrence whose characteristic polynomial has the z_j as roots, +// f_{t+r} + a_{r-1} f_{t+r-1} + ... + a_0 f_t = 0, +// so the coefficients a solve a Hankel system in the samples, H(t, k) = f_{t+k}, +// and the recurrence residual over all samples is a rectangular Hankel product. +// The roots are the nodes z_j, with damping -log|z_j| and frequency arg z_j; the +// amplitudes solve the dual Vandermonde system V^T c = f, V(j, t) = z_j^t, with +// complex nodes, by Bjorck-Pereyra. A real signal gives conjugate pairs. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <complex> +#include <iomanip> +#include <iostream> + +using namespace Eigen; + +int main() { + const int r = 4, m = 64; + // Two damped sinusoids A exp(-alpha t) cos(omega t + phi): four exponentials. + const double alpha[2] = {0.02, 0.05}, omega[2] = {0.3, 1.1}, A[2] = {1.0, 0.5}, phi[2] = {0.0, 0.7}; + VectorXd f = VectorXd::Zero(m); + for (int t = 0; t < m; ++t) + for (int j = 0; j < 2; ++j) f[t] += A[j] * std::exp(-alpha[j] * t) * std::cos(omega[j] * t + phi[j]); + + // The r x r Hankel system on the first 2r samples, and the recurrence on all m. + const VectorXd a = makeHankel(f.head(r), f.segment(r - 1, r)).solve(-f.segment(r, r)); + const auto H = makeHankel(f.head(m - r), f.segment(m - r - 1, r)); + std::cout << "recurrence residual over " << m << " samples: " << (H * a + f.tail(m - r)).norm() << "\n"; + + // The roots of z^r + a_{r-1} z^{r-1} + ... + a_0 are the eigenvalues of its companion matrix. + MatrixXd companion = MatrixXd::Zero(r, r); + companion.bottomLeftCorner(r - 1, r - 1).setIdentity(); + companion.col(r - 1) = -a; + const VectorXcd z = EigenSolver<MatrixXd>(companion, false).eigenvalues(); + const BjorckPereyra<std::complex<double>> amplitudes(makeVandermonde(z)); + 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"; +}
diff --git a/contrib/doc/examples/StructuredQuadrature.cpp b/contrib/doc/examples/StructuredQuadrature.cpp new file mode 100644 index 0000000..587ad1a --- /dev/null +++ b/contrib/doc/examples/StructuredQuadrature.cpp
@@ -0,0 +1,37 @@ +// 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 BjorckPereyra<double> bp(makeVandermonde(x)); + const VectorXd w = bp.transpose().solve(moments); + std::cout << std::setw(3) << n << " " << std::setw(6) << w.sum() << " " + << std::abs(w.dot(x.array().exp().matrix()) - exact) << "\n"; + } + + // Interpolation: the cubic through four samples of x^3 - 2x + 1. + const Vector4d x(-1, 0, 0.5, 2); + const Vector4d f = x.array().cube() - 2 * x.array() + 1; + std::cout << "monomial coefficients of the interpolant: " + << BjorckPereyra<double>(makeVandermonde(x)).solve(f).transpose() << "\n"; +}
diff --git a/contrib/doc/examples/StructuredRationalApproximation.cpp b/contrib/doc/examples/StructuredRationalApproximation.cpp new file mode 100644 index 0000000..986608c --- /dev/null +++ b/contrib/doc/examples/StructuredRationalApproximation.cpp
@@ -0,0 +1,42 @@ +// 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]); + } + const VectorXcd c = CauchyLU<Complex>(makeCauchy(z, w)).solve(fz); + + // 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"; + } +}
diff --git a/contrib/doc/examples/StructuredSeparableLeastSquares.cpp b/contrib/doc/examples/StructuredSeparableLeastSquares.cpp new file mode 100644 index 0000000..a82e402 --- /dev/null +++ b/contrib/doc/examples/StructuredSeparableLeastSquares.cpp
@@ -0,0 +1,40 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Least-squares fitting of a surface sampled on a grid by a tensor-product +// polynomial sum_{p,q} c_pq x^p y^q. With the samples F(x_i, y_j) stored with x +// as the fast index, the design matrix is the Kronecker product V_y (x) V_x of +// the two rectangular Vandermonde matrices, and KroneckerOperator solves the +// least-squares problem through one complete orthogonal decomposition per +// factor, (A (x) B)^+ = A^+ (x) B^+: for m points per direction and degrees +// P, Q, the two decompositions cost O(m (P^2 + Q^2)) and applying them +// O(m^2 (P + Q)), against O(m^2 P^2 Q^2) for the assembled m^2 x (P+1)(Q+1) +// matrix. Its rank and singular values also come from the factors. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iostream> + +using namespace Eigen; + +int main() { + const int m = 60; // grid points per direction + const ArrayXd x = ArrayXd::LinSpaced(m, -1, 1), y = ArrayXd::LinSpaced(m, -1, 1); + MatrixXd F(m, m); // F(i, j) = exp(x_i y_j), with x the fast index of vec(F) + for (int j = 0; j < m; ++j) + for (int i = 0; i < m; ++i) F(i, j) = std::exp(x[i] * y[j]); + + std::cout << "degree rank kappa max fit error |c - c_dense|\n"; + for (int degree : {2, 4, 6, 8}) { + const MatrixXd Vx = makeVandermonde(x.matrix(), degree + 1), Vy = makeVandermonde(y.matrix(), degree + 1); + const auto design = makeKroneckerOperator(Vy, Vx); // m^2 x (degree + 1)^2 + const VectorXd c = design.leastSquaresSolve(F.reshaped()); + const VectorXd s = design.singularValues(); + + const MatrixXd dense = design; + const VectorXd reference = dense.completeOrthogonalDecomposition().solve(F.reshaped()); + std::cout << " " << degree << " " << design.rank() << " " << s.maxCoeff() / s.minCoeff() << " " + << (F.reshaped() - design * c).cwiseAbs().maxCoeff() << " " << (c - reference).cwiseAbs().maxCoeff() + << "\n"; + } +}
diff --git a/contrib/doc/examples/StructuredSpectralDifferentiation.cpp b/contrib/doc/examples/StructuredSpectralDifferentiation.cpp new file mode 100644 index 0000000..acd6708 --- /dev/null +++ b/contrib/doc/examples/StructuredSpectralDifferentiation.cpp
@@ -0,0 +1,55 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// Fourier spectral differentiation on the periodic grid x_j = j h, h = 2 pi / N, +// N even. The differentiation matrix is the circulant with first column +// D_0 = 0, D_j = (-1)^j / (2 tan(j h / 2)), j = 1, ..., N-1, +// and the second-derivative matrix the circulant with +// D2_0 = -pi^2 / (3 h^2) - 1/6, D2_j = -(-1)^j / (2 sin^2(j h / 2)). +// Their eigenvalues are the wavenumbers: D has i k for |k| < N/2 and 0 for the +// constant and for the sawtooth mode k = N/2, so it is singular of rank N - 2, +// and Circulant::solve returns the minimum-norm antiderivative, the one with +// zero mean and no sawtooth component. The derivatives, the antiderivative and +// the periodic boundary value problem u'' - u = f all converge geometrically +// for u = exp(sin x). + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iomanip> +#include <iostream> + +using namespace Eigen; + +// First column of the N x N spectral differentiation matrix of the given order. +VectorXd spectralColumn(int N, int order) { + const double pi = std::acos(-1.0), h = 2 * pi / N; + VectorXd column(N); + column[0] = order == 1 ? 0 : -pi * pi / (3 * h * h) - 1.0 / 6; + for (int j = 1; j < N; ++j) { + const double sign = j % 2 == 0 ? 1 : -1; + column[j] = order == 1 ? sign / (2 * std::tan(j * h / 2)) : -sign / (2 * std::pow(std::sin(j * h / 2), 2)); + } + return column; +} + +int main() { + const double pi = std::acos(-1.0); + const double mean = 1.2660658777520084; // mean of exp(sin x) over a period, the Bessel function I_0(1) + std::cout << " N rank error of u' error of u'' antiderivative u'' - u = f\n"; + for (int N : {8, 16, 24, 32}) { + const auto D = makeCirculant(spectralColumn(N, 1)); + const auto D2 = makeCirculant(spectralColumn(N, 2)); + VectorXd shifted = spectralColumn(N, 2); + shifted[0] -= 1; + const auto D2mI = makeCirculant(shifted); // D2 - I + + const ArrayXd x = ArrayXd::LinSpaced(N, 0, 2 * pi * (N - 1) / N), s = x.sin(), c = x.cos(); + const VectorXd u = s.exp(), du = c * s.exp(), d2u = (c * c - s) * s.exp(); + std::cout << std::setw(2) << N << std::setw(5) << D.rank() << " " << std::setw(11) + << (D * u - du).cwiseAbs().maxCoeff() << " " << std::setw(12) << (D2 * u - d2u).cwiseAbs().maxCoeff() + << " " << std::setw(14) << (D.solve(du).array() + mean - s.exp()).abs().maxCoeff() << " " + << (D2mI.solve(VectorXd(d2u - u)) - u).cwiseAbs().maxCoeff() << "\n"; + } + const auto D = makeCirculant(spectralColumn(8, 1)); + std::cout << "N = 8, eigenvalues / i: " << D.eigenvalues().imag().array().round().cast<int>().transpose() << "\n"; +}
diff --git a/contrib/doc/examples/StructuredTorusHelmholtz.cpp b/contrib/doc/examples/StructuredTorusHelmholtz.cpp new file mode 100644 index 0000000..101d81e --- /dev/null +++ b/contrib/doc/examples/StructuredTorusHelmholtz.cpp
@@ -0,0 +1,46 @@ +// SPDX-FileCopyrightText: The Eigen Authors +// SPDX-License-Identifier: MPL-2.0 + +// The screened Poisson equation -(u_xx + u_yy) + kappa^2 u = f on the periodic +// unit square, five-point stencil on an n x n grid. Periodic boundaries make +// the matrix a block circulant with circulant blocks, solved by Bccb in +// O(N log N) through the 2-D FFT. The same matrix is the Kronecker sum +// (C + kappa^2 I) (+) C of the 1-D periodic second-difference circulant C, +// which BartelsStewart solves by fast diagonalization; the two agree. + +#include <contrib/Eigen/StructuredMatrices> +#include <cmath> +#include <iostream> + +using namespace Eigen; + +int main() { + const double pi = std::acos(-1.0), kappa = 2.0; + const int n = 64; + const double h = 1.0 / n; + // Stencil generator: column k holds the first column of block k. + MatrixXd G = MatrixXd::Zero(n, n); + G(0, 0) = 4 / (h * h) + kappa * kappa; + G(1, 0) = G(n - 1, 0) = G(0, 1) = G(0, n - 1) = -1 / (h * h); + const auto A = makeBccb(G); + + // u = cos(2 pi x) sin(4 pi y) is exact up to the O(h^2) stencil error. + VectorXd exact(n * n), f(n * n); + for (int j = 0; j < n; ++j) + for (int i = 0; i < n; ++i) { + exact[j * n + i] = std::cos(2 * pi * i * h) * std::sin(4 * pi * j * h); + f[j * n + i] = (20 * pi * pi + kappa * kappa) * exact[j * n + i]; + } + const VectorXd u = A.solve(f); + std::cout << "Bccb: max error " << (u - exact).cwiseAbs().maxCoeff() << "\n"; + + VectorXd column = VectorXd::Zero(n); + column[0] = 2 / (h * h); + column[1] = column[n - 1] = -1 / (h * h); + MatrixXd C; + C = makeCirculant(column); // dense, for the Kronecker sum + const auto L = makeKroneckerSum(MatrixXd(C + kappa * kappa * MatrixXd::Identity(n, n)), C); + const VectorXd v = L.solve(f); + std::cout << "KroneckerSum: max error " << (v - exact).cwiseAbs().maxCoeff() << "\n"; + std::cout << "max |u_Bccb - u_KroneckerSum|: " << (u - v).cwiseAbs().maxCoeff() << "\n"; +}