Subsections

• 4.12.1 The Administration Scheme
• 4.12.2 Newton Adjustment Levels
• 4.12.3 Improved Sorting Feature

4.12 Newton Adjustment

One possibility to speed up the assembly process is to reuse already allocated MCSR structures for the next Newton iteration step. For some applications such as semiconductor device simulation, this should be possible since the structure of the equation system hardly ever changes: on the one side, the mesh used in the simulation remains normally unmodified, on the other side changes in the Newton iteration regarding models, quantities, or iteration schemes occur infrequently. Furthermore, the efficiency of the Newton adjustment can be increased if separate equation systems are created for each activated simulation mode and iteration scheme. Consequently, the assembly module provides two assembly modes: first, the conventional assembly mode based on flexible sparse structures (see Section 4.6), and second the Newton adjustment mode presented here.

The benefit of the Newton adjustment does not only originate from fewer memory allocations and deallocations but also from the possibility to skip symbolic phases of all involved mathematical operations. For sparse matrices, a mathematical operation must first count the required number of entries in the result, which is done in the symbolic phase. Then, the result structure is allocated and the actual mathematical operation is performed.

However, if one entry in the structure intended to be reused is missing, measures have to be taken to correct this so-called Newton adjustment error. One possibility might be to add the missing entry to the structure, which is a cumbersome and complicated task (see also Section 4.13.3). However, it is advantageous to simply restart the complete assembly in the conventional assembly mode.

The reasons for this are:

• Restarting is a simpler solution since no additional code is required.
• The circumstances when Newton adjustment errors occur are known in advance. Therefore, the simulator should take care of the correct settings and avoid Newton adjustment errors in advance as well.
• The effort of the enlargement algorithms must not be neglected since several requirements have to be met (see also Section 4.13.3).
• For the same reasons, there is no code provided which copies the already assembled entries to flexible sparse structures and silently continues in the conventional mode.

4.12.1 The Administration Scheme

In the first implementation of the assembly module the main class was supposed to be bound to one linear equation system or one Newton iteration step, respectively. The class provided two administration methods: one method was responsible for allocating all required structures, the other one for their deallocation. In other words, the new modules were designed for solving one linear equation system during the life cycle between construction and destruction as illustrated in the left of Figure 4.5. Some information the next step could benefit from is stored in the separate parameter class, for example the fill-in control parameter.

This administrative scheme of the main assembly class was changed in the refined version of the module: the class itself should be used for all iterations of a complete Newton approximation. Only some of its members should be allocated for a single iteration only and deleted afterwards. Since the structure was divided into two parts with different life times, a division of the allocation and deallocation process as depicted in the center of Figure 4.5 was necessary.

Figure 4.5: Former (left), refined (center), and final (right) administrative scheme.

The step from the former to the refined scheme does not result in a Newton adjustment, but lays the foundations for actually reusing already allocated structures. The final administrative scheme is shown in the right figure of Figure 4.5. If Newton adjustment is activated, the already existing assembly structures are not deallocated but kept in the memory after reinitialization. In the case of a Newton adjustment error, the conventional assembly mode is used instead. Note that in this figure the Newton deallocation is not separately shown any more, because it is implicitly called by the allocation and the class deallocation.

4.12.2 Newton Adjustment Levels

The Newton adjustments were introduced in three levels. Level two and three depend on the success of the preceding one.

1. The first level reuses the structure of all four matrices of the assembly process: $\ensuremath{\mathbf{A}}_{\mathrm{b}}$, $\ensuremath{\mathbf{A}}_{\mathrm{s}}$, $\ensuremath{\mathbf{T}}_{\mathrm{b}}$, and $\ensuremath{\mathbf{T}}_{\mathrm{v}}$. If a Newton adjustment error occurs, the simulator must correct the situation, preferably by restarting the complete assembly in the conventional assembly mode.
2. The second level reuses all resulting structures created during the compilation of the complete linear equation system. In contrast to the first level the assembly process is already finished at execution time. Thus, in the case of a Newton adjustment error the simulator is not affected at all.
3. The third level reuses all matrices resulting from the pre-elimination process. As for the second step, Newton adjustment errors are corrected internally.

An overview about the Newton adjustment is given in Table 4.2.

Table 4.2: Newton adjustment levels.

Level	Status	Target	Errors
1	assembly	$\ensuremath{\mathbf{A}}_{\mathrm{b}}$, $\ensuremath{\mathbf{A}}_{\mathrm{s}}$, $\ensuremath{\mathbf{T}}_{\mathrm{b}}$, and $\ensuremath{\mathbf{T}}_{\mathrm{v}}$	handled by simulator
2	compilation	compilation results	handled internally
3	pre-elimination	pre-elimination results	handled internally

The Newton adjustment levels do not change the sequence of mathematical operations, so both assembly modes yield exactly the same linear equation systems and exactly the same solution is obtained. Thus, the Newton adjustment levels are a performance improvement feature only - and do not affect the accuracy or any values at all.

4.12.3 Improved Sorting Feature

In the implementation of the sorting permutation of the inner linear equation system an additional potential for speed-up can be identified. This possibility is related to the Newton adjustment, because a conventional mode is involved as well. In this mode, a sorting vector is calculated and applied. However, once the sorting vector is known, it can be already used during pre-elimination. This saves not only the recalculation of the sorting vector, but makes it also possible (and necessary) to skip the sorting permutation.

The lower part of the pre-elimination vector is basically initialized by ascending indices. If both sorting and pre-elimination are enabled, the already existing sorting vector can directly become the lower part of the pre-elimination vector. If the inner system matrix is already sorted, the subsequent sorting must be skipped. As already discussed for the Newton adjustment levels, the simulator is responsible for setting the appropriate parameters to have the sorting vector recalculated if respective modifications make this necessary.

In contrast to the Newton adjustment levels, the improved sorting feature causes a changed sequence of mathematical operations and thus different results are observed.