Method and apparatus for bounding the solution set of a system of linear equations

1. A method for bounding the solution set of a system of linear equations Ax=b, wherein A is an interval matrix and b is an interval vector, the method comprising:

receiving the system of linear equations Ax=b;

storing Ax=b in a memory in a computer system;

preconditioning the set of linear equations Ax=b by multiplying both side of the linear equations by a matrix B to produce a preconditioned set of linear equations BAx=Bb, wherein the set of linear equations is a representation of a global optimization problem;

substituting M 0 =BA and r=Bb to produce M 0 x=r;

widening the matrix M 0 to produce a widened matrix M, wherein the midpoints of the interval elements of M form the identity matrix; and

using M and r to compute a hull h of the system Mx=r, which bounds the solution set of the system M 0 x=r;

wherein the interval operations involved in bounding the solution set are performed using a special-purpose interval arithmetic unit configured to perform interval arithmetic operations.

2. The method of claim 1 , wherein the method further comprises computing the matrix B by:

computing an approximate center A C of the interval elements of matrix A; and

forming B by computing an approximate inverse of A C , B=(A C ) −1 .

3. The method of claim 1 , further comprising assuring that sup(r i )≧0 by changing the sign of r i and x i if necessary, wherein r i is an element of r.

4. The method of claim 1 , further comprising:

determining if M is regular; and

using the Gauss-Seidel process for computing the hull h if M is not regular.

5. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for bounding the solution set of a system of linear equations Ax=b, wherein A is an interval matrix and b is an interval vector, the method comprising:

receiving the system of linear equations Ax=b;

storing Ax=b in a memory in a computer system;

preconditioning the set of linear equations Ax=b by multiplying both side of the linear equations by a matrix B to produce a preconditioned set of linear equations BAx=Bb, wherein the set of linear equations is a representation of a global optimization problem;

substituting M 0 =BA and r=Bb to produce M 0 x=r;

widening the matrix M 0 to produce a widened matrix M, wherein the midpoints of the interval elements of M form the identity matrix; and

using M and r to compute a hull h of the system Mx=r, which bounds the solution set of the system M 0 x=r;

wherein the interval operations involved in bounding the solution set are performed using a special-purpose interval arithmetic unit configured to perform interval arithmetic operations.

6. The computer-readable storage medium of claim 5 , wherein the method further comprises computing the matrix B by:

computing an approximate center A C of the interval elements of matrix A; and

forming B by computing an approximate inverse of A C , B=(A C ) −1 .

7. The computer-readable storage medium of claim 5 , wherein using M and r to compute the hull h involves:

forming P as an inverse of the left endpoint of M;

forming c i =1/(2P ii −1) for i=1, . . . , n;

forming z i =(inf(r i )+sup(r i ))P ii −e i T Psup(r), wherein e i T is a unit vector in which the i-th element is 1 and other elements are 0, and wherein r i is an element of r;

setting inf(h i )=c i z i if z i >0;

setting inf(h i )=z i if z i ≦0; and

setting sup(h)=Psup(r).

8. The computer-readable storage medium of claim 5 , wherein the method further comprises assuring that sup(r i )≧0 by changing the sign of r i and x i if necessary, wherein r i is an element of r.

9. The computer-readable storage medium of claim 5 , wherein the method further comprises:

determining if M is regular; and

using the Gauss-Seidel process for computing the hull h if M is not regular.

10. An apparatus that bounds the solution set of a system of linear equations Ax=b, wherein A is an interval matrix and b is an interval vector, comprising:

a receiving mechanism configured to receive the system of linear equations Ax=b;

a special purpose arithmetic unit configured to perform interval computations;

a storing mechanism configured to store Ax=b in a memory in a computer system;

a preconditioning mechanism within the special purpose arithmetic unit that is configured to precondition the set of linear equations Ax=b by multiplying both side of the linear equations by a matrix B to produce a preconditioned set of linear equations BAx=Bb, wherein the set of linear equations is a representation of a global optimization problem;

a substituting mechanism within the special purpose arithmetic unit that is configured to substitute M 0 =BA and r=Rb to produce M 0 x=r;

a widening mechanism within the special purpose arithmetic unit that is configured to widen the matrix M 0 to produce a widened matrix M , wherein the midpoints of the interval elements of M form the identity matrix; and

a hull computing mechanism within the special purpose arithmetic unit that is configured to use M and r to compute a hull h of the system Mx=r, which bounds the solution set of the system M 0 x=r;

wherein the interval operations involved in bounding the solution set are performed using the special-purpose interval arithmetic unit.

11. The apparatus of claim 10 , wherein the preconditioning mechanism is configured to:

compute an approximate center A C of the interval elements of matrix A; and to

form B by computing an approximate inverse of A C , B=(A C ) −1 .

12. The apparatus of claim 10 , wherein the hull computing mechanism is configured to:

form P as an inverse of the left endpoint of M;

form c i =1/(2P ii −1) for i=1, . . . , n;

form z i =(inf(r i )+sup(r i ))P ii −e i T Psup(r), wherein e i T is a unit vector in which the i-th element is 1 and other elements are 0, and wherein r i is an element of r;

set inf(h i )=c i z i if z i >0;

set inf(h i )=z i if z i ≦0; and to

set sup(h)=Psup(r).

13. The apparatus of claim 10 , wherein the preconditioning mechanism is configured to assure that sup(r i )≧0 by changing the sign of r i and x i if necessary, wherein r i is an element of r.

14. The apparatus of claim 10 , wherein the preconditioning mechanism is configured to:

determine if M is regular; and to

terminate the process of computing the hull h if M is not regular.

15. A method for bounding the solution set of a system of linear equations Ax=b by multiplying both side of the linear equations by the matrix B to produce a preconditioned set of linear equations BAx=Bb, wherein the set of linear equations is a representation of a global optimization problem, the method comprising:

receiving the system of linear equations Ax=b;

storing Ax=b in a memory in a computer system;

substituting M 0 =BA and r=Bb producing M 0 x=r;

assuring that sup(r i )≧0 by changing the sign of r i (and x i ) if necessary;

widening the matrix M 0 to produce a widened matrix M, wherein the midpoints of the interval elements of M form the identity matrix; and

using M and r to compute a hull h of the system Mx=r, which bounds the solution set of the system M 0 x=r by,

forming P as an inverse of the left endpoint of M,

forming c i =1/(2P ii −1) for i=1, . . . , n,

forming z i =(inf(r i )+sup(r i ))P ii −e i T Psup(r), wherein e i T is a unit vector in which the i-th element is 1 and other elements are 0, and wherein r i is an element of r,

setting inf(h i )=c i z i if z i >0,

setting inf(h i )=z i if z i ≦0, and

setting sup(h)=Psup(r);

wherein the interval operations involved in bounding the solution set are performed using a special-purpose interval arithmetic unit configured to perform interval arithmetic operations.

16. The method of claim 15 , further comprising:

determining if M is regular; and

using the Gauss-Seidel process for computing the hull h if M is not regular.

17. The method of claim 15 , wherein the method further comprises computing the matrix B by:

computing an approximate center A C of the interval elements of matrix A; and

forming B by computing an approximate inverse of A C , B=(A C ) −1 .