This page presents a speed comparison of the dense matrix decompositions offered by Eigen for a wide range of square matrices and overconstrained problems.
For a more general overview on the features and numerical robustness of linear solvers and decompositions, check this table .
This benchmark has been run on a laptop equipped with an Intel core i7 @ 2,6 GHz, and compiled with clang with AVX and FMA instruction sets enabled but without multi-threading. It uses single precision float numbers. For double, you can get a good estimate by multiplying the timings by a factor 2.
The square matrices are symmetric, and for the overconstrained matrices, the reported timmings include the cost to compute the symmetric covariance matrix \( A^T A \) for the first four solvers based on Cholesky and LU, as denoted by the * symbol (top-right corner part of the table). Timings are in milliseconds, and factors are relative to the LLT decomposition which is the fastest but also the least general and robust.
| solver/size | 8x8 | 100x100 | 1000x1000 | 4000x4000 | 10000x8 | 10000x100 | 10000x1000 | 10000x4000 |
|---|---|---|---|---|---|---|---|---|
| LLT | 0.05 | 0.42 | 5.83 | 374.55 | 6.79 * | 30.15 * | 236.34 * | 3847.17 * |
| LDLT | 0.07 (x1.3) | 0.65 (x1.5) | 26.86 (x4.6) | 2361.18 (x6.3) | 6.81 (x1) * | 31.91 (x1.1) * | 252.61 (x1.1) * | 5807.66 (x1.5) * |
| PartialPivLU | 0.08 (x1.5) | 0.69 (x1.6) | 15.63 (x2.7) | 709.32 (x1.9) | 6.81 (x1) * | 31.32 (x1) * | 241.68 (x1) * | 4270.48 (x1.1) * |
| FullPivLU | 0.1 (x1.9) | 4.48 (x10.6) | 281.33 (x48.2) | - | 6.83 (x1) * | 32.67 (x1.1) * | 498.25 (x2.1) * | - |
| HouseholderQR | 0.19 (x3.5) | 2.18 (x5.2) | 23.42 (x4) | 1337.52 (x3.6) | 34.26 (x5) | 129.01 (x4.3) | 377.37 (x1.6) | 4839.1 (x1.3) |
| ColPivHouseholderQR | 0.23 (x4.3) | 2.23 (x5.3) | 103.34 (x17.7) | 9987.16 (x26.7) | 36.05 (x5.3) | 163.18 (x5.4) | 2354.08 (x10) | 37860.5 (x9.8) |
| CompleteOrthogonalDecomposition | 0.23 (x4.3) | 2.22 (x5.2) | 99.44 (x17.1) | 10555.3 (x28.2) | 35.75 (x5.3) | 169.39 (x5.6) | 2150.56 (x9.1) | 36981.8 (x9.6) |
| FullPivHouseholderQR | 0.23 (x4.3) | 4.64 (x11) | 289.1 (x49.6) | - | 69.38 (x10.2) | 446.73 (x14.8) | 4852.12 (x20.5) | - |
| JacobiSVD | 1.01 (x18.6) | 71.43 (x168.4) | - | - | 113.81 (x16.7) | 1179.66 (x39.1) | - | - |
| BDCSVD | 1.07 (x19.7) | 21.83 (x51.5) | 331.77 (x56.9) | 18587.9 (x49.6) | 110.53 (x16.3) | 397.67 (x13.2) | 2975 (x12.6) | 48593.2 (x12.6) |
*: This decomposition do not support direct least-square solving for over-constrained problems, and the reported timing include the cost to form the symmetric covariance matrix \( A^T A \).
Observations:
The above table has been generated by the bench/dense_solvers.cpp file, feel-free to hack it to generate a table matching your hardware, compiler, and favorite problem sizes.