1namespace Eigen {
2
3/** \eigenManualPage TopicLinearAlgebraDecompositions Catalogue of dense decompositions
4
5This page presents a catalogue of the dense matrix decompositions offered by Eigen.
6For an introduction on linear solvers and decompositions, check this \link TutorialLinearAlgebra page \endlink.
7
8\section TopicLinAlgBigTable Catalogue of decompositions offered by Eigen
9
10<table class="manual-vl">
11    <tr>
12        <th class="meta"></th>
13        <th class="meta" colspan="5">Generic information, not Eigen-specific</th>
14        <th class="meta" colspan="3">Eigen-specific</th>
15    </tr>
16
17    <tr>
18        <th>Decomposition</th>
19        <th>Requirements on the matrix</th>
20        <th>Speed</th>
21        <th>Algorithm reliability and accuracy</th>
22        <th>Rank-revealing</th>
23        <th>Allows to compute (besides linear solving)</th>
24        <th>Linear solver provided by Eigen</th>
25        <th>Maturity of Eigen's implementation</th>
26        <th>Optimizations</th>
27    </tr>
28
29    <tr>
30        <td>PartialPivLU</td>
31        <td>Invertible</td>
32        <td>Fast</td>
33        <td>Depends on condition number</td>
34        <td>-</td>
35        <td>-</td>
36        <td>Yes</td>
37        <td>Excellent</td>
38        <td>Blocking, Implicit MT</td>
39    </tr>
40
41    <tr class="alt">
42        <td>FullPivLU</td>
43        <td>-</td>
44        <td>Slow</td>
45        <td>Proven</td>
46        <td>Yes</td>
47        <td>-</td>
48        <td>Yes</td>
49        <td>Excellent</td>
50        <td>-</td>
51    </tr>
52
53    <tr>
54        <td>HouseholderQR</td>
55        <td>-</td>
56        <td>Fast</td>
57        <td>Depends on condition number</td>
58        <td>-</td>
59        <td>Orthogonalization</td>
60        <td>Yes</td>
61        <td>Excellent</td>
62        <td>Blocking</td>
63    </tr>
64
65    <tr class="alt">
66        <td>ColPivHouseholderQR</td>
67        <td>-</td>
68        <td>Fast</td>
69        <td>Good</td>
70        <td>Yes</td>
71        <td>Orthogonalization</td>
72        <td>Yes</td>
73        <td>Excellent</td>
74        <td><em>Soon: blocking</em></td>
75    </tr>
76
77    <tr>
78        <td>FullPivHouseholderQR</td>
79        <td>-</td>
80        <td>Slow</td>
81        <td>Proven</td>
82        <td>Yes</td>
83        <td>Orthogonalization</td>
84        <td>Yes</td>
85        <td>Average</td>
86        <td>-</td>
87    </tr>
88
89    <tr class="alt">
90        <td>LLT</td>
91        <td>Positive definite</td>
92        <td>Very fast</td>
93        <td>Depends on condition number</td>
94        <td>-</td>
95        <td>-</td>
96        <td>Yes</td>
97        <td>Excellent</td>
98        <td>Blocking</td>
99    </tr>
100
101    <tr>
102        <td>LDLT</td>
103        <td>Positive or negative semidefinite<sup><a href="#note1">1</a></sup></td>
104        <td>Very fast</td>
105        <td>Good</td>
106        <td>-</td>
107        <td>-</td>
108        <td>Yes</td>
109        <td>Excellent</td>
110        <td><em>Soon: blocking</em></td>
111    </tr>
112
113    <tr><th class="inter" colspan="9">\n Singular values and eigenvalues decompositions</th></tr>
114
115    <tr>
116        <td>JacobiSVD (two-sided)</td>
117        <td>-</td>
118        <td>Slow (but fast for small matrices)</td>
119        <td>Excellent-Proven<sup><a href="#note3">3</a></sup></td>
120        <td>Yes</td>
121        <td>Singular values/vectors, least squares</td>
122        <td>Yes (and does least squares)</td>
123        <td>Excellent</td>
124        <td>R-SVD</td>
125    </tr>
126
127    <tr class="alt">
130        <td>Fast-average<sup><a href="#note2">2</a></sup></td>
131        <td>Good</td>
132        <td>Yes</td>
133        <td>Eigenvalues/vectors</td>
134        <td>-</td>
135        <td>Good</td>
136        <td><em>Closed forms for 2x2 and 3x3</em></td>
137    </tr>
138
139    <tr>
140        <td>ComplexEigenSolver</td>
141        <td>Square</td>
142        <td>Slow-very slow<sup><a href="#note2">2</a></sup></td>
143        <td>Depends on condition number</td>
144        <td>Yes</td>
145        <td>Eigenvalues/vectors</td>
146        <td>-</td>
147        <td>Average</td>
148        <td>-</td>
149    </tr>
150
151    <tr class="alt">
152        <td>EigenSolver</td>
153        <td>Square and real</td>
154        <td>Average-slow<sup><a href="#note2">2</a></sup></td>
155        <td>Depends on condition number</td>
156        <td>Yes</td>
157        <td>Eigenvalues/vectors</td>
158        <td>-</td>
159        <td>Average</td>
160        <td>-</td>
161    </tr>
162
163    <tr>
165        <td>Square</td>
166        <td>Fast-average<sup><a href="#note2">2</a></sup></td>
167        <td>Depends on condition number</td>
168        <td>-</td>
169        <td>Generalized eigenvalues/vectors</td>
170        <td>-</td>
171        <td>Good</td>
172        <td>-</td>
173    </tr>
174
175    <tr><th class="inter" colspan="9">\n Helper decompositions</th></tr>
176
177    <tr>
178        <td>RealSchur</td>
179        <td>Square and real</td>
180        <td>Average-slow<sup><a href="#note2">2</a></sup></td>
181        <td>Depends on condition number</td>
182        <td>Yes</td>
183        <td>-</td>
184        <td>-</td>
185        <td>Average</td>
186        <td>-</td>
187    </tr>
188
189    <tr class="alt">
190        <td>ComplexSchur</td>
191        <td>Square</td>
192        <td>Slow-very slow<sup><a href="#note2">2</a></sup></td>
193        <td>Depends on condition number</td>
194        <td>Yes</td>
195        <td>-</td>
196        <td>-</td>
197        <td>Average</td>
198        <td>-</td>
199    </tr>
200
201    <tr class="alt">
202        <td>Tridiagonalization</td>
204        <td>Fast</td>
205        <td>Good</td>
206        <td>-</td>
207        <td>-</td>
208        <td>-</td>
209        <td>Good</td>
210        <td><em>Soon: blocking</em></td>
211    </tr>
212
213    <tr>
214        <td>HessenbergDecomposition</td>
215        <td>Square</td>
216        <td>Average</td>
217        <td>Good</td>
218        <td>-</td>
219        <td>-</td>
220        <td>-</td>
221        <td>Good</td>
222        <td><em>Soon: blocking</em></td>
223    </tr>
224
225</table>
226
227\b Notes:
228<ul>
229<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>
230<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>
231<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.
232</ul>
233
234\section TopicLinAlgTerminology Terminology
235
236<dl>
238    <dd>For a real matrix, selfadjoint is a synonym for symmetric. For a complex matrix, selfadjoint is a synonym for \em hermitian.
239        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>
240  <dt><b>Positive/negative definite</b></dt>
241    <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$.
242        In the same vein, it is negative definite if \f$v^* A v < 0 \f$ for any non zero vector \f$v \f$ </dd>
243  <dt><b>Positive/negative semidefinite</b></dt>
244    <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$.
245        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>
246
247  <dt><b>Blocking</b></dt>
248    <dd>Means the algorithm can work per block, whence guaranteeing a good scaling of the performance for large matrices.</dd>
262