next up previous contents
Next: Dealing with inequalities Up: Practical implementation Previous: Practical implementation   Contents

The generic analyzer

The purpose of the generic analyzer is to consider as input any system defined in a MAPLE file and an initial set of ranges for the unknowns and to produce as output a set of ranges, strictly included in the initial set, that may contain real roots of the system. The output is presented as a file that can be used directly as input for the generic solver.

A formal-numerical approach has been used to develop this generic analyzer. Basically it takes as input a MAPLE file, called the formula file, which define the analytical form of the equations of the system and a range file in in which are defined both the names of the variables and their initial ranges (a range file may contain more than one set of ranges for the unknowns). The convention in the formula file is to define each equation of the system in the MAPLE file as a sentence prefixed by the key-word eqn where n is the number of the equation starting at 1. For example

is a valid formula file, describing a set of 4 equations. The range file has as many lines as unknowns and each line start by the name of the variable followed by two numbers indicating the range for the variable. For example
x -100 100
y -100 100
z -100 100
t -100 100
is a valid range file for the previous formula file. The analyzer is able to deal with infinity in the ranges: instead of using numbers you may indicate infinity or -infinity. In a first step the analyzer will use MAPLE to produce various intermediary files which are needed for the algorithm to proceed (see section For example it will write in the /tmp/Equation file a description of the system compatible with the syntax used by the parser. Similarly you will find in the /tmp/Gradient_Equation and Hessian_Equation files a description of the gradient and hessian of the system. As soon as all the necessary files have been written, the algorithms described in the previous section will be used.

The result of the analyzer is a file (by default .result_IA) that describe the possibles ranges which may contain real roots of the system. This file may then be used as input for the solver. The analyzer will also produced the .gradient_IA file that indicate the value of the gradient matrices for each of the out ranges.

The analyzer is run by using the syntax:

Interval_Analyzer -F [formula file] [-G] [-H] -R [range file]
In this list of argument only the -F, -R are compulsory. The -G option indicates that you will use the monotonicity of the equations (evaluated through an interval evaluation of the gradient) to improve the interval evaluation of the equations. The -H indicates that you will also use Kantorovitch theorem to isolate the real roots of the equations. In that case if you have $m$ equations and $n$ unknowns with $m>n$, then Kantorovitch will be applied on the $n$ first equations.

This program will then ask you the maximum number of ranges that may be created by the algorithm, an accuracy $\epsilon_f$ on the value of the equations that will be used to stop the computation of the Newton scheme, a minimal value for the maximal diameter for the output ranges (which is not used right now), a depth level, a maximal diameter for the ranges over which Kantorovitch is not used and the value of the debug level (0 if the program is to be run quietly, 1 to see how many boxes are dealt with and 2 for a full debug). Note that if you are using the -H option and have $m$ equations and $n$ unknowns, with $m>n$ and if the algorithm returns roots of the system (i.e. the output ranges are reduced to a point) it will mean that these points are guaranteed roots of the $n$ first equations (you may use the Newton scheme with a lower $\epsilon_f$ on these roots and you will still get a root), while the absolute values of the $m-n$ remaining equations at these points will be lower than $\epsilon_f$ but there is no guarantee that these points are effectively roots of these equations.

Alternatively you may use a configuration file to give values for these parameters.

A configuration file consists in a list of keywords followed by a value.

For example
Iteration 1000
AccuracyF 0.00001
Debug 0
Kanto 0.5
Level 2
Location_IS /u/ALIAS/Maple
is a valid configuration file. It indicates that at most 1000 ranges may be created (this is not the maximal number of ranges at the end of the algorithm but the maximal number of ranges that may be created at any time in the algorithm), that the accuracy for the Newton scheme is 0.00001, that the algorithm will run quietly, that Kantorovitch will be used as soon as the maximal diameter of the considered range is lower than 0.5 and that the depth level will be 2. We indicate also in which directory is located the library lib_IS. files are located.

You use the configuration file with the syntax:

Interval_Analyzer -F [formula file] -G -H -R [range file] -C
[configuration file]
So a typical analysis and solving process will be done by using the two following command lines (which are basically identical to what is used in the script script_solver provided in the standard distribution of ALIAS):
Interval_Analyzer -F equation.maple -G -H -R range -C conf_analyzer
Interval_Solver -F /tmp/Equation -G /tmp/Gradient_Equation -H
/tmp/Hessian_Equation -R .result_IA -GI .gradient_IA -C conf_solver
You will then have the result of the solution of your system in the file .result_IS.

next up previous contents
Next: Dealing with inequalities Up: Practical implementation Previous: Practical implementation   Contents
Jean-Pierre Merlet 2012-12-20