Method and apparatus for solving overdetermined systems of...

Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Reexamination Certificate

active

10447371

ABSTRACT:
One embodiment of the present invention provides a system that solves an overdetermined system of interval linear equations. During operation, the system receives a representation of the overdetermined system of interval linear equations Ax=b, wherein A is a matrix with m rows corresponding to m equations, and n columns corresponding to n variables, and wherein x includes n variable components, b includes m scalar components, and m>n. Next, the system performs a Gaussian Elimination operation to transform Ax=b into the form[TW]⁢x=[uv],wherein T is a square upper triangular matrix of order n, u is a vector with n components, v is a vector with m−n components, and W is a matrix with m−n rows and n columns, wherein W is zero except in the last column, which is represented as a column vector z with m−n components. Next, the system performs an interval intersection operation based on the equations zixn=vi(i=1, . . . , m−n) and Tnnx=unto solve for xn. If xnis not the empty interval, the system performs a back substitution operation using xnand Tx=u to solve for the remaining components (xn−1, . . . , x1) of x.

REFERENCES:
patent: 6859817 (2005-02-01), Walster et al.
patent: 6915321 (2005-07-01), Walster et al.
patent: 6920472 (2005-07-01), Walster et al.
patent: 6950844 (2005-09-01), Walster et al.
patent: 6993548 (2006-01-01), Walster et al.
patent: 2003/0105789 (2003-06-01), Walster et al.
patent: 2003/0110195 (2003-06-01), Walster et al.
patent: 2004/0015531 (2004-01-01), Walster 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, Reliabiliy 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.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Method and apparatus for solving overdetermined systems of... 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 overdetermined systems of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for solving overdetermined systems of... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3853058

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.