INTLAB - INTerval LABoratory
INTLAB is the Matlab toolbox for reliable computing and self-validating algorithms. It comprises of
- self-validating methods for
- dense linear systems (also inner inclusions and structured matrices)
- sparse s.p.d. linear systems
- systems of nonlinear equations (including unconstrained optimization)
- roots of univariate and multivariate nonlinear equations (simple and clusters)
- eigenvalue problems (simple and clusters, also inner inclusions and structured matrices)
- generalized eigenvalue problems (simple and clusters)
- quadrature for univariate functions
- univariate polynomial zeros (simple and clusters)
- interval arithmetic for real and complex data including vectors and matrices (very fast)
- interval arithmetic for real and complex sparse matrices (very fast)
- automatic differentiation (forward mode, vectorized computations, fast)
- Gradients (to solve systems of nonlinear equations)
- Hessians (for global optimization)
- Taylor series for univariate functions
- automatic slopes (sequential approach, slow for many variables)
- verified integration of (simple) univariate functions
- univariate and multivariate (interval) polynomials
- rigorous real interval standard functions (fast, very accurate, ~3 ulps)
- rigorous complex interval standard functions (fast, rigorous, but not necessarily sharp inclusions)
- rigorous input/output (outer and inner inclusions)
- accurate summation, dot product and matrix-vector residuals (interpreted, reference implementation, slow)
- multiple precision interval arithmetic with error bounds (does the job, slow)
INTLAB has several thousand users in more than 50 countries. INTLAB is used in many areas, from verification of chaos to population biology, from controller design to computer-assisted proofs, from PDEs to Petri Nets (cf. some selected Refences to INTLAB). Over the years many colleagues helped to improve INTLAB, my dearest thanks to them!
The main focus of INTLAB is to produce reliable results. Any result is proved to be true under any circumstances, in particular covering rounding errors and all error terms. The philosophy of INTLAB is that everything is written in Matlab code to assure best portability. INTLAB extensively uses BLAS routines. This assures fast computing times, comparable to pure floating point arithmetic. Interval vector and matrix operations are very fast in INTLAB; however, nonlinear computations and loops may slow down the system significantly due to interpretation overhead and extensive use of the operator concept.
Further reading- My 163-page review paper Verification methods: Rigorous results using floating-point arithmetic in Acta Numerica includes many examples based on INTLAB.
- Five out of the ten solutions to the SIAM 10x10-digit challenge in the book by Bornemann et al. are verified by INTLAB.
- The SIAM-book Introduction to Interval Analysis by Ramon E. Moore, R. Baker Kearfott, Michael J. Cloud is also based on INTLAB.
- The Springer-book Nichtlineare Optimierung, Theorie, Numerik und Experimente by R. Reinhardt, A. Hoffmann and T. Gerlach uses the Gradient and Hessian toolbox of INTLAB.
- Hargreaves' thesis (supervisor Nicholas J. Higham) Interval Analysis in Matlab is a nice introduction into parts of INTLAB together with a tutorial. Moreover, some routines written by Hargreaves in INTLAB are presented, among them an algorithm to find all zeros of a nonlinear function within a box and a computation of Viswanath's constant, the common limit of random Fibonacci recurrences.
- Tiago Montanher wrote INTSOLVER, an INTLAB based solver for Global Optimization.
- A large collection of verification algorithms written in Matlab/INTLAB is Rohn's VERSOFT.
Following are some timings on a Laptop using Intel i7 M640 2.8 GHz. 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.114 | 0.35 | 0.43 | 1.4 | |||||
| 2000 | 0.86 | 1.8 | 2.7 | 8.3 | |||||
| 5000 | 14 | 26 | 43 | 112 | |||||
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.081 | 0.59 | 0.76 | 0.96 | |||||
| 2000 | 0.50 | 2.9 | 3.5 | 5.4 | |||||
| 5000 | 6.0 | 35 | 39 | 62 | |||||
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.047 | 0.0064 | 0.068 | 0.075 | |||||
| 2000 | 0.34 | 0.023 | 0.26 | 0.27 | |||||
| 5000 | 5.3 | 0.18 | 1.7 | 1.7 | |||||
| 10000 | 42 | 1.09 | 8.1 | 7.7 | |||||
| 20000 | - | 7.1 | 38 | 39 | |||||
| 50000 | - | 103 | 612 | 604 | |||||
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.7 | 2615 | 0.24 | 178 | 7.0e-015 | 0.056 | |||||||
| 100 | 3.7 | 8678 | 0.26 | 379 | 1.0e-014 | 0.059 | |||||||
| 300 | 28 | 29514 | 0.39 | 1180 | 1.9e-014 | 0.078 | |||||||
| 1000 | 2359 | 100500 | 1.3 | 3984 | 3.5e-014 | 0.22 | |||||||
| 3000 | - | - | 8.0 | 11995 | 6.1e-014 | 1.16 | |||||||
| 10000 | - | - | 83 | 40034 | 1.1e-013 | 10.5 | |||||||
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.
INTLAB includes a linear system solver to treat extremely ill-conditioned linear systems. It is based on a method I designed in about 1984 and uses error-free transformations for extra-precise residual calculations. Usually the method works until condition numbers of about 1030, occasionally for much larger condition numbers. The following test uses Matlab's invhilb and the right hand side ones(n,1), where the displayed condition number is the true 2-norm condition number.
Ill-coonditioned linear systems, time [sec]
| true | linear system | maximum | ||||
| dimension | cond. number | verified [sec] | rel.error | |||
| 10 | 1.6e+013 | 0.103 | 2.0e-015 | |||
| 20 | 9.4e+026 | 0.51 | 5.2e-013 | |||
| 30 | 4.8e+042 | 0.91 | 2.4e-012 | |||
| 40 | 3.1e+057 | 1.8 | 7.4e-008 | |||
| 50 | 5.0e+072 | 2.7 | 1.7e-007 | |||
| 100 | 3.1e+148 | 11.0 | 6.3e-002 | |||
If you are interested in extremely ill-conditioned examples, consider
| A = [ | -5046135670319638, | -3871391041510136, | -5206336348183639, | -6745986988231149 ; |
| -640032173419322, | 8694411469684959, | -564323984386760, | -2807912511823001 ; | |
| -16935782447203334, | -18752427538303772, | -8188807358110413, | -14820968618548534 ; | |
| -1069537498856711, | -14079150289610606, | 7074216604373039, | 7257960283978710 ]; |
For details, see randmat.m. With a condition number of about 1065, this is too much for the algorithm implemented in INTLAB.
Most routines in INTLAB are self-explaining and/or information can be obtained by the Matlab help command (cf. also readme.txt for more information).
There are a number of demo files for different INTLAB toolboxes. Matlab demos are not executed, but the results are dispayed. You may view the demos directly, or copy the demos directory file into your Matlab working directory, change your directory by "cd demos" and call "demointlab".
INTLAB LICENSE INFORMATION
Copyright (c) 1998 - 2013 Siegfried M. Rump @ TUHH, Institute for Reliable Computing
All rights reserved.
If you use INTLAB in publications, please include the reference S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.
===> INTLAB can be downloaded and used for private and for purely academic purposes, and for commercial purposes within a company. In any case proper reference has to be given acknowledging that the software package INTLAB has been developed by Siegfried M. Rump at Hamburg University of Technology, Germany.
===> The use of INTLAB in a commercial product which needs INTLAB or parts of INTLAB to work properly requires a special license. This is independent of whether the commercial product is used privately or for commercial purposes. To obtain such a license contact the author Siegfried M. Rump (@tuhh.de).
===> Neither the name of the university nor the name of the author may be used to endorse or promote products derived with or from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATIONS, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
DISCLAIMER: Extensive tests have been performed to ensure reliability of the algorithms. However, neither an error-free processor nor an error-free program can be guaranteed.
INTLAB under Windows operating system:
Windows 32-bit: The package is thoroughly tested and works successfully with Matlab versions 7.0, 7.2 (R2006a), R2006b, R2007a, R2007b, R2008a, R2009b, R2010a, R2010b, R2011a, R2011b, R2012a and R2012b. Old Matlab releases 5.3, 6.0, 6.5 and 6.5.1 can be used with a restricted range of applicability. Switching the rounding fails under Windows 32-bit Matlab versions 7.0.1, 7.0.4, 7.1, R2008b and R2009a.
Windows 64-bit: The package is thoroughly tested and works successfully with Matlab versions R2007b, R2008a, R2008b, R2009a, R2009b, R2010a, R2010b, R2011a, R2011b, R2012a and R2012b.
INTLAB under Linux operating system:
Linux 32-bit: The package is thoroughly tested and works successfully with Matlab versions R2007a, R2007b, R2008a, R2008b, R2009a, R2009b, R2010a, R2010b, R2011a, R2011b, and R2012a. The latter Matlab release R2012a is the last supporting Linux 32-bit operating system.
Linux 64-bit: The package is thoroughly tested and works successfully with Matlab versions R2009a, R2009b, R2010a, R2010b, R2011a, R2011b, R2012a and R2012b.
Other operating systems:
Users report that INTLAB works as well under other operating systems, in particular Unix and MAC, however, I have no possibility to test this myself.
Known Matlab bugs:
In Matlab Version 7.2 (2006a) there is a problem on some operating systems with constant*sparse (independent of INTLAB). The result is correct, but it may take very long.
In Matlab releases R2006b and R2009b on some operating systems there are known bugs (delivering wrong results, independent of INTLAB), and I recommend to use other releases.