# Storage and Basic Operations of the Execution Engine

In this section we present, in a step-by-step manner, the operations
that, when combined, build up the AIMMS sparse execution engine. The
data storage method with which these operations work is called an
*ordered view*.

Ordered view

The AIMMS execution engine stores the data according to the concept of an ordered view. An ordered view is an ordered, sparse collection of the non-default elements of an identifier. The order is the lexicographical order of the indices of that identifier. Because of this order:

the non-default elements of the identifier can be visited in a lexicographic order one at a time, and

a particular tuple can be found efficiently using values for the indices.

Running example

The running example, used in this section and presented below, contains
the two parameters `A(i,j)`

and `B(i,j)`

, where `i`

and `j`

are
indices in a set `S`

containing the elements `{a1..a5}`

. The default
values of these parameters are 0.0, and they contain the following data:

```
A(i,j) := data table B(i,j) := data table
a1 a2 a3 a4 a5 a1 a2 a3 a4 a5
! -- -- -- -- -- ! -- -- -- -- --
a1 2 5 a1 3 2
a2 2 3 2 a2
a3 a3 5 1 2
a4 4 a4 4
a5 ; a5 ;
```

The ordered views of `A`

and `B`

are presented in the composite
tables below:

```
Composite table: Composite table:
i j A i j B
! -- -- - ! -- -- -
a1 a2 2 a1 a2 3
a1 a5 5 a1 a5 2
a2 a1 2 a3 a1 5
a2 a3 3 a3 a3 1
a2 a4 2 a3 a4 2
a4 a1 4 ; a4 a1 4 ;
```

Like an index in relational databases

There is nothing really new here; an ordered view corresponds to an
relational table in database terminology, with a (database) index on the
primary keys `i`

and `j`

. A characteristic of both representations
is that they can be easily searched given explicit values for `i`

and
`j`

.

Basic operations

In the following sections, we will classify the algebraic operations in AIMMS according to their behavior in the AIMMS sparse execution engine, and discuss the effects of combining multiple operations or changing the natural index order.

## The `+`

Operator: Union Behavior

First statement

The first statement in the running example is the simple addition of the
matching elements resulting in parameter `C(i,j)`

:

```
C(i,j) := A(i,j) + B(i,j);
```

Merging rows

As illustrated in the following figure, this statement can be
executed in a sparse manner by merging the ordered views of `A`

and
`B`

and adding the values as one progresses.

Union behavior

In this figure, each arrow represents a computed result. The behavior of
the `+`

operator is referred to as *sparse union* behavior: the union
of rows from `A`

and `B`

is taken to form the rows of `C`

and it
is sparse because we do not need to consider those tuples `(i,j)`

for
which `A(i,j)`

and `B(i,j)`

are both 0.0.

Similar operators

Other operators, such as `OR`

, `XOR`

, `<`

, `>`

and `<>`

have a
similar behavior. They can also be implemented using the union of rows
and performing the appropriate operation.

## The `*`

Operator: Intersection Behavior

Second statement

The second statement in the running example is the simple multiplication
of the matching elements resulting in parameter `D(i,j)`

:

```
D(i,j) := A(i,j) * B(i,j);
```

Matching rows

This statement can be executed in a sparse manner by intersecting the
ordered views of `A`

and `B`

and multiplying the corresponding
values. Intersection is sufficient because only for those tuples
`(i,j)`

for which both `A(i,j)`

and `B(i,j)`

are non-zero, will a
non-zero be computed. This is illustrated in the
the following figure

Intersection behavior

Note that the ordered views of both `A`

and `B`

are searchable and,
thus, finding the matching elements can be efficiently implemented. We
call this behavior *sparse intersection* behavior. Because only matching
rows need to be considered, sparse intersection operators are much more
efficient than sparse union operators.

Similar operators

Other operators, such as the `AND`

and `$`

operators, exhibit
similar behavior. They can also be implemented using the intersection of
the rows and performing the appropriate operation.

## The `=`

Operator: Dense Behavior

Third statement

The third statement in the running example checks whether corresponding values are equal.

```
E(i,j) := (A(i,j) = B(i,j));
```

Comparing values

This statement is admittedly somewhat artificial. However, such
conditions are frequently part of larger expressions and must be
considered. The key observation is that the comparison `0.0 = 0.0`

evaluates to true. In AIMMS the value ‘true’ is represented by the
numerical value 1.0. Therefore, the result of `E(i,j)`

is:

```
E(i,j) := data table
a1 a2 a3 a4 a5
! -- -- -- -- --
a1 1 1 1
a2 1 1
a3 1 1
a4 1 1 1 1 1
a5 1 1 1 1 1 ;
```

Dense behavior

Given that the comparison of two zeros also results in a non-zero, all
possible combinations of `(i,j)`

have to be considered. Therefore,
this operation exhibits *dense* behavior, i.e. the operation cannot be
performed in a sparse manner. Dense operators have the worst possible
efficiency.

Similar operators

Other operators, such as `/`

, `**`

, `<=`

and `=>`

demonstrate
similar behavior. They also need to be implemented by considering all
the possibilities and evaluating as one progresses.

Beware!

Increasing the number of indices, or increasing the size of the sets will make the number of rows to be considered in such operations grow rapidly. Large-dimensional dense operations are a potential cause of performance glitches in an application.

## Behavior of Combined Operations

Fourth statement

The fourth statement is a variation of the third statement:

```
EP(i,j) := ( A(i,j) = B(i,j) ) $ A(i,j);
```

Speeding up

Although the operation `=`

remains dense, the entire right hand side
of the assignment statement is limited to only those tuples `(i,j)`

for which `A(i,j)`

is non-zero. This is known as a domain condition on
the expression. The net effect on the expression is that this condition
speeds up efficient behavior by moving from dense to sparse behavior.
The result of this fourth assignment is:

```
EP(i,j) := data table
a1 a2 a3 a4 a5
! -- -- -- -- --
a1
a2
a3
a4 1
a5 ;
```

Preventing dense behavior

If your model contains a statement that performs badly due to a dense operation, using a domain condition can remedy the problem. Often, it is possible to formulate a domain condition that does not alter the result of the computation, but which does allow AIMMS to execute the statement in a sparse manner.

## Summation

Fifth statement

The fifth statement, as detailed below, is a step towards the sixth
statement and illustrates a language construct where sparse evaluation
is straightforward. This fifth statement is a simple aggregation of the
parameter `A(i,j)`

in a parameter `AI(i)`

:

```
AI(i) := Sum( j, A(i,j) );
```

This operation is illustrated in the following figure.

Running indices and identifier indices match

Each pairing represents a group of values corresponding to a particular
value of `i`

. As the elements in a group are adjacent in this ordered
view, the result of `AI`

can be computed in a single pass over the
ordered view of `A`

. The order of the running indices in the statement
is `[i,j]`

. The first running index `i`

is already part of the left
hand side of the assignment, and `j`

is added to this list as part of
the sum.

Single pass is sufficient

Because the order of the running indices matches the order of the
indices in the identifier `A(i,j)`

, the results of the sum can be
computed in a single pass over the ordered view of `A(i,j)`

.

## Reordered Views

Sixth statement

The sixth statement is a small variation to the fifth statement above.
This sixth statement is an aggregation of the parameter `A`

in a
parameter `AJ(j)`

:

```
AJ(j) := Sum( i, A(i,j) );
```

Non-matching index order

This time, the elements that belong to the same group `j`

are not
adjacent in the ordered view of `A`

as the order of the indices in
this statement is `[j,i]`

which does not match the order of the
indices in `A(i,j)`

.

Reordered views

In order to regain adjacency of the elements in the same group, AIMMS
maintains other views of the parameter `A`

known as *reordered views*.
A reordered view of an ordered view is a lexicographic order of the
elements such that the order of the indices in the identifier matches
the order of the running indices. A reordered view, and the grouping
according to this view, are illustrated in the following figure.

Single pass is sufficient

Again, each pairing represents a group of values corresponding to a
particular value of `j`

. As the elements in a group are adjacent in
this reordered view, the results of `AJ`

can be computed by a single
pass over this reordered view of `A`

. AIMMS generates and maintains
reordered views on an as needs basis. They do, however, take up memory.