IntervalMatrices.jl

IntervalMatrices is a Julia package to work with matrices that have interval coefficients.

Features

Here is a quick summary of the available functionality. See the section Library Outline below for details.

  • An IntervalMatrix type that wraps a two-dimensional array whose components are intervals.
  • Arithmetic between scalars, intervals and interval matrices.
  • Quadratic expansions using single-use expressions (SUE).
  • Interval matrix exponential: underapproximation and overapproximation routines.
  • Utility functions such as: operator norm, random sampling, splitting and containment check.

An application of interval matrices is to find the set of states reachable by a dynamical system whose coefficients are uncertain. The library ReachabilityAnalysis.jl implements algorithms that use interval matrices [3] [4].

Installing

Depending on your needs, choose an appropriate command from the following list and enter it in Julia's REPL.

To install the latest release version:

pkg> add IntervalMatrices

To install the latest development version:

pkg> add IntervalMatrices#master

To clone the package for development:

pkg> dev IntervalMatrices

Quickstart

An interval matrix is a matrix whose coefficients are intervals. For instance,

julia> using IntervalMatrices

julia> A = IntervalMatrix([0..1 1..2; 2..3 -4.. -2])
2×2 IntervalMatrix{Float64, Interval{Float64}, Matrix{Interval{Float64}}}:
 [0, 1]    [1, 2]
 [2, 3]  [-4, -2]

defines an interval matrix $A$. The type of each coefficient in $A$ is an interval, e.g. its coefficient in position $(1, 1)$ is the interval $[0, 1]$ over double-precision floating-point numbers:

julia> A[1, 1]
[0, 1]

julia> typeof(A[1, 1])
Interval{Float64}

This library uses the interval arithmetic package IntervalArithmetic.jl to deal with interval computations. For instance, one can compute a multiple of $A$,

julia> 2A
2×2 IntervalMatrix{Float64, Interval{Float64}, Matrix{Interval{Float64}}}:
 [0, 2]    [2, 4]
 [4, 6]  [-8, -4]

Or an interval multiple of $A$,

julia> (-1.0..1.0) * A
2×2 IntervalMatrix{Float64, Interval{Float64}, Matrix{Interval{Float64}}}:
 [-1, 1]  [-2, 2]
 [-3, 3]  [-4, 4]

Or compute the square of $A$,

julia> square(A)
2×2 IntervalMatrix{Float64, Interval{Float64}, Matrix{Interval{Float64}}}:
    [2, 7]  [-8, -1]
 [-12, -2]   [6, 22]

In these cases, the rules of interval arithmetic are used; see the Wikipedia page on interval arithmetic for the relevant definitions and algebraic rules that apply.

However, the straightforward application of the rules of interval arithmetic does not always give the exact result: in general it only gives an overapproximation [1] [2]. To illustrate, suppose that we are interested in the quadratic term $At + \frac{1}{2}A^2 t^2$, which corresponds to the Taylor-series expansion at order two of $e^{At} - I$. Then, at $t = 1.0$,

julia> A + 1/2 * A^2
2×2 IntervalMatrix{Float64, Interval{Float64}, Matrix{Interval{Float64}}}:
  [0.5, 4.5]  [-3.25, 2.5]
 [-4.25, 3]   [-2.25, 9]

However, that result is not tight. The computation can be performed exactly via single-use expressions implemented in this library:

julia> quadratic_expansion(A, 1.0, 0.5)
2×2 IntervalMatrix{Float64, Interval{Float64}, Matrix{Interval{Float64}}}:
  [1, 4.5]  [-2, 1]
 [-3, 1.5]   [1, 7]

We now obtain an interval matrix that is strictly included in the one obtained from the naive multiplication.

An overapproximation and an underapproximation method at a given order for $e^{At}$, where $A$ is an interval matrix, are also available. See the Methods section for details.

Library Outline

Explore the types and methods defined in this library by following the links below, or use the search bar in the left to look for a specific keyword in the documentation.

References

  • 1Althoff, Matthias, Olaf Stursberg, and Martin Buss. Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. 2008 47th IEEE Conference on Decision and Control. IEEE, 2008.
  • 2Kosheleva, Olga, et al. Computing the cube of an interval matrix is NP-hard. Proceedings of the 2005 ACM symposium on Applied computing. ACM, 2005.
  • 3Althoff, Matthias, Bruce H. Krogh, and Olaf Stursberg. Analyzing reachability of linear dynamic systems with parametric uncertainties. Modeling, Design, and Simulation of Systems with Uncertainties. Springer, Berlin, Heidelberg, 2011. 69-94.
  • 4Liou, M. L. A novel method of evaluating transient response. Proceedings of the IEEE 54.1 (1966): 20-23.