Overview of the Simplex Algorithm

As we mentioned in the previous section the problems we are interested in can be reduced to the solution of the following equation system:

$$\begin{array}{lr} f_i(x_1,x_2,\cdots,x_n) = 0 & (i=1,2,\cdots,n-1) \end{array}$$ (1)

where $f_{i}$ denote (nonlinear) scalar functions with $n$ real variables. In an $n$ dimensional space the $n-1$ component-functions determine $n-1$ hyper-surfaces. The intersection of these hyper-surfaces determines (typically) one-dimensional manifolds (lines) in the $n$ dimensional space. To find these lines, i.e. to solve this equation system Domokos and Gáspár [3] adopted the so-called PL algorithm (described by Allgower and Georg [1]) to the given task. The evaluation of the functions $f_i$ requires in general the forward integration of an ordinary differential equation (ODE). In this section we describe briefly a generalized version of the algorithm.

In the first step we construct an orthogonal grid with grid sizes $\Delta_i (i=1,2,\cdots,n)$ in the $n$-dimensional space. This grid subdivides the phase space into finite orthogonal domains to which we will refer as "cubes" for the sake of simplicity. Each cube has $2^n$ vertices and can be subdivided further into $n!$ simplices. Each of these simplices has $n+1$ vertices. (If $n=2$ then the simplex is a triangle, if $n=3$ then it is a tetrahedron.) The functions $f_i$ can be now linearly interpolated on the simplectic grid, the linearized functions will be denoted by $f_i^L$. The solution of the linear equation system

$$\begin{array}{lr} f_i^L(x_1,x_2,\cdots,x_n) = 0 & (i=1,2,\cdots,n-1) \end{array}$$ (2)

yields an equation of a straight line. If this line goes through the investigated simplex, then the line has two intersection points with the surface of this simplex and the inner part of the line represents a segment of the result in the $n$ dimensional space.

This operation has to be repeated for each simplex in the investigated phase space. Since the number of simplices can be very large and the operation on each simplex is identical, this offers an ideal task for PVM [4]. The implementation is described in the next section.