File size: 8,806 Bytes
90f0b29 |
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 276 |
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 rountines.</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>
*/
}
|