ALIAS, a System Solving Library Based on Interval Analysis
by Jean-Pierre Merlet
ALIAS is a C++/Maple library based on interval arithmetics, designed for system solving and optimization problems. It has been developed in the framework of the COPRIN project since 1999. Next to general purpose schemes it addresses systems with a particular structure, and intensively uses symbolic computation.
Interval arithmetics is a well known method that enables one to compute bounds for almost any analytically defined expression F(X), being given ranges for the unknowns.
Such computations are required to determine, for example, the range of action of a robot, or possible molecular structures, satisfying certain constraints. The interval obtained by applying interval arithmetics on a mathematical expression is called the interval evaluation of the expression and can be implemented so that numerical round-off errors are taken into account, ie the interval evaluation will always include the exact value of the mathematical expression for any instance of the unknowns within their ranges.
A direct application of this property for systems solving is that if the interval evaluation of the left hand side of at least one equation of the system F(X) = 0 does not include 0, then there is no solution for the system within the given ranges for the unknowns. A straightforward solving algorithm for determining the real roots of a system within some search space can easily be implemented using a branch-and-bound method. A box is defined as a set of ranges, one for each unknown, and a list L of boxes B0, B1, B2, ...,Bn will be maintained during the solving procedure and will be initialized with a box B0 which describes the initial search space. An index i, initialized to 0, will indicate the number of the currently processed box in L.
This algorithm stops when all boxes in L have been processed, and returns as solutions a set of boxes. It may be seen already that this basic algorithm may be extended without effort to deal with inequalities constraints and global optimization. Furthermore, distributed implementation is possible as the processing of one box is independent from the processing of all other boxes in L.
Possible operators have been proposed from different disciplines, numerical analysis and constraints programming, but no available software offers the possibility of hybrid solving based on a combination of operators. However, various experimental trials have shown that an appropriate combination of numerical analysis and constraints programming operators leads to the most efficient solver. Hence, our objectives are twofold:
ALIAS is a relatively large C++ library (200,000 lines of code) that implements various general purpose solving schemes for systems solving and optimization problems. It includes a large library of filtering, exclusion and existence operators, some of them quite original in this field.
ALIAS also includes a set of specific purpose solving schemes devoted to classes of systems with a particular structure (such as distance equations). A theoretical analysis based on the structure of the equations has been used to optimize the efficiency of the general purpose operators and to develop operators that are specific to the system, thereby drastically improving the efficiency of the schemes.
Another important feature of ALIAS is its intensive use of symbolic computation. First of all, the ALIAS C++ library may be used directly from Maple: within a Maple session it is possible to call a specific solving Maple procedure that will automatically create the necessary C++ code, compile and execute it, and return the result to the Maple session. Symbolic computation is also used to improve the efficiency of the C++ code and to create the C++ code of operators that are completely specific to the system at hand.
ALIAS is the software platform of the COPRIN project and has been in development since 1999. The library can freely be downloaded (see the information at http://www-sop.inria.fr/ coprin/logiciels/ALIAS/ALIAS.html). ALIAS has been used to solve various problems in very different domains. Here we give four examples.