aboutsummaryrefslogtreecommitdiff
path: root/doc/TopicLinearAlgebraDecompositions.dox
diff options
context:
space:
mode:
Diffstat (limited to 'doc/TopicLinearAlgebraDecompositions.dox')
-rw-r--r--doc/TopicLinearAlgebraDecompositions.dox260
1 files changed, 260 insertions, 0 deletions
diff --git a/doc/TopicLinearAlgebraDecompositions.dox b/doc/TopicLinearAlgebraDecompositions.dox
new file mode 100644
index 000000000..faa564b93
--- /dev/null
+++ b/doc/TopicLinearAlgebraDecompositions.dox
@@ -0,0 +1,260 @@
+namespace Eigen {
+
+/** \page TopicLinearAlgebraDecompositions Linear algebra and decompositions
+
+
+\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</td>
+ <td>Proven</td>
+ <td>Yes</td>
+ <td>-</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>Soon: blocking</em></td>
+ </tr>
+
+ <tr>
+ <td>FullPivHouseholderQR</td>
+ <td>-</td>
+ <td>Slow</td>
+ <td>Proven</td>
+ <td>Yes</td>
+ <td>Orthogonalization</td>
+ <td>Yes</td>
+ <td>Average</td>
+ <td>-</td>
+ </tr>
+
+ <tr class="alt">
+ <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>
+ <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><em>Soon: blocking</em></td>
+ </tr>
+
+ <tr><th class="inter" colspan="9">\n Singular values and eigenvalues decompositions</th></tr>
+
+ <tr>
+ <td>JacobiSVD (two-sided)</td>
+ <td>-</td>
+ <td>Slow (but fast for small matrices)</td>
+ <td>Excellent-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>Good</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><em>Soon: blocking</em></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><em>Soon: blocking</em></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.
+</ul>
+
+\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 algortihm itself is not parallelized, but that it relies on parallelized matrix-matrix product rountines.</dd>
+ <dt><b>Explicit Multi Threading (MT)</b></dt>
+ <dd>Means the algorithm is explicitely 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>
+
+*/
+
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-12 17:44:50 +0000