[136] | 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 |
|
---|
| 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">
|
---|
| 128 | <td>SelfAdjointEigenSolver</td>
|
---|
| 129 | <td>Self-adjoint</td>
|
---|
| 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>
|
---|
| 164 | <td>GeneralizedSelfAdjointEigenSolver</td>
|
---|
| 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>
|
---|
| 203 | <td>Self-adjoint</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>
|
---|
| 237 | <dt><b>Selfadjoint</b></dt>
|
---|
| 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>
|
---|
| 249 | <dt><b>Implicit Multi Threading (MT)</b></dt>
|
---|
| 250 | <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>
|
---|
| 251 | <dt><b>Explicit Multi Threading (MT)</b></dt>
|
---|
| 252 | <dd>Means the algorithm is explicitely parallelized to take advantage of multicore processors via OpenMP.</dd>
|
---|
| 253 | <dt><b>Meta-unroller</b></dt>
|
---|
| 254 | <dd>Means the algorithm is automatically and explicitly unrolled for very small fixed size matrices.</dd>
|
---|
| 255 | <dt><b></b></dt>
|
---|
| 256 | <dd></dd>
|
---|
| 257 | </dl>
|
---|
| 258 |
|
---|
| 259 | */
|
---|
| 260 |
|
---|
| 261 | }
|
---|