mirror of
https://gitlab.com/libeigen/eigen.git
synced 2026-04-10 11:34:33 +08:00
311 lines
10 KiB
Plaintext
311 lines
10 KiB
Plaintext
namespace Eigen {
|
|
|
|
/** \eigenManualPage TopicLinearAlgebraDecompositions Catalogue of dense decompositions
|
|
|
|
This page presents a catalogue of the dense matrix decompositions offered by Eigen.
|
|
For an introduction on linear solvers and decompositions, check this \link TutorialLinearAlgebra page \endlink.
|
|
To get an overview of the true relative speed of the different decompositions, check this \link DenseDecompositionBenchmark benchmark \endlink.
|
|
|
|
\section TopicLinAlgBigTable Catalogue of decompositions offered by Eigen
|
|
|
|
<table class="manual-vl">
|
|
<tr>
|
|
<th class="meta"></th>
|
|
<th class="meta" colspan="5">Generic information, not Eigen-specific</th>
|
|
<th class="meta" colspan="3">Eigen-specific</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<th>Decomposition</th>
|
|
<th>Requirements on the matrix</th>
|
|
<th>Speed</th>
|
|
<th>Algorithm reliability and accuracy</th>
|
|
<th>Rank-revealing</th>
|
|
<th>Allows to compute (besides linear solving)</th>
|
|
<th>Linear solver provided by Eigen</th>
|
|
<th>Maturity of Eigen's implementation</th>
|
|
<th>Optimizations</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>PartialPivLU</td>
|
|
<td>Invertible</td>
|
|
<td>Fast</td>
|
|
<td>Depends on condition number</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>Yes</td>
|
|
<td>Excellent</td>
|
|
<td>Blocking, Implicit MT</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>FullPivLU</td>
|
|
<td>-</td>
|
|
<td>Slow (no blocking)</td>
|
|
<td>Proven</td>
|
|
<td>Yes</td>
|
|
<td>Rank, kernel, image</td>
|
|
<td>Yes</td>
|
|
<td>Excellent</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>HouseholderQR</td>
|
|
<td>-</td>
|
|
<td>Fast</td>
|
|
<td>Depends on condition number</td>
|
|
<td>-</td>
|
|
<td>Orthogonalization</td>
|
|
<td>Yes</td>
|
|
<td>Excellent</td>
|
|
<td>Blocking</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>ColPivHouseholderQR</td>
|
|
<td>-</td>
|
|
<td>Fast</td>
|
|
<td>Good</td>
|
|
<td>Yes</td>
|
|
<td>Orthogonalization</td>
|
|
<td>Yes</td>
|
|
<td>Excellent</td>
|
|
<td><em>-</em></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>FullPivHouseholderQR</td>
|
|
<td>-</td>
|
|
<td>Slow (no blocking)</td>
|
|
<td>Proven</td>
|
|
<td>Yes</td>
|
|
<td>Orthogonalization</td>
|
|
<td>Yes</td>
|
|
<td>Average</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>CompleteOrthogonalDecomposition</td>
|
|
<td>-</td>
|
|
<td>Fast</td>
|
|
<td>Good</td>
|
|
<td>Yes</td>
|
|
<td>Orthogonalization</td>
|
|
<td>Yes</td>
|
|
<td>Excellent</td>
|
|
<td><em>-</em></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>LLT</td>
|
|
<td>Positive definite</td>
|
|
<td>Very fast</td>
|
|
<td>Depends on condition number</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>Yes</td>
|
|
<td>Excellent</td>
|
|
<td>Blocking</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>LDLT</td>
|
|
<td>Positive or negative semidefinite<sup><a href="#note1">1</a></sup></td>
|
|
<td>Very fast</td>
|
|
<td>Good</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>Yes</td>
|
|
<td>Excellent</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr><th class="inter" colspan="9">\n Singular values and eigenvalues decompositions</th></tr>
|
|
|
|
<tr>
|
|
<td>BDCSVD (divide \& conquer)</td>
|
|
<td>-</td>
|
|
<td>One of the fastest SVD algorithms</td>
|
|
<td>Excellent</td>
|
|
<td>Yes</td>
|
|
<td>Singular values/vectors, least squares</td>
|
|
<td>Yes (and does least squares)</td>
|
|
<td>Excellent</td>
|
|
<td>Blocked bidiagonalization</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>JacobiSVD (two-sided)</td>
|
|
<td>-</td>
|
|
<td>Slow (but fast for small matrices)</td>
|
|
<td>Proven<sup><a href="#note3">3</a></sup></td>
|
|
<td>Yes</td>
|
|
<td>Singular values/vectors, least squares</td>
|
|
<td>Yes (and does least squares)</td>
|
|
<td>Excellent</td>
|
|
<td>R-SVD</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>SelfAdjointEigenSolver</td>
|
|
<td>Self-adjoint</td>
|
|
<td>Fast-average<sup><a href="#note2">2</a></sup></td>
|
|
<td>Good</td>
|
|
<td>Yes</td>
|
|
<td>Eigenvalues/vectors</td>
|
|
<td>-</td>
|
|
<td>Excellent</td>
|
|
<td><em>Closed forms for 2x2 and 3x3</em></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>ComplexEigenSolver</td>
|
|
<td>Square</td>
|
|
<td>Slow-very slow<sup><a href="#note2">2</a></sup></td>
|
|
<td>Depends on condition number</td>
|
|
<td>Yes</td>
|
|
<td>Eigenvalues/vectors</td>
|
|
<td>-</td>
|
|
<td>Average</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>EigenSolver</td>
|
|
<td>Square and real</td>
|
|
<td>Average-slow<sup><a href="#note2">2</a></sup></td>
|
|
<td>Depends on condition number</td>
|
|
<td>Yes</td>
|
|
<td>Eigenvalues/vectors</td>
|
|
<td>-</td>
|
|
<td>Average</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>GeneralizedSelfAdjointEigenSolver</td>
|
|
<td>Square</td>
|
|
<td>Fast-average<sup><a href="#note2">2</a></sup></td>
|
|
<td>Depends on condition number</td>
|
|
<td>-</td>
|
|
<td>Generalized eigenvalues/vectors</td>
|
|
<td>-</td>
|
|
<td>Good</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr><th class="inter" colspan="9">\n Helper decompositions</th></tr>
|
|
|
|
<tr>
|
|
<td>RealSchur</td>
|
|
<td>Square and real</td>
|
|
<td>Average-slow<sup><a href="#note2">2</a></sup></td>
|
|
<td>Depends on condition number</td>
|
|
<td>Yes</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>Average</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>ComplexSchur</td>
|
|
<td>Square</td>
|
|
<td>Slow-very slow<sup><a href="#note2">2</a></sup></td>
|
|
<td>Depends on condition number</td>
|
|
<td>Yes</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>Average</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr class="alt">
|
|
<td>Tridiagonalization</td>
|
|
<td>Self-adjoint</td>
|
|
<td>Fast</td>
|
|
<td>Good</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>Good</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td>HessenbergDecomposition</td>
|
|
<td>Square</td>
|
|
<td>Average</td>
|
|
<td>Good</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>-</td>
|
|
<td>Good</td>
|
|
<td>-</td>
|
|
</tr>
|
|
|
|
</table>
|
|
|
|
\b Notes:
|
|
<ul>
|
|
<li><a name="note1">\b 1: </a>There exist two variants of the LDLT algorithm. Eigen's one produces a pure diagonal D matrix, and therefore it cannot handle indefinite matrices, unlike Lapack's one which produces a block diagonal D matrix.</li>
|
|
<li><a name="note2">\b 2: </a>Eigenvalues, SVD and Schur decompositions rely on iterative algorithms. Their convergence speed depends on how well the eigenvalues are separated.</li>
|
|
<li><a name="note3">\b 3: </a>Our JacobiSVD is two-sided, making for proven and optimal precision for square matrices. For non-square matrices, we have to use a QR preconditioner first. The default choice, ColPivHouseholderQR, is already very reliable, but if you want it to be proven, use FullPivHouseholderQR instead.</li>
|
|
</ul>
|
|
|
|
\section TopicLinAlgPracticalGuidance Practical guidance
|
|
|
|
The following recommendations apply to the most common use cases:
|
|
|
|
\li <b>Symmetric positive definite systems:</b> Use \b LLT. It is the fastest solver and has excellent
|
|
numerical properties for this class of problems. For semidefinite or nearly singular symmetric systems,
|
|
use \b LDLT.
|
|
\li <b>General invertible systems:</b> Use \b PartialPivLU. It uses cache-friendly blocking and implicit
|
|
multi-threading, making it the fastest general-purpose solver. Partial pivoting is sufficient for
|
|
virtually all practical problems.
|
|
\li <b>Least squares (over- or under-determined systems):</b> Use \b CompleteOrthogonalDecomposition as
|
|
the default. Like the SVD, it robustly computes the minimum-norm solution for rank-deficient and
|
|
under-determined problems, but at QR-like speed. Use \b BDCSVD when you also need singular values
|
|
or vectors, not just the least squares solution.
|
|
\li <b>Full-rank least squares (overdetermined systems):</b> When the matrix is known to be full rank,
|
|
\b HouseholderQR is the fastest option. For very tall and skinny well-conditioned matrices,
|
|
solving via the normal equations with \b LLT can be faster still.
|
|
\li <b>FullPivLU and FullPivHouseholderQR</b> use complete pivoting, which prevents the use of
|
|
cache-friendly blocking algorithms and makes them significantly slower than their partial/column
|
|
pivoting counterparts. In practice, complete pivoting rarely provides meaningful accuracy benefits.
|
|
These decompositions are primarily useful for debugging, pedagogy, or the very rare case
|
|
where column pivoting is insufficient.
|
|
|
|
\section TopicLinAlgTerminology Terminology
|
|
|
|
<dl>
|
|
<dt><b>Selfadjoint</b></dt>
|
|
<dd>For a real matrix, selfadjoint is a synonym for symmetric. For a complex matrix, selfadjoint is a synonym for \em hermitian.
|
|
More generally, a matrix \f$ A \f$ is selfadjoint if and only if it is equal to its adjoint \f$ A^* \f$. The adjoint is also called the \em conjugate \em transpose. </dd>
|
|
<dt><b>Positive/negative definite</b></dt>
|
|
<dd>A selfadjoint matrix \f$ A \f$ is positive definite if \f$ v^* A v > 0 \f$ for any non zero vector \f$ v \f$.
|
|
In the same vein, it is negative definite if \f$ v^* A v < 0 \f$ for any non zero vector \f$ v \f$ </dd>
|
|
<dt><b>Positive/negative semidefinite</b></dt>
|
|
<dd>A selfadjoint matrix \f$ A \f$ is positive semi-definite if \f$ v^* A v \ge 0 \f$ for any non zero vector \f$ v \f$.
|
|
In the same vein, it is negative semi-definite if \f$ v^* A v \le 0 \f$ for any non zero vector \f$ v \f$ </dd>
|
|
|
|
<dt><b>Blocking</b></dt>
|
|
<dd>Means the algorithm can work per block, whence guaranteeing a good scaling of the performance for large matrices.</dd>
|
|
<dt><b>Implicit Multi Threading (MT)</b></dt>
|
|
<dd>Means the algorithm can take advantage of multicore processors via OpenMP. "Implicit" means the algorithm itself is not parallelized, but that it relies on parallelized matrix-matrix product routines.</dd>
|
|
<dt><b>Explicit Multi Threading (MT)</b></dt>
|
|
<dd>Means the algorithm is explicitly parallelized to take advantage of multicore processors via OpenMP.</dd>
|
|
<dt><b>Meta-unroller</b></dt>
|
|
<dd>Means the algorithm is automatically and explicitly unrolled for very small fixed size matrices.</dd>
|
|
<dt><b></b></dt>
|
|
<dd></dd>
|
|
</dl>
|
|
|
|
|
|
*/
|
|
|
|
}
|