11.2 The Algorithm

Figure 11.1: In this figure the calculations performed for one point of the unstructured target grid $B$ are outlined in a two-dimensional example. They are analogous in higher dimensions. The thin orthogonal lines confine the cells of the initial grid $A$, the four sloped lines denote the unstructured grid, and the point in the middle is the one currently considered. The $5^2$ points show which values are used for determining the approximating polynomial.

Figure 11.2: A view of the sample device, where the upper part consists of poly-silicon, the middle part of silicon dioxide, and the lower part of silicon.

Figure 11.3: A cut through the sample device, where the middle part is silicon and the outer part silicon dioxide.

The algorithm works by constructing approximating multivariate Bernstein polynomials in the neighborhood of the points of the unstructured, new grid. Let $A$ be the initial isotropic homogeneous grid, where values are associated with the volume cells, as is usually the case in Monte Carlo simulations of ion implantations, and $B$ the anisotropic inhomogeneous grid, which is to be used in following simulations, where values are associated with the grid points.

For each point of grid $B$, $m^d$ neighboring points are used for constructing an approximation value for the point considered (cf. Figure 11.1), where $m\ge 3$, $m$ odd, and $d$ is the dimension. $m=5$ was chosen in the example below and provides good smoothing results. At the boundary the values of grid $A$ are extended constantly. Thus $m^d$ points are used for constructing a multivariate Bernstein polynomial which is evaluated at the point in the middle in question. Note that it is not necessary to calculate the polynomial explicitly, since each polynomial is later evaluated at one point only. Additionally, it is not necessary to use an affine transformation by assuming that the convex hull of the neighboring points is $[0,1]^d$ and the middle point has coordinates $({1\over2},\ldots,{1\over2})$.

Thus for three dimensions and setting $n:=m-1$, the values of the points of grid $B$ are

$$B_{f,n,n,n}({\textstyle{1\over2},{1\over2},{1\over2}}) = {1\over8... ...}^n \sum_{k_3=0}^n f_{k_1,k_2,k_3} {n\choose k_1}{n\choose k_2}{n\choose k_3},$$

where $f_{k_1,k_2,k_3}$ are the values of the corresponding cell of grid $A$ and $f_{0,0,0}$ has coordinates $(0,0,0)$ and $f_{n,n,n}$ has coordinates $(1,1,1)$.

One of the benefits of this algorithm is that it can be implemented in a straightforward manner in languages like C and Fortran using the expression for $B_{f,n,n,n}({1\over2},{1\over2},{1\over2})$ given above. In order to minimize computation time, the values of the binomial coefficients can be pre-calculated and stored in arrays.

Furthermore, it is fast so that it can be used for grids containing hundreds of thousands of points. Due to the theorems given in Chapter 7, its smoothing and approximating properties are outstanding. Thus it is faster, easier to implement, and approximates and smoothes better than the RSM approach of fitting polynomials of fixed degree.