Representing data having multi-dimensional input vectors and corresponding output element by piece-wise polynomials

• US 7,483,819 B2
• Filed: 12/07/2004
• Issued: 01/27/2009
• Est. Priority Date: 12/07/2004
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Gururajarao, Sumanth K, Tiwari, Shitanshu Krishnachandra, Mair, Hugh Thomas, Gurumurthy, Girishankar
• Primary Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US10/904,973
• Publication Number:
  US 20060123074A1
• Time in Patent Office: 1,512 Days
• Field of Search: 703/2, 703/14, 348/243, 735/73, 705/17
• US Class Current: 703/2
• CPC Class Codes: G06F 17/175 of multidimensional data

Abstract

Determining piece-wise polynomials which together would represent large data sets having multi-dimensional input vectors and corresponding output element. In an embodiment, a function/procedure/routine is recursively called/invoked to determine piece-wise polynomial is a data set cannot be entirely modeled by one polynomial. Another aspect of the present invention reduces the number of combinations (of orders for sub-polynomials forming the polynomials) to be tried in determining polynomials, meeting various accuracy requirements. Such a reduction is obtained based on a recognition that when the order in one dimension alone is increased and the result does not lead to acceptable accuracy of the polynomial, the combinations with a lesser number for the order (of the dimension) can be ruled out.

Claims

1. A method of generating a plurality of piece-wise polynomials representing an input data set with input vectors of multiple dimensions and corresponding output values, said method comprising:

receive a set of parameters providing acceptance criteria for said plurality of piece-wise polynomials;

set a present split dimension to equal one of said multiple dimensions;

set a present sub-domain to equal a portion of a data set along said present split dimension;

determining whether an acceptable polynomial representing said present sub-domain exists;

if said acceptable polynomial exists, setting a temporary polynomial to said acceptable polynomial whereby said temporary polynomial corresponds to said present sub-domain, expanding said present sub-domain along said present split dimension and performing said determining;

if said acceptable polynomial does not exist, saving said temporary polynomial as a piece-wise polynomial for the corresponding present sub-domain, increasing said present sub domain to cover more of an unresolved data set along said present split dimension, wherein said unresolved data set represents a portion of said input data set not yet covered by said piece-wise polynomial;

if said acceptable polynomial does not exist, changing said present split dimension to equal another one of said multiple dimensions; and

wherein said input data set comprises characterization data for a cell library used in the design of integrated circuits.

2. The method of claim 1, if said acceptable polynomial does not exist, wherein said changing is performed only if a number of points in said unresolved data set along said present split dimension equals 2.

3. The method of claim 2 if said acceptable polynomial does not exist, wherein said determining is implemented in the form of a routine which is called recursively.

4. The method of claim 1, wherein said acceptable polynomial comprises a plurality of sub-polynomials which are multiplied to form said acceptable polynomial, wherein a corresponding one of a plurality of orders is associated with each of said plurality of sub-polynomials, said determining comprises:

increasing only a first order to a first value, said first order being contained in said plurality of orders;

computing a corresponding polynomial with said first order being equal to said first value;

checking whether said corresponding polynomial forms said acceptable polynomial; and

ruling out combinations of said first order with lesser than said first value in further determination of said acceptable polynomial.

5. A computer readable medium carrying one or more sequences of instructions for causing a system to generate a plurality of piece-wise polynomials representing an input data set with input vectors of multiple dimensions and corresponding output values, wherein execution of said one or more sequences of instructions by one or more processors contained in said system causes said one or more processors to perform the actions of:

receive a set of parameters providing acceptance criteria for said plurality of piece-wise polynomials;

set a present split dimension to equal one of said multiple dimensions;

set a present sub-domain to equal a portion of a data set along said present split dimension;

determining whether an acceptable polynomial representing said present sub-domain exists;

if said acceptable polynomial exists, setting a temporary polynomial to said acceptable polynomial whereby said temporary polynomial corresponds to said present sub-domain, expanding said present sub-domain along said present split dimension and performing said determining;

if said acceptable polynomial does not exist, saving said temporary polynomial as a piece-wise polynomial for the corresponding present sub-domain, increasing said present sub domain to cover more of an unresolved data set along said present split dimension, wherein said unresolved data set represents a portion of said input data set not yet covered by said piece-wise polynomial;

if said acceptable polynomial does not exist, changing said present split dimension to equal another one of said multiple dimensions; and

wherein said input data set comprises characterization data for a cell library used in the design of integrated circuits.

6. The computer readable medium of claim 5, if said acceptable polynomial does not exist, wherein said changing is performed only if a number of points in said unresolved data set along said present split dimension equals 2.

7. The computer readable medium of claim 6 if said acceptable polynomial does not exist, wherein said determining is implemented in the form of a routine which is called recursively.

8. The computer readable medium of claim 5, wherein said acceptable polynomial comprises a plurality of sub-polynomials which are multiplied to form said acceptable polynomial, wherein a corresponding one of a plurality of orders is associated with each of said plurality of sub-polynomials, said determining comprises:

increasing only a first order to a first value, said first order being contained in said plurality of orders;

computing a corresponding polynomial with said first order being equal to said first value;

checking whether said corresponding polynomial forms said acceptable polynomial; and

ruling out combinations of said first order with lesser than said first value in further determination of said acceptable polynomial.