Representing Data Having Multi-dimensional Input Vectors and Corresponding Output Element by Piece-wise Polynomials

• US 20060123074A1
• Filed: 12/07/2004
• Published: 06/08/2006
• Est. Priority Date: 12/07/2004
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: TIWARI, Shitanshu Krishnachandra, GURURAJARAO, Sumanth K., MAIR, Hugh Thomas, GURUMURTHY, Girishankar
• Granted Patent: US 7,483,819 B2
• Time in Patent Office: Days
• US Class Current: 708/270
• 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 a 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 and present sub-domain exists;

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

if said acceptable polynomial does not exist, having said temp 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 input data set not yet covered by said piece-wise polynomial.

2. The method of claim 1, if said acceptable polynomial does not exist, changing said present split dimension to equal another one of said multiple dimensions.

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

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

5. The method of claim 1, wherein said acceptable polynomial comprises a plurality of sub-polynomial 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 combination of said first order with lesser that said first value in further determination of said acceptable polynomial.

6. The method of claim 1, wherein said input data set comprises characterization data for a cell library used in the design of integrated circuits.

7. A method of determining a plurality of sub-polynomials, which when multiplied forms an acceptable polynomial representing an input data set with input vectors of multiple dimensions and corresponding output values, wherein a corresponding one of a plurality of orders is associated with each of said plurality of sub-polynomials, said method comprising:

increasing only a first order to a first value, said first 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 that said first value in further determination of said acceptable polynomial if said corresponding polynomial does not form said acceptable polynomial.

8. A computer readable ridable carrying one or more sequences of instructions for causing 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 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 temp polynomial to said acceptable polynomial whereby said temp polynomial corresponds to said present sub-domain, expanding said present sub-domain along said split dimension and performing said determining; and

if said acceptable polynomial does not exist, saving said temp 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 input data set not yet covered by said piece-wise polynomial.

9. The computer readable medium of claim 8, if said acceptable polynomial does not exist, changing said present split dimension to equal another one of said multiple dimensions.

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

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

12. The computer readable medium of claim 8, 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.

13. The computer readable medium of claim 8, wherein said input data set comprises characterization data for a cell library used in the design of integrated circuits.

14. A computer readable medium carrying one or more sequences of instructions for causing system to determine a plurality of sub-polynomials, which when multiplied forms an acceptable polynomial representing an input data set with input vectors of multiple dimensions and corresponding output values, wherein a corresponding one of a plurality of orders is associated with each of said plurality of sub-polynomials, 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 action of:

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 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 if said corresponding polynomial does not form said acceptable polynomial.