4.8 The Pre-Elimination

The main matrix $\ensuremath{\mathbf{A}}_{\mathrm{s}}$ consists of fluxes that will (if the control functions are correctly assigned to the variables) satisfy the criterion of diagonal dominance which is necessary to make the linear equation system solvable with an iterative solver (see Section 4.4).

The transformations and additional terms imposed by the boundary conditions may heavily disrupt this feature both in structural and numerical aspects. Some of the boundary or interface conditions can make the full system matrix so ill-conditioned thereby simply preventing iterative linear solvers to converge.

This problem can be simply passed to the solver module which is likely to employ a direct solver to solve such heavily ill-conditioned problems. Alternatively, an elimination concept as designed and presented in [65] can be pursued which applies a Gaussian elimination to some parts of the linear equation system only. It is important to note that this solving capability is part of the assembly module. It is possible to disable this feature and pass the complete linear equation system to the solver module (after sorting and scaling, if enabled).

The elimination concept is based on the idea to apply Gaussian elimination to the problematic or critical equations before the system is passed on to the linear solver. After the iterative solver has converged, the eliminated variables are calculated by back-substitution into the eliminated equations. This process is thus a partial Gaussian factorization of the matrix, which is called pre-elimination in the context of the assembly module.

Before these equations can be eliminated, they are sorted to the end of the matrix, together with their assigned variables. This is done by applying a permutation matrix $\mathbf{P}$ to the linear equation system. The permutation matrix is calculated automatically on solving the system. All equations causing a possible ill condition have to be marked for pre-elimination by the simulator.

Figure 4.1: All equations marked for pre-elimination (*) are moved to the outer system matrix, the others remain in the inner one [65,228].

The outer system is removed from the linear equation system and later solved by Gaussian elimination, the inner system with an improved condition suitable for iterative solvers is passed on to the solver module. See Figure 4.1 [65,228] for an illustration of this concept. The resulting system is given by

$$(\ensuremath{\mathbf{E}} \ensuremath{\mathbf{P}} \ensuremath{\til... ...bf{E}} \ensuremath{\mathbf{P}} \ensuremath{\tilde{\ensuremath{\mathbf{b}}}})\ ,$$ (4.21)

where $\mathbf{P}$ is the permutation matrix with its inverse equal to its transposed matrix $\ensuremath{\mathbf{P}}^\mathrm{T}$. As the factorization starts with the last equation and proceeds upwards, the usual terms for direct Gaussian LU factorizations have a different meaning. The upper triangular matrix $\mathbf{E}$ stores the elimination coefficients obtained as the lower matrix $\mathbf{L}$ of a Gaussian elimination. It contains non-zero off-diagonals in the outer parts only, the inner matrix domain is a strict unity matrix. The unity diagonal of $\mathbf{E}$ is not stored. The result of the multiplication of $\mathbf{E}$ with $\mathbf{A}$ is a matrix with some (but not all) entries in the domain right of the diagonal removed, and some newly created entries. This matrix is split into two parts: the core matrix containing all equations of the inner matrix and the outer matrix.

In Figure 4.2 the effect of the pre-elimination for the system matrix shown. The so-called inner system matrix does not contain the problematic equations any more, for example the equations in rows 1-44 of the complete system matrix. It is obvious that the majority of equations remains in the inner system matrix. Thus, the effort of the Gaussian elimination is kept small whereas the solver module is expected to bear the main solving effort.

Figure 4.2: On the left the completely compiled system matrix of a discretized two-dimensional MOS transistor structure assembled by MINIMOS-NT is shown. The magnitude of the entries are encoded by the colors according to the legend in the right. Some regions with problematic equations are indicated by red dashed rectangles. After the pre-elimination, the inner system matrix (right) does not contain the problematic equations any more. The dimension is not significantly reduced since the majority of equations is not affected.