4.11 Solving and Back-Substitution

The solver module is responsible for calculating the solution vector of the inner linear equation system. Basically, it is a separate module, but is invoked by the assembly module. As discussed in the next chapter, the solver module provides three in-house solvers as well as an interface to external solver modules. To summarize the various steps between assembling the linear equation system and returning its complete solution vector to the simulator, a schematic overview is given in Figure 4.4.

Figure 4.4: Schematic assembly overview.

In the upper left corner the Newton iteration control of the simulator is represented, which uses an interface class to access the assembly. The inputs of the assembly module are the contributions of the various segment and boundary models implemented in the simulator, which are subsequently called. Following the black solid lines beginning at the interface, the four matrices $\ensuremath{\mathbf{T}}_{\mathrm{b}}$, $\ensuremath{\mathbf{A}}_{\mathrm{s}}$, $\ensuremath{\mathbf{A}}_{\mathrm{b}}$, and $\ensuremath{\mathbf{T}}_{\mathrm{v}}$ are assembled by using the flexible sparse storage class based on balanced binary trees.

These structures are then converted to the MCSR format and compiled resulting in the complete linear system, which is pre-eliminated to obtain the inner and outer system. The inner one is sorted, scaled, and finally passed to the solver module. After the solver module has returned the solution vector (or solution vectors in case of multiple right-hand-side vectors), the assembly module has to back-substitute the pre-eliminated equations as well as revert scaling, sorting, and the variable transformation to obtain the complete solution vector(s).

The Newton adjustment levels (red dashed lines) reuse already existing MCSR structures to reduce the assembling effort: the flexible sparse structures may be skipped completely, and during compilation and pre-elimination much simpler functions (red bold boxes) can be used than in the conventional mode (black bold boxes with slash). The latter requires symbolic phases in order to calculate the result storage requirements, which are known for the already existing structures. In the next section, the Newton adjustment is described in more detail.

As the assembly module also provides an interface to a system for calculating eigenvalues, the system matrices shown in Figures 4.2 and 4.3 have been analyzed. The spectral condition for a non-symmetric matrix [52] is given by

$$\kappa_{\mathrm{s}}(\ensuremath{\mathbf{A}}) = \sqrt{\frac{\lambd... ...\mathrm{T}}})}{\lambda_\mathrm{min}(\ensuremath{\mathbf{A A^\mathrm{T}}})}} \ .$$ (4.26)

The results summarized in Table 4.1 have been obtained by the ARPACK package [128], which stands for Arnoldi Package and provides a collection of FORTRAN 77 subroutines for the solution of large scale eigenvalue problems. The package can be applied for Hermitian, non-Hermitian, standard or generalized eigenvalue problems. It is designed to compute a user-specified number of eigenvalues only, for example the largest or smallest eigenvalue. The ARPACK package links against the LAPACK and BLAS libraries (see Section 5.1).

Table 4.1: Eigenvalues of the compiled, pre-eliminated, sorted, and scaled system matrix.

System matrix after	$\lambda_\mathrm{max}(\ensuremath{\mathbf{A A^\mathrm{T}}})$	$\lambda_\mathrm{min}(\ensuremath{\mathbf{A A^\mathrm{T}}})$	$\kappa_{\mathrm{s}}$
compiling	230.323	$2.53722 \times 10^{-35}$	$3.01294 \times 10^{18}$
pre-elimination	574.806	$4.26668 \times 10^{-17}$	$3.67042 \times 10^{09}$
sorting	574.806	$4.32143 \times 10^{-17}$	$3.64709 \times 10^{09}$
scaling	4.28363	$1.32148 \times 10^{-12}$	$1.80043 \times 10^{06}$

A spectral condition in the order of $10^c$ and the precision of the numeric representation of $10^{-p}$ approximately results in an error of $10^{c-p}$ [52]. Thus, a small error follows from a small residual only for a small condition number [188]. As it is demonstrated by the results in Table 4.1, the condition number is significantly improved by twelve orders of magnitude due to the applied measures.