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