1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
|
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</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>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><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 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>
*/
}
|
