Re: table_model constraints

Geoffrey,

I talked to our table model developer who has worked on our model as well
as with the folks from Antrim whom were active in using the behavioral
table models in block modeling. Based on my conversation with him I think
we are trying to make this too complicated but I'm open to opposing views.

First if you must cut to make the deadline do not remove the 3 dimensions
as that is a must but just restrict 2nd and 3rd order interpolation to 1
dimension tables. To do so the changes are fairly straight forward.

In 10.12.3.1 state that currently a restriction on multi-dimension tables
is that only linear interpolation is supported. This restriction may be
removed at a later date.
In 10.12.3.3 the table needs to change the "3" to "1"
In 10.12.4 the examples would need the "3" changed to "1"

With this said the most common way (I also searched the Internet a bit on
this also) is to treat each input variable (dimension)
independently. First if we start with the agreement that a one dimensional
table model is not a problem, we have enough data to fully generate 1st,
2nd, or 3rd order interpolation of this type of table using the conditions
already documented. I'm not sure if I can do justice in words to explain
this but I'll try.

Moving to a two dimensional model with say a 2nd order interpolation we can
take the input data provided (X, Y) and create a series of 1-dimensional
curves for X using 2nd order interpolation. So now I have for each value of
X a spline curve that for any value of Y gives me my F(xi,yj) value.

With the above set of Xi curves I can now generate a equivalent set of Yj
curves. The good news is since for each Xi value I can provide either the
actual Y value or the interpolated Y value based on my Xi curves allowing
this set of curves to be generated.

And I can also generate the Yj curve for the F(Xi,Yj) being solved for
which will most likely be all interpolated values at each Xi grid
point. With this last curve I can now easily determine my F(Xi,Yj) value
from this curve and the problem is now solved with the given data.

This method is extendible for any dimension table although it does become
compute intensive which is why we limited it to 3 dimensions. No Cartesian
grid is required nor are derivatives although if you wanted there are
methods to calculate them. There are other more complex ways to
interpolate points such as building a surface model for each section of the
surface bounded by the data points you provided which take more up front
time but are faster and slightly more accurate lookups.

You will also noticed that there is a certain amount of error built into
this method as the set of Yj curves are based in many cases on interpolated
results making those curves not exact but this after all is a table
model. It should also be noted that this form of table model should not be
confused with the specialized table models used in FastSPICE simulators to
model MOS devices which are highly optimized and based on numerous
assumptions to the device they are used to model.

I did find a good source of data on this at the following web site. The
second link is the description of their math library that does a similar
thing to what we do.

http://mathalacarte.com/cb/mom.fcg/ya59
http://mathalacarte.com/cb/mom.fcg/ch12-02.pdf?_;ydm=0;II=59

I'm also not convinced that we need to document more on how to do this in
the LRM as this method seemed to be well understood by those doing table
lookup in the industry and I would not want to limit folks to one specific
implementation (there are optimizations also not discussed).

I do hope this helps clarify the questions although in written form without
pictures I'm sure it leaves lots of open questions.

Let me know if this helps (or not :) )

Jon

At 01:04 PM 8/10/2004, Geoffrey.Coram wrote:
>I've been having a look at the numbers of equations and unknowns
>for a 2-d interpolation, 2nd and 3rd order.
>
>**** 2nd order splines
>
>If one has a polynomial Cij x^i y^j for i=0..2, j=0..2, there are
>9 coefficients per region.
>
>If we assume a Cartesian grid, with M points in the x direction
>and N points in the y direction, that gives (M-1)*(N-1) regions.
>
>Thus, we have a total of 9MN-9M-9N+9 unknowns.
>
>
>In each region, the polynomial must fit the data given for the four
>corners. This is 4MN-4M-4N+4 equations/constraints.
>
>The derivative df/dx must be continuous at the boundaries. I believe
>we want the derivative to be continuous for all y along the edge,
>not just at the corner points. df/dx will have terms that are
>order y^0,y^1, and y^2; the coefficients of each power must be
>equal on either side of the boundary, so this means we have 3
>equations for each boundary. There are (M-2) boundaries per "row"
>and (N-1) rows. This makes 3MN-3M-6N+6 equations.
>
>The derivative df/dy gives us 3MN-6M-3N+6 for similar reasons.
>
>Thus, we have a total of 10MN-13M-13N+16 equations, but only
>9MN-9M-9N+9 unknowns. The system is *overconstrained* once we
>get bigger than 7x7.
>
>I don't see that a 2nd order spline is useful in 2d (or 3d),
>since we have to give up some constraints, either fitting
>the data or continuity of derivatives.
>
>
>**** 3rd order splines
>
>The book "Numerical Recipes in C" indicates that a bicubic spline can
>be set up by specifying f, df/dx, df/dy, and d2f/dxdy on the Cartesian
>grid. The interpolation function will have these specified derivatives
>continuous across the region boundaries. Note that, even though it is
>cubic, we don't necessarily get 2nd order derivatives continuous.
>The bicubic spline is of the form
> (sum on i=0..3)(sum on j=0..3) Cij x^i y^j
>which is 16 terms per region.
>
>Since users generally will not have derivative information, let's see
>how many constraints we need beyond the function values and the
>continuity of derivatives.
>
>The values provide 4 constraints per region.
>
>The derivative df/dx will contain terms of order y^0, y^1, y^2, y^3,
>and these must vanish independently; that means we have 4 equations
>per boundary, and (M-2)*(N-1) boundaries. We get the same number of
>constraints for df/dy.
>
>It turns out that we do not get any further constraints by requiring
>continuity of d2f/dxdy, because these constraints are linearly related
>to the constraints enforced by the first derivatives.
>
>So, we have 16MN-16M-16N+16 unknowns, and 12MN-16M-16N+20 equations,
>so we are missing 4MN-4 constraints.
>
>Anyone one want to take a stab at defining those constraints?
>
>
>-Geoffrey

***********************************************************
Jonathan L. Sanders
Product Engineering Director
Custom IC Solutions
Cadence Design Systems, Inc.
555 River Oaks Pkwy
San Jose, CA. 95134
  INTERNET:jons@cadence.com Tel: (408) 428-5654 Fax : (408) 944-7027
***********************************************************
Received on Wed Aug 11 08:19:29 2004