Institute for Reliable Computing
Head: Prof. Dr. Siegfried M. Rump
Following are some timings on an Intel(R) Xeon(R) CPU E5-1620 with 3.6 GHz using Matlab R2012b on Windows 7 (64 bit) operating system. The source code for the test is here. We start with matrix multiplication and compare the pure floating-point with the verified product, the latter for point data (data without tolerance) and interval data. Note this is comparing apples and oranges: pure floating-point only gives an approximation whereas the latter algorithms provide results which are verified to be correct.
Matrix multiplication, time [sec]
| pure | verified | verified | verified | ||||||
| dimension | fl-pt | A*A | A*intA | intA*intA | |||||
| 1000 | 0.028 | 0.059 | 0.098 | 0.13 | |||||
| 2000 | 0.24 | 0.48 | 0.71 | 0.92 | |||||
| 5000 | 3.1 | 6.1 | 9.1 | 12.1 | |||||
| 10000 | 22 | 45 | 67 | 86 | |||||
INTLAB is optimized for fast execution without sacrifycing the correctness of the results. For example, the routine mtimes.m for matrix multiplication consists of more than 700 lines of Matlab code (without comments). The timing factor is between 2 and 4 compared to the Matlab (pure fl-pt) multiplication.
Next we show timings for dense linear systems. Here an extra-precise residual iteration is available. To stay with our philosophy to use only Matlab code, the latter is a Matlab implementation, suffering from interpretation overhead. Fortunately only matrix-vector multiplications use extra-precise residuals, so the timing factor is between 5 and 10 compared to Matlab's backslash.
Dense linear systems (up to factor 2 faster than previous version), time [sec]
| pure | verified | verified | verified | ||||||
| dimension | fl-pt | A\b | high acc. A\b | intA\intb | |||||
| 1000 | 0.022 | 0.20 | 0.23 | 0.28 | |||||
| 2000 | 0.13 | 1.11 | 1.14 | 1.5 | |||||
| 5000 | 1.4 | 9.7 | 10.5 | 16 | |||||
| 10000 | 8.9 | 62 | 63 | 114 | |||||
Fast and competitive algorithms for sparse linear systems basically exist only for the symmetric definite case. INTLAB applies some symmetric preordering using symamd.m, Matlab's backslash does not. Therefore A\b is very slow without preordering. With preordering the timing factor to pure floating-point is roughly 8. Recall that again we compare apples and oranges.
Sparse s.p.d. linear systems (approx. 10 nonzero elements per row), time [sec]
| pure | symand | verified | verified | ||||||
| dimension | fl-pt | fl-fp | A\b | intA\intb | |||||
| 1000 | 0.033 | 0.0044 | 0.060 | 0.034 | |||||
| 2000 | 0.24 | 0.011 | 0.13 | 0.14 | |||||
| 5000 | 3.3 | 0.058 | 1.07 | 1.07 | |||||
| 10000 | 23 | 0.29 | 5.0 | 5.0 | |||||
| 20000 | - | 1.6 | 22 | 24 | |||||
| 50000 | - | 19 | 185 | 192 | |||||
Sometimes INTLAB is faster than pure floating-point. There are such examples for quadrature,
see demoquad in INTLAB. The following is an
optimization problem listed in Coconut. INTLAB solves the problem by finding a root
of the nxn nonlinear system ∇ f(x)=0
using the Hessian toolbox. An inclusion of a stationary point is computed, and by verifying
the Hessian at this point to be positive definite, it is proved to be a local minimum.
Note that in fact the Hessian evaluated at the
| fminsearch | local | nonlin.system | local | maximum | verification | ||||||||
| dimension | fl-pt [sec] | minimum | verefied [sec] | minimum | rel.error | pos.def. | |||||||
| 50 | 1.3 | 3181 | 0.38 | 178 | 7.0e-015 | 0.042 | |||||||
| 100 | 2.8 | 6733 | 0.116 | 379 | 1.0e-014 | 0.022 | |||||||
| 300 | 19 | 29342 | 0.16 | 1180 | 1.9e-014 | 0.028 | |||||||
| 1000 | 1243 | 100655 | 0.69 | 3984 | 3.5e-014 | 0.096 | |||||||
| 3000 | - | - | 5.0 | 11995 | 6.1e-014 | 0.64 | |||||||
| 10000 | - | - | 56 | 40034 | 1.1e-013 | 7.0 | |||||||
As can be seen the Matlab's fminsearch.m is much slower than the verified nonlinear solver. The comparison is not entirely fair because Matlab uses a Nelder-Mead search without derivatives.
Institute for Reliable Computing
Hamburg University of Technology
Am Schwarzenberg-Campus 3
21071 Hamburg
Germany