Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2005-05-17
2005-05-17
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06895422
ABSTRACT:
One embodiment of the present invention provides a system for finding the roots of a polynomial or a quadratic equation with interval coefficients. The system operates by receiving a representation of a polynomial equation, which can be a quadratic equation of the form F(x)=Ax2+Bx+C=0, wherein A=[AL, AU], B=[BL, BU] and C=[CL, CU] are interval coefficients. Next, the system computes intervals containing roots of the functions F1(x), F2(x), F3(x) and F4(x), wherein F1(x)=ALx2+BLx+CL, F2(x)=AUx2+BUx+CU, F3(x)=ALx2+BUx+CLand F4(x)=AUx2+BLx+CU. The system then places the computed intervals into a list, L, and orders the computed intervals in L by their left endpoints, so that for a each entry, Si=[SiL, SiU], SiL≦Si+1,L. Next, the system establishes interval roots for F(x) from the interval entries in list L. In one embodiment of the present invention, establishing interval roots from the list L involves: establishing one interval root, [S1,L, S2U], if L contains two entries, S1and S2; establishing two interval roots, [S1,L, S2U], and [S3L, S4U], if L contains four entries, S1, S2, S3and S4; and establishing three interval roots, [−∞, S2U], [S3L, S4U] and [S5L, +∞], if L contains six entries, S1, S2, S3, S4, S5and S6.
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-08-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 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 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, Elsevier, 1994, pp. 63-136.
Hansen Eldon R.
Walster G. William
Ngo Chuong Dinh
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for computing roots of a polynomial... 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 computing roots of a polynomial..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for computing roots of a polynomial... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3369722