Method and apparatus for bounding the solution set of a system of linear equations
AssigneeSun Microsystems, Inc.
InventorsG. William Walster, Eldon R. Hansen
Life of this patent
Estimating the term…
Abstract
One embodiment of the present invention provides a system that bounds the solution set of a system of nonlinear equations specified by the set of linear equations Ax=b, wherein A is an interval matrix and b is an interval vector. During operation, the system preconditions the set of linear equations Ax=b by multiplying through by a matrix B to produce a preconditioned set of linear equations M0x=r, wherein M0=BA and r=Bb. Next, the system widens the matrix M0 to produce a widened matrix, M, wherein the midpoints of the elements of M form the identity matrix. Finally, the system uses M and r to compute the hull h of the system Mx=r, which bounds the solution set of the system M0x=r.
Claims18
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:
- preconditioning the set of linear equations Ax=b by multiplying through by a matrix B to produce a preconditioned set of linear equations M0x=r, wherein M0=BA and r=Bb;
- widening the matrix M0 to produce a widened matrix M, wherein the midpoints of the elements of M form the identity matrix;
- and
- using M and r to compute the hull h of the system Mx=r, which bounds the solution set of the system M0x=r.
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:
- preconditioning the set of linear equations Ax=b by multiplying through by a matrix B to produce a preconditioned set of linear equations M0x=r, wherein M0=BA and r=Bb;
- widening the matrix M0 to produce a widened matrix M, wherein the midpoints of the elements of M form the identity matrix;
- and
- using M and r to compute the hull h of the system Mx=r, which bounds the solution set of the system M0x=r.
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 preconditioning mechanism that is configured to precondition the set of linear equations Ax=b by multiplying through by a matrix B to produce a preconditioned set of linear equations M0x=r, wherein M0=BA and r=Bb;
- a widening mechanism that is configured to widen the matrix M0 to produce a widened matrix M, wherein the midpoints of the elements of M form the identity matrix;
- and
- a hull computing mechanism that is configured to use M and r to compute the hull h of the system Mx=r, which bounds the solution set of the system M0x=r.
A method for bounding the solution set of a system of linear equations Ax=b by multiplying through by the matrix B to produce a preconditioned set of linear equations M0x=r, wherein M0=BA and r=Bb, the method comprising:
- assuring that sup(ri)≧0 by changing the sign of ri (and xi) if necessary;
- widening the matrix M0 to produce a widened matrix M, wherein the midpoints of the elements of M form the identity matrix;
- and
- using M and r to compute the hull h of the system Mx=r, which bounds the solution set of the system M0x=r by,
- forming P as an inverse of the left endpoint of M,
- forming ci=1/(2Pii−1) for i=1, . . . , n,
- forming zi=(inf(ri)+sup(ri))Pii−eiTPsup(r), wherein eiT is a unit vector in which the i-th element is 1 and other elements are 0,
- setting inf(hi)=cizi if zi>0,
- setting inf(hi)=zi if zi≦0, and
- setting sup(h)=Psup(r).
Dependencies are inferred from the claim text.