Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2005-09-27
2005-09-27
Mai, Tan V. (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06950844
ABSTRACT:
One embodiment of the present invention provides a system that performs a procedure to solve a system of linear inequalities. During operation, the system receives a representation of the system of linear inequalities Ax≦b, wherein Ax≦b can be a linearized form of a system of nonlinear equations. Within this representation, A is an interval matrix with m rows corresponding to m inequalities, and with n columns corresponding to n variables, the vector x includes n variable components, and the vector b includes m scalar interval components. The system solves the system of linear inequalities Ax≦b by performing a Gaussian elimination process using only positive multipliers so as not to change the sense of any inequality. For a given column j in A, performing the Gaussian elimination process involves attempting to select a primary pivot row r including a primary pivot element, arj, which does not contain zero, and attempting to select a secondary pivot row s including a secondary pivot element, asj, which does not contain zero and is opposite in sign to arj. If r and s are successfully selected, the system uses the secondary pivot element asjto zero elements opposite in sign to it in the same column of A, except for the primary pivot element arj. The system also adds a copy s′ of the secondary pivot row s to the matrix A, thereby increasing the number of rows in the matrix A. Next, the system uses the primary pivot element are to zero elements opposite in sign to it in the same column of A, except for the copy of the secondary pivot element as′jin row s′.
REFERENCES:
patent: 5136538 (1992-08-01), Karmarkar et al.
patent: 5717621 (1998-02-01), Gupta et al.
patent: 5872952 (1999-02-01), Tuan et al.
patent: 6078938 (2000-06-01), Pan et al.
E.R. Hansen, “Global Optimization Using Interval Analysis,” Marcel Dekker, Inc., New York, NY, 1992.
R.B. Kearfott, “A Fortran 90 Environment for Research and Prototyping of Enclosure Algorithms for Nonlinear Equations and Global Optimization,” ACM Transactions on Mathematical Software, vol. 21, No. 1, Mar. 1995, pp. 63-78 http://interval.louisiana.edu/preprints.html.
R. B. Kearfott, Algorithm 763: Interval Arithmetic: A Fortran 90 Module for an Interval Data Type, ACM Trans. Math. Software, 22, vol. 4, 1996, pp. 385-392. http://interval.louisiana.edu/preprints.html.
R. B. Kearfott and M. Novoa III, “Algorithm 681: INTBIS, A portable interval Newton/bisection package”, ACM Trans. Math Software, vol. 16, No. 2, pp. 152-147. http://www.netlib.org/toms/681.
R. B. Kearfott, M. Dawande, K.S. Du, and C. Hu, “Algorithm 737: INTLIB: A Portable Fortran 737 Interval Standard Function Library,” ACM Trans. Math. Software, 20, vol. 4, Dec. 1994, pp. 447-458.
R. B. Kearfott and G.W. Walster, “On Stopping Criteria in Verfied Nonlinear Systems or Optimization Algorithms,” ACM Trans. Math. Software, 26, vol. 3, Sep. 2000, pp. 323-351. The publication itself says Received: Jul. 1999; revised: Mar. 2000; accepted: Mar. 2000. http://interval.louisiana.edu/preprints.html.
R.E. Moore and S.T. Jones “Safe Starting Regions for Iterative Methods”, SIAM Journal on Numerical Analysis, vol. 14, No. 6 (Dec. 1977), pp. 1051-1065.
A. Neumaier, “The Enclosure of Solutions of Parameter-Dependent Systems of Euqations,” Cambridge University Press, Cambridge, 1990, ISBN: 0-12-505630-3, Reliability in Computing pp. 269-286.
S.M. Rump, “Verification Methods for Dense and Sparse Systems of Equations,” in Topics in Validated Computations: Proceedings of the IMACS-GAMM International Workshop on Validated Computations, University of Oldenburg, J. Herzberger, ed., Elsevier Studies in Computational Mathematics, Elsevier, 1994, pp. 63-136.
Pascal Van Hentenryck, Vijay Saraswat and Yves Deville, “Design, Implementation, and Evaluation of the Constraint Language cc (FD),” Elsevier Science, Inc., 1998.
Hansen Eldon R.
Walster G. William
Mai Tan V.
Park Vaughan & Fleming LLP
Sun Microsystems Inc
LandOfFree
Method and apparatus for solving systems of linear inequalities does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for solving systems of linear inequalities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for solving systems of linear inequalities will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3374727