# Interval vectors and matrices

An interval vector is an ordered tuple of intervals placed vertically(column vector) or horizontally (row vector). So, if `a1, a2, ... , an` are intervals, then

and

`a1, a2, ... , an` is a row vector.

The set of all interval n-vectors is denoted later in the text by IRn.

The interval vectors can be associated with their geometric images, namely rectangular boxes of the space Rn, whose sides are parallel to the coordinate axes. For this reason, interval vectors are often called boxes for brevity.

An interval matrix is a rectangular table composed of the intervals:

or `A = (aij)`. Interval vectors can be identified with interval matrices either of the size `n × 1` (column vectors) or `1 × n` (row vectors). The set of all interval `m × n`-matrices is denoted by `IRm×n`. Arithmetic operations between interval vectors and matrices can be introduced on the basis of the relation that generalizes (1) (see [Alefeld83], [Neumaier90]).

An interval square matrix `A ∈ IRn×n` is referred to as regular (nonsingular) if and only if all the point matrices `A ∈ A` are regular (nonsingular), that is, have nonzero determinants. Otherwise, the interval matrix `A ∈ IRn×n` is called singular, which means that it contains at least one singular point matrix.

Generally, recognition of whether an interval matrix is regular or singular is an NP-hard problem, which implies that there may be no relatively simple (polynomially complex) algorithms that completely solve the problem in a reasonable time.

For practical needs, it is important to have a set of workable sufficient criteria for testing regularity of a wide range of interval matrices. Intel MKL provides routines that implement Ris-Beeck spectral criterion, Rump singular value criterion, as well as Rohn-Rex singular value criterion for testing regularity/singularity of interval matrices.

Sometimes, a related property (called strong regularity) needs to be checked for interval matrices. Strong regularity requires that the product of the interval matrix by its midpoint inverse is regular. The routine ?gerbr enables to check the strong regularity judging by the value of its output parameter sr.

## Interval Linear Systems

Solving systems of linear algebraic equations of the form

or, concisely,
`Ax = b`

with an `m × n` matrix A and a right-hand side m-vector b, is one of the key problems in science and engineering. If `aij` and `bi` are not defined exactly but rather belong to known intervals `aij` and `bi` respectively, the system is called an interval linear system and can be written as

with intervals `aij` and `bi`, or in a short form as

A x = b | (4)

with an interval matrix `A = ( aij)` and interval right-hand side vector `b = ( bi)`. An interval linear system (3)–(4) is considered as a set of point linear systems of the same form `Ax = b` with the parameters `aij` and `bi` such that `aij ∈ aij` and `bi ∈ bi`.

When `aij` and `bi` are changing within intervals `aij` and `bi`, the solutions to the corresponding point systems `Ax = b` with `A = ( aij)` and `b = (bi)` form a set in the space `Rn`, namely

Ξ(A, b := {x ∈ Rn|(∃A ∈ A)(∃b ∈ b)(Ax = b)}. | (5)

The set (5), made up of solutions to all the point systems `Ax = b` with `A ∈ A` and `b ∈ b`, is called a solution set to the interval linear system (3)–(4). Usually, the solution set is a solid polyhedron in `Rn` for independent `aij` and `bi`, `1≤i, j≤n`, sometimes star-shaped as in the figure below.

### Note

The above described set `Ξ(A,B)` is often called a untied solution set, since there exist a variety of other solution sets to interval systems of equations (see [Shary02]).

An exact description of the solution set is practically impossible for dimensions n larger than several tens, since its complexity grows exponentially with n. On the other hand, such an exact description is not really necessary in most cases. Usually, one needs to compute some estimates, in a prescribed sense, of the solution set. The most popular in practice is the following problem of outer (by supersets) interval estimation:

For an interval system of linear equations `Ax = b` find an interval enclosure of the solution set `Ξ(A, b).` | (6)

Frequently, a component-wise form of the problem (6) is considered:

For an interval system of linear equations `Ax = b` find estimates for `min{xv|x∈Ξ(A, b)}` from below, for `max{xv|x∈Ξ(A, b)}`from above, `v = 1, 2, . . . , n`. | (7)

In particular, Intel MKL ?gepps routines operate with this type of the problem statement.

The problem (6)–(7) is one of the historically first and most popular in modern interval analysis. You can find an extensive bibliography on this problem, for example, in [Alefeld83], [Kearfott96] , [Neumaier90]).

Thus, solving an interval linear system is understood here as computing an outer interval estimate of the solution set to an interval linear system (3)–(4). The matrix A of the system is usually assumed to be square nonsingular.

Unlike classical computational linear algebra, solving interval linear systems proves to be very computationally hard in general. Computing the optimal (smallest) interval enclosures of the solution in (6), or, equivalently, computing exact estimates of the solution set in (7), is an NP-hard problem (see [Kreinovich97]), if there are no restrictions on the widths of the intervals in the system and/or the structure of nonzero elements in the matrix A. Moreover, the problem remains NP-hard even if we weaken the requirements on the solution and compute estimates of the solution sets that must be precise to within a predetermined absolute or relative accuracy.

From the practical standpoint, NP-hardness means that with a high probability a general problem cannot be solved in polynomial time with respect to problem size.

For this reason, numerical algorithms employed in Intel MKL for solving interval linear systems are divided into two classes depending on whether or not they provide a guaranteed accuracy of the result. “Fast” algorithms work fast and compute an enclosure of the solution set in a reasonable time, but without any accuracy assumptions. “Optimal”, or “sharp” algorithms may take a lot of time to complete execution, but the results they obtain are less crude and may satisfy some accuracy requirements.

Intel MKL includes interval solver routines that implement algorithms of both types. For example, fast methods, such as interval Gauss method, interval Householder method, Hansen-Bliek-Rohn method, and Krawczyk iteration, are implemented in routines ?gegas, ?gehss, ?gehbs, and ?gekws, respectively. Parameter partitioning method (PPS-method) implemented in ?gepps routine is an example of a sharp method. The routine ?trtrs is subsumed under both categories due to a very special matrix structure.

Parent topic: Interval Linear Systems