Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2005-07-05
2005-07-05
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06915321
ABSTRACT:
One embodiment of the present invention provides a computer-based system for solving a system of nonlinear equations specified by a vector function, f, wherein f(x)=0 represents ƒ1(x)=0, ƒ2(x)=0, ƒ3(x)=0 . . . , ƒn(x)=0, wherein x is a vector (x1, X2, X3, . . . xn). The system operates by receiving a representation of a subbox X=(X1, X2, . . . , Xn), wherein for each dimension, i, the representation of Xi, includes a first floating-point number, ai, representing the left endpoint of Xi, and a second floating-point number, bi, representing the right endpoint of Xi. The system stores the representation in a computer memory. Next, the system applies term consistency to the set of nonlinear equations, ƒ1(x)=0, ƒ2(x)=0, ƒ3(x)=0, . . . , ƒn,(x)=0, over X, and excludes portions of X that violate the set of nonlinear equations. The system also applies box consistency to the set of nonlinear equations over X, and excludes portions of X that violate the set of nonlinear equations. Finally, the system performs an interval Newton step on X to produce a resulting subbox Y, wherein the point of expansion of the interval Newton step is a point x within X, and wherein performing the interval Newton step involves evaluating f(x) using interval arithmetic to produce an interval result fI(x). The system integrates the sub-parts of the process with branch tests designed to increase the overall speed of the process.
REFERENCES:
patent: 5008672 (1991-04-01), Leedy
patent: 5014230 (1991-05-01), Sinha et al.
patent: 6327581 (2001-12-01), Platt
patent: 6560623 (2003-05-01), Smith
patent: 6563566 (2003-05-01), Rosenbluth 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, 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 Verified 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, Elsever, 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. p. 139-164
Hansen Eldon R.
Walster G. William
Ngo Chuong Dinh
Park Vaughan & Fleming LLP
LandOfFree
Method and apparatus for solving systems of nonlinear... 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 nonlinear..., 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 nonlinear... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3397138