Interval package: Difference between revisions

Jump to navigation Jump to search
455 bytes removed ,  14 January 2015
m
Removed dependency to fenv package
(→‎What to expect: Removed fenv package)
m (Removed dependency to fenv package)
Line 1: Line 1:
The [https://sourceforge.net/p/octave/interval/ interval package] provides data types and fundamental operations for real valued interval arithmetic based on the common floating-point format “binary64” a. k. a. double-precision.  It aims to be standard compliant with the (upcoming) [http://standards.ieee.org/develop/project/1788.html IEEE 1788] and therefore implements the ''set-based'' interval arithmetic flavor.  '''Interval arithmetic''' produces mathematically proven numerical results.
The [https://sourceforge.net/p/octave/interval/ interval package] provides data types and fundamental operations for real valued interval arithmetic based on the common floating-point format “binary64” a. k. a. double-precision.  It aims to be standard compliant with the (upcoming) [http://standards.ieee.org/develop/project/1788.html IEEE 1788] and therefore implements the ''set-based'' interval arithmetic flavor.  '''Interval arithmetic''' produces mathematically proven numerical results.


Warning: The package has not yet been released. If you want to experience the development version, you may (1) install the (currently deprecated) [http://octave.sourceforge.net/fenv/ fenv package], (2) download a [https://sourceforge.net/p/octave/interval/ci/default/tarball snapshot version of the interval package], (3) install the [http://www.mpfr.org/mpfr-current/#download development library of MPFR] for your system, (4) execute <code>make install</code> in the <code>src/</code> subfolder, (5) navigate to the <code>inst/</code> subfolder and run octave.
Warning: The package has not yet been released. If you want to experience the development version, you may (1) download a [https://sourceforge.net/p/octave/interval/ci/default/tarball snapshot version of the interval package], (2) install the [http://www.mpfr.org/mpfr-current/#download development library of MPFR] for your system, (3) execute <code>make install</code> in the <code>src/</code> subfolder, (5) navigate to the <code>inst/</code> subfolder and run octave.


== Motivation ==
== Motivation ==
Line 46: Line 46:


''Why is the interval package slow?''
''Why is the interval package slow?''
All arithmetic interval operations are simulated in high-level octave language using C99 floating-point routines, which is a lot slower than hardware implementations [https://books.google.de/books?id=JTc4XdXFnQIC&pg=PA61]. Building interval arithmetic operations from floating-point routines is easy for simple monotonic functions, e. g., addition and subtraction, but is complex for others, e. g., [http://exp.ln0.de/heimlich-power-2011.htm interval power function], atan2, or [[#Reverse_arithmetic_operations|reverse functions]]. For some interval operations it is not even possible to rely on floating-point routines, since not all required routines are available in C99 or BLAS.
All arithmetic interval operations are simulated in high-level octave language using C99 floating-point routines or multi-precision floating-point routines, which is a lot slower than hardware implementations [https://books.google.de/books?id=JTc4XdXFnQIC&pg=PA61]. Building interval arithmetic operations from floating-point routines is easy for simple monotonic functions, e. g., addition and subtraction, but is complex for others, e. g., [http://exp.ln0.de/heimlich-power-2011.htm interval power function], atan2, or [[#Reverse_arithmetic_operations|reverse functions]]. For some interval operations it is not even possible to rely on floating-point routines, since not all required routines are available in C99 or BLAS.
 
For example, for some tightly rounded results of vector and matrix operations the interval package has to simulate a [http://books.google.de/books?hl=de&id=I7X9EVfeV5EC&q=accumulator Kulisch accumulator], which introduces a computational overhead of factor 10. However, the Kulisch accumulator could be implemented in hardware and then outperform floating-point routines.


Great algorithms and optimizations exist for matrix arithmetic in GNU octave. Good interval versions of these still have to be found and implemented.
Great algorithms and optimizations exist for matrix arithmetic in GNU octave. Good interval versions of these still have to be found and implemented.
Line 55: Line 53:
Some basic operations are provided by the C library on common platforms with directed rounding and correctly rounded result: plus, minus, division, multiplication and square root. All other GNU Octave arithmetic functions are not guaranteed to produce accurate results, because they are based on C99 floating-point routines [http://www.gnu.org/software/libc/manual/html_node/Errors-in-Math-Functions.html#Errors-in-Math-Functions]. Their results depend on hardware, system libraries and compilation options.
Some basic operations are provided by the C library on common platforms with directed rounding and correctly rounded result: plus, minus, division, multiplication and square root. All other GNU Octave arithmetic functions are not guaranteed to produce accurate results, because they are based on C99 floating-point routines [http://www.gnu.org/software/libc/manual/html_node/Errors-in-Math-Functions.html#Errors-in-Math-Functions]. Their results depend on hardware, system libraries and compilation options.


The interval package handles all functions with the help of the [http://www.mpfr.org/ GNU MPFR library]. With MPFR it is possible to compute system-independent, valid and tight enclosures of the correct results.
The interval package handles all arithmetic functions with the help of the [http://www.mpfr.org/ GNU MPFR library]. With MPFR it is possible to compute system-independent, valid and tight enclosures of the correct results.


== Quick start introduction ==
== Quick start introduction ==
Line 220: Line 218:


  octave:1> sin (infsup (0.5))
  octave:1> sin (infsup (0.5))
  ans ⊂ [.47942553860420294, .47942553860420307]
  ans ⊂ [.47942553860420294, .47942553860420301]
  octave:2> pow (infsup (2), infsup (3, 4))
  octave:2> pow (infsup (2), infsup (3, 4))
  ans = [8, 16]
  ans = [8, 16]
  octave:3> atan2 (infsup (1), infsup (1))
  octave:3> atan2 (infsup (1), infsup (1))
  ans ⊂ [.785398163397448, .7853981633974487]
  ans ⊂ [.7853981633974482, .7853981633974484]


=== Reverse arithmetic operations ===
=== Reverse arithmetic operations ===
Line 233: Line 231:
In the following example, we compute the constraints for base and exponent of the power function <code>pow</code> as shown in the figure.
In the following example, we compute the constraints for base and exponent of the power function <code>pow</code> as shown in the figure.
  octave:1> x = powrev1 (infsup ("[1.1, 1.45]"), infsup (2, 3))
  octave:1> x = powrev1 (infsup ("[1.1, 1.45]"), infsup (2, 3))
  x ⊂ [1.6128979635153644, 2.7148547265657923]
  x ⊂ [1.6128979635153646, 2.7148547265657915]
  octave:2> y = powrev2 (infsup ("[2.14, 2.5]"), infsup (2, 3))
  octave:2> y = powrev2 (infsup ("[2.14, 2.5]"), infsup (2, 3))
  y ⊂ [.7564707973660297, 1.4440113978403293]
  y ⊂ [.7564707973660299, 1.4440113978403284]


=== Numerical operations ===
=== Numerical operations ===
Line 251: Line 249:
Above mentioned operations can also be applied element-wise to interval vectors and matrices. Many operations use [http://www.gnu.org/software/octave/doc/interpreter/Vectorization-and-Faster-Code-Execution.html#Vectorization-and-Faster-Code-Execution vectorization techniques].
Above mentioned operations can also be applied element-wise to interval vectors and matrices. Many operations use [http://www.gnu.org/software/octave/doc/interpreter/Vectorization-and-Faster-Code-Execution.html#Vectorization-and-Faster-Code-Execution vectorization techniques].


In addition, there are matrix operations on interval matrices. These operations comprise: tight dot product, fast dot product, tight matrix multiplication, fast matrix multiplication, tight vector sums, matrix inversion, matrix powers, and solving linear systems. As a result of missing hardware / low-level library support and missing optimizations, these operations are quite slow compared to familiar operations in floating-point arithmetic.
In addition, there are matrix operations on interval matrices. These operations comprise: tight dot product, tight matrix multiplication, tight vector sums, matrix inversion, matrix powers, and solving linear systems. As a result of missing hardware / low-level library support and missing optimizations, these operations are quite slow compared to familiar operations in floating-point arithmetic.


  octave:1> A = infsup ([1, 2, 3; 4, 0, 0; 0, 0, 1]); A (2, 3) = "[0, 6]"
  octave:1> A = infsup ([1, 2, 3; 4, 0, 0; 0, 0, 1]); A (2, 3) = "[0, 6]"
240

edits

Navigation menu