1 namespace Eigen { 2 3 /** \eigenManualPage TopicLinearAlgebraDecompositions Catalogue of dense decompositions 4 5 This page presents a catalogue of the dense matrix decompositions offered by Eigen. 6 For an introduction on linear solvers and decompositions, check this \link TutorialLinearAlgebra page \endlink. 7 To get an overview of the true relative speed of the different decomposition, 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>Soon: blocking</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>LLT</td> 92 <td>Positive definite</td> 93 <td>Very fast</td> 94 <td>Depends on condition number</td> 95 <td>-</td> 96 <td>-</td> 97 <td>Yes</td> 98 <td>Excellent</td> 99 <td>Blocking</td> 100 </tr> 101 102 <tr> 103 <td>LDLT</td> 104 <td>Positive or negative semidefinite<sup><a href="#note1">1</a></sup></td> 105 <td>Very fast</td> 106 <td>Good</td> 107 <td>-</td> 108 <td>-</td> 109 <td>Yes</td> 110 <td>Excellent</td> 111 <td><em>Soon: blocking</em></td> 112 </tr> 113 114 <tr><th class="inter" colspan="9">\n Singular values and eigenvalues decompositions</th></tr> 115 116 <tr> 117 <td>JacobiSVD (two-sided)</td> 118 <td>-</td> 119 <td>Slow (but fast for small matrices)</td> 120 <td>Proven<sup><a href="#note3">3</a></sup></td> 121 <td>Yes</td> 122 <td>Singular values/vectors, least squares</td> 123 <td>Yes (and does least squares)</td> 124 <td>Excellent</td> 125 <td>R-SVD</td> 126 </tr> 127 128 <tr class="alt"> 129 <td>SelfAdjointEigenSolver</td> 130 <td>Self-adjoint</td> 131 <td>Fast-average<sup><a href="#note2">2</a></sup></td> 132 <td>Good</td> 133 <td>Yes</td> 134 <td>Eigenvalues/vectors</td> 135 <td>-</td> 136 <td>Excellent</td> 137 <td><em>Closed forms for 2x2 and 3x3</em></td> 138 </tr> 139 140 <tr> 141 <td>ComplexEigenSolver</td> 142 <td>Square</td> 143 <td>Slow-very slow<sup><a href="#note2">2</a></sup></td> 144 <td>Depends on condition number</td> 145 <td>Yes</td> 146 <td>Eigenvalues/vectors</td> 147 <td>-</td> 148 <td>Average</td> 149 <td>-</td> 150 </tr> 151 152 <tr class="alt"> 153 <td>EigenSolver</td> 154 <td>Square and real</td> 155 <td>Average-slow<sup><a href="#note2">2</a></sup></td> 156 <td>Depends on condition number</td> 157 <td>Yes</td> 158 <td>Eigenvalues/vectors</td> 159 <td>-</td> 160 <td>Average</td> 161 <td>-</td> 162 </tr> 163 164 <tr> 165 <td>GeneralizedSelfAdjointEigenSolver</td> 166 <td>Square</td> 167 <td>Fast-average<sup><a href="#note2">2</a></sup></td> 168 <td>Depends on condition number</td> 169 <td>-</td> 170 <td>Generalized eigenvalues/vectors</td> 171 <td>-</td> 172 <td>Good</td> 173 <td>-</td> 174 </tr> 175 176 <tr><th class="inter" colspan="9">\n Helper decompositions</th></tr> 177 178 <tr> 179 <td>RealSchur</td> 180 <td>Square and real</td> 181 <td>Average-slow<sup><a href="#note2">2</a></sup></td> 182 <td>Depends on condition number</td> 183 <td>Yes</td> 184 <td>-</td> 185 <td>-</td> 186 <td>Average</td> 187 <td>-</td> 188 </tr> 189 190 <tr class="alt"> 191 <td>ComplexSchur</td> 192 <td>Square</td> 193 <td>Slow-very slow<sup><a href="#note2">2</a></sup></td> 194 <td>Depends on condition number</td> 195 <td>Yes</td> 196 <td>-</td> 197 <td>-</td> 198 <td>Average</td> 199 <td>-</td> 200 </tr> 201 202 <tr class="alt"> 203 <td>Tridiagonalization</td> 204 <td>Self-adjoint</td> 205 <td>Fast</td> 206 <td>Good</td> 207 <td>-</td> 208 <td>-</td> 209 <td>-</td> 210 <td>Good</td> 211 <td><em>Soon: blocking</em></td> 212 </tr> 213 214 <tr> 215 <td>HessenbergDecomposition</td> 216 <td>Square</td> 217 <td>Average</td> 218 <td>Good</td> 219 <td>-</td> 220 <td>-</td> 221 <td>-</td> 222 <td>Good</td> 223 <td><em>Soon: blocking</em></td> 224 </tr> 225 226 </table> 227 228 \b Notes: 229 <ul> 230 <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> 231 <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> 232 <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. 233 </ul> 234 235 \section TopicLinAlgTerminology Terminology 236 237 <dl> 238 <dt><b>Selfadjoint</b></dt> 239 <dd>For a real matrix, selfadjoint is a synonym for symmetric. For a complex matrix, selfadjoint is a synonym for \em hermitian. 240 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> 241 <dt><b>Positive/negative definite</b></dt> 242 <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$. 243 In the same vein, it is negative definite if \f$ v^* A v < 0 \f$ for any non zero vector \f$ v \f$ </dd> 244 <dt><b>Positive/negative semidefinite</b></dt> 245 <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$. 246 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> 247 248 <dt><b>Blocking</b></dt> 249 <dd>Means the algorithm can work per block, whence guaranteeing a good scaling of the performance for large matrices.</dd> 250 <dt><b>Implicit Multi Threading (MT)</b></dt> 251 <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> 252 <dt><b>Explicit Multi Threading (MT)</b></dt> 253 <dd>Means the algorithm is explicitly parallelized to take advantage of multicore processors via OpenMP.</dd> 254 <dt><b>Meta-unroller</b></dt> 255 <dd>Means the algorithm is automatically and explicitly unrolled for very small fixed size matrices.</dd> 256 <dt><b></b></dt> 257 <dd></dd> 258 </dl> 259 260 261 */ 262 263 } 264
