IAsolver 0.1beta1
(10/97)
the Brandeis Interval Arithmetic Constraint Solver
Please send any bug reports to
tim@cs.brandeis.edu
You need a java-enabled web brower to run the applet.
Featured Applet
for the week of 15-22 August 1997 in the
Gamelan Java Archive
Source Code is now Available
The source code for IAsolver is available for browsing in
this directory, or you can download
this gzipped tar file (414K) directly.
This source code is being released as three libraries: ia_math, ia_parser, and ia_solver. All
of these are currently being distributed using the GNU LGPL copyleft for libraries.
Portability
This applet has reportedly run successfully on the following configurations:
- Silicon Graphics workstations
- Netscape Navigator 3.01 on an SGI Indy running IRIX 5.3
- Netscape Navigator 4.02 on an SGI Indy running IRIX 5.3
- Macintosh
- Netscape Navigator 3.01 a Mac Performa 637 running MacOS 7.5
- Netscape Communicator Pro 4.01 on a Power Mac 7300/200 Mac OS 7.5.5
- Netscape 3.02 on a Power Mac running Mac OS 7.6.1
- PC's
- Netscape 4.0 on a PC running Windows NT 4.0
There have been some reports of problems
under some Microsoft operating systems and
browsers, but I have't had any detailed bug reports yet. If you do have a
problem, I would greatly appreciate it if you could send me email at
tim@cs.brandeis.edu describing the machine, browser,
operating system and problem, and I'll post it here and try to work on it.
Thanks.
Please be patient. It may take a few minutes to download this
applet over the net. You can read the instructions and examples
below while waiting for it to load!
Instructions
When the applet has been fully loaded onto your machine, a button
labelled Show IAsolver will appear at the top left
of this page. Pushing this button will open a
new window on which you can enter and solve systems of
arithmetic constraints using narrowing. If there are two or more
variables in the constraint set, then you can use the Interval
Arithmetic plotting feature to simultaneously view
one or more projections of the solution set.
The main window of the solver contains an area for entering
constraints, an area for viewing the current bounds on the
variables, and several control buttons, as shown below:
NOTE: THE FOLLOWING IS JUST A GIF IMAGE.
THE REAL APPLET IS AT THE TOP LEFT OF THIS PAGE.
-
Narrow This button starts a simple narrowing iteration
loop in which each constraint is used to narrow the
intervals of the variables it contains. This processes is
repeated a fixed number of times (initially 10), and you can change this
parameter using the text field at the bottom of the window.
The narrowed intervals for the variables appearing in the constraints
are shown in the textarea labelled "variables" and you can watch the
intervals shrinking while the narrowing is going on. In principle
the narrowing operation has the property that it shrinks the intervals
associated to each variable without removing any of the solution set.
In practice, the current applet relies on the underlying math library
which is not guaranteed to be accurate to the last bit, so this ideal
property is currently not guaranteed to hold.
-
Absolve This button applies another form of narrowing which
attempts to trim the upper and lower bounds of
each variable using a proof by contradiction approach.
More precisely, it trims an upper bound of a variable by
first binding that variable to the region it wishes to trim away.
If narrowing fails, then the region is removed; otherwise, the
region remains. The current system first tries to trim away 1/2
of the interval, then it trims away 1/16.
-
Clear Variables This button sets the bounds of all variables
to [-infty,infty], but has no effect on the set of constraints.
-
Clear Constraints This clears the constraints window, but leaves
the variable bindings alone.
-
Hide This hides the window and stops the applet.
-
Stop This stops the current narrowing operation.
-
Plot This button, draws a 2d plot of the projection of the
constraint onto two (user-specified) variables. You can view several projections
simultaneously. Also, you can use the mouse to zoom in on any interesting
section of a projection. This has the effect of adding additional
constraints to the constraint set (limiting the projected variables),
and hence all other projections will reflect the new "pruned" view.
You can also "unzoom". This feature allows one to examine several
discrete solutions individually.
-
depth This choice selector allows you to control the level
of detail which the plotter presents. A level of k means that
the x and y axes are divided into 2^k segments and each of the
4^k boxes is then narrowed. If narrowing fails the box is painted
white, otherwise it is painted blue.
-
Zoom/Unzoom
This allows you to use the mouse to zoom in on any segment of the plot.
It has the effect of temporarily adding new constraints to the constraint
system and this will therefore affect all other plotting windows
that you have opened. Unzooming reverts to the previous view as
usual.
-
Size to Fit
This increases the magnification so that the solution set fills the
window and then it narrows to depth 3. By repeatedly pressing this
button you can often effectively narrow in on an isolated solution point.
-
max_narrows
This is normally set to 1. It is the number of times that he constraintns
are narrowed for each small subbox that is being plotted.
-
Shade boundary
When this is selected it draws a 10 pixel red boundary around the
blue solution set. This is useful when the solution consists of
1x1 blue pixels which can easily be overlooked (especially if your
screen is dirty!)
Examples of allowable constraints
The constraints must each end with a semicolon and are constructed
from variable names and simple decimal numbers using the standard
operators listed below. Some examples of valid constraints are:
-
sin(x*cos(y))=cos(y*sin(x)); x= [-6.3,6.3]; y = [0,10];
This constraint has a complex (and beautiful) solution set
which you can view using the PLOT function.
The region
which is displayed properly contains the solution set.
It was plotted with the DEPTH parameter set to 8.
By selecting a greater DEPTH parameter for the plot you
can view more detail.
-
y^2 = x*(x^2-1)+z^2; x*y*z=1;
x = [-2,2]; z = [-2,2];
The solution set of this constraint is a 1 dimensional curve in 3-space.
Plotting its (x,y) projection we get the following curve:
which has four components.
If we add the additional constraint sin(x*cos(y))=cos(y*sin(x)), the system
has four solutions which can be isolated using the Plot,
Zoom and UnZoom facilities.
-
x^5 + 3*x^2 +x+50 = 7*exp(x^2) ; x = [-100,0];
has one solution in the following box:
x = [-1.3960403710880638, -1.396040371088062]
-
x**x = 5; x = [1,4] ;
This has one solution in the following interval:
x = [2.129372482760152, 2.1293724827601612]
-
x^2 + y^2 = 25; (x-5)^4 + y^4 = 25; y > 0;
This has one solution in the following box:
x = [4.472998922610509, 4.47299892261052]
y = [2.2343412090200485, 2.2343412090200516]
-
x = [0.88,0.89];
v := MP(x);
y := v - (v^4 - 12*v^3 + 47*v^2 - 60*v + 24)/
(4*x^3 - 36*x^2 + 94*x - 60);
y=x;
This example shows how the interval newton method can be implemented using
IAsolver 0.0. The "y:=E" operator evaluates its right hand side E using
interval arithmetic and assigns that value to the variable y on the left. The
MP(x) function returns the midpoint of the interval x, when evaluated using
interval arithmetic, but it is a nop when narrowed. We could also have used
the left endpoint (LP(x)) or the right endpoint (RP(x)), or some point midway
(0.25*LP(x)+0.75*RP(x)).
This constraint yields the following solution:
x = [0.8883057790717404, 0.8883057790717662]
v = [0.8883057790717532, 0.8883057790717532]
y = [0.8883057790717404, 0.8883057790717662]
SYNTAX
A Constraint is one of the following relations,
where A,B are expressions:
A=B, AB, A!=B, A<=B, A>=B, V:=E
The last is the assignment operator. It evaluates
E using interval arithmetic, and binds the
resulting interval to the variable V. The allowable
expressions are defined below:
-
An Expression E is formed from variables, numbers,
operators, and subexpressions A and B as follows:
-
Decimal numbers (e.g. 3.141592 or -2.718281828459045
-
infty and -infty: the IEEE 754 infinite numbers.
-
variables A variable is a string of letters and/or digits, starting with
a letter.
-
[A,B] the interval notation. This
is equivalent to a variable X with
the additional constraints that A<=X and X <= B. Here A and B must be
numbers, they cannot be variables or compound expressions.
-
A+B, A-B, A*B, A/B the arithmetic operators.
-
A^n the integer power operator, where n must evaluate to an integer.
-
A**B the real power operator, where A must be positive.
-
exp(A), log(A)
the exponential function and the logarithm.
-
MP(x), LP(x), RP(x)
The midpoint function MP(x) returns the midpoint of the interval
x when evaluated using interval arithmetic (i.e. in the RHS of an
assignment statement v := E), but which is the identity function
when narrowed (i.e. when it occurs in an equation F=E). The left
and right endpoint functions (LP(x), RP(x)) are also available
and behave similarly.
-
sin(A), cos(A), tan(A), asin(A), acos(A), atan(A)
The trigonometric functions and their inverses.
Commercial Interval Arithmetic Constraint Systems
If you need a more powerful interval arithmetic constraint solver
you may be interested in the ALS Prolog implementation of
CLP(BNR)
which combines a powerful (and efficient) interval
arithmetic constraint solver with a high quality Prolog
compiler and it runs on almost every platform.
Cautions and Provisos
This software is experimental and you should use at your own risk.
In particular, the current version is NOT sound since it relies on
Java's underlying math library which is not proven to be accurate
to the last bit.
Please send any bug reports, suggestions, or comments to
tim@cs.brandeis.edu
The development of this applet was partially supported
by NSF grant CCR-9403427.