Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1999-12-30
2004-11-02
Jones, Hugh (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S001000
Reexamination Certificate
active
06813590
ABSTRACT:
FIELD OF THE INVENTION
The invention relates the field of fitting mathematical expressions to data.
PRIOR ART
There are many known techniques for fitting both continuous functions and piecewise-linear expressions to data. These techniques have become more important recently since with current computing power it is now possible to rapidly solve mathematical expressions that were not solvable a few decades ago. Moreover, as the cost of computing power decreases new opportunities arise for solving problems in unexplored fields.
Where a few variables and tens or hundreds of data points are involved, techniques using heuristic approaches and intuition may be adequate. It is known, for instance, to use a piecewise-linear fitting representing the characteristics of transistors where the maximum value of all of the piecewise planes approximate the data. The breakpoint of the planes are selected heuristically since the operation of transistors are relatively simple and well understood. On the other hand, a complex problem such as airline scheduling may involve hundreds of thousands of variables with no intuitive guidelines to set initial bounds. There are countless other systems having thousands of variables which defy an intuitive approach. Thus there is a continuing need for rigorous methods that allow for the developing of expressions especially for complex systems.
Additionally, mathematical expressions that can be expressed as, or converted to, posynomial expressions lend themselves to geometric programs. These programs can be solved with efficient interior-point methods. This technique is known particularly for solving electrical circuit problems. See “CMOS Operational Amplifier Design In Optimization Via Geometric Programming,” by Hershenson, Boyd and Lee, Proceedings of the First International Workshop on Design of Mixed Mode Integrated Circuits and Applications, July 97 and “Automated Design of Folded-Cascode Op Amps with Sensitivity Analysis,” by Herschenson, Boyd and Lee, 5
th
IEEE International Conference on Electronics, Circuits and System, September 98.
SUMMARY OF THE INVENTION
A computer implemented method for providing a mathematical representation of a system having a plurality of variables is disclosed. Planes are fitted to the data where each plane deviates from the data by no more than a predetermined tolerance in one sense. A plane is selected for inclusion in a set of planes if inclusion reduces the error between the set of planes and the data. After a plane is added to the set, refitting occurs and another plane is selected for inclusion in the set. This continues until there is no reduction in error from adding planes to the set. The maximum value of the planes in the set forms an expression which represents the data.
In an alternate embodiment a look ahead method is used which determines whether the inclusion of a particular plane in the set provides for more error reduction when taking into account the inclusion of planes in subsequent iterations.
In addition methods are described for providing a max-monomial approximation as well as a posynomial approximation.
REFERENCES:
patent: 5373457 (1994-12-01), George et al.
patent: 5692107 (1997-11-01), Simoudis et al.
patent: 5774382 (1998-06-01), Tyler et al.
patent: 6253164 (2001-06-01), Rohm et al.
patent: 6269277 (2001-07-01), Hershenson et al.
Heredia et al., “Piecewise Linear System Modeling Based on a Continuous Threshold Decomposition”, IEEE Transactions on Signal Processing, vol. 44, Issue 6, Jun. 1996, pp. 1440-1453.
Barcelona Design, Inc.
Blakely , Sokoloff, Taylor & Zafman LLP
Jones Hugh
LandOfFree
Method for providing convex piecewise-linear expression for... 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 for providing convex piecewise-linear expression for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for providing convex piecewise-linear expression for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3307943