Efficient method of identifying non-solution or non-optimal regions of the domain of a function

Patent 7076516 Issued on July 11, 2006. Estimated Expiration Date:

September 18, 2021. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

3789203

Method and apparatus for real-time constraint solution
Patent #: 5381361
Issued on: 01/10/1995
Inventor: Kirk, et al.

System for obtaining strict solution in accordance with accuracy of approximate solutions
Patent #: 5631858
Issued on: 05/20/1997
Inventor: Narita, et al.

Speedup for solution of systems of linear equations
Patent #: 5717621
Issued on: 02/10/1998
Inventor: Gupta, et al.

Discriminate reduction data acquisition
Patent #: 5884245
Issued on: 03/16/1999
Inventor: Chandler

Method and system for solving linear systems
Patent #: 6078938
Issued on: 06/20/2000
Inventor: Pan, et al.

Signal processor with local signal behavior Patent #: 6115726
Issued on: 09/05/2000
Inventor: Ignjatovic

Inventors

Assignee

California Institute of Technology

Application

No. 09956590 filed on 09/18/2001

US Classes:

708/446, Solving equation708/290, Interpolation/extrapolation708/801, Particular function performed708/443, Differentiation708/500, Evaluation of root708/300Filtering

Examiners

Primary: Chaki, Kakali
Assistant: Do, Chat C.

Attorney, Agent or Firm

Howrey LLP

Foreign Patent References

1362910 GB 08/01/1974

International Class

G06F 7/38

Abstract

A method of identifying one or more regions of the domain of a function that do not contain solutions is described along with a related subdivision method. These methods may be employed in the context of branch and bound methods that use interval analysis to search for solutions of functions. The one or more regions of the function domain that do not contain solutions are identified using a cropping formula derived from one or more components (low order and high order) of a Taylor Form inclusion function. A Corner Taylor Form inclusion function is also described which might be used to identify the output range of a function.

Other References

Taylor et al., Convergence analysis and optimisation of an iterative technique for polynomial factorisation, Sep. 1989, IEEE, p. 507-511.
Stuart, LP-Form inclusion functions for global optimisation, 1991, IEEE, pp. 51-65.
Hanson, P. et al., Decomposition and Interval Arithmetic Applied to Global Minimization of Polynomial and Rational Functions, Journal of Global Optimization, vol. 3, 1993, pp. 421-437.
Lagouanelle, J-L, and Messine, F., Algorithme d'encadrement de l'optimum global d'une fonction différentiable, C.R. Acad. Sci. Paris—Analyse Numérique, vol. 326, 1998, pp. 629-632.
Messine, F. and Lagouanelle, J-L, Enclosure Methods for Multivariate Differentiable Functions and Application to Global Optimization, Journal of Universal Computer Science, vol. 4, No. 6, 1998, pp. 589-603.
Snyder, John M., Interval Analysis For Computer Graphics; in Proceedings of SIGGRAPH 1992, ACM SIGGRAPH, pp. 121-130, 1992.
Moore, Ramon E., Interval Analysis; Prentice Hall, Inc., pp. 1-145, 1966.
Ratchek, H. and Rokne, J., New Computer Methods for Global Optimization, Ellis Horwood Ltd. 1988, pp. 7-71.
Snyder, J., Generative Modeling for Computer Graphics and CAD: Symbolic Shape Design Using Interval Analysis, Academic Press, Inc. 1992, pp. 1-2; 121-217.