Home Geography Direct methods for sparse matrices
Frontal methods: general finite-element problems
The frontal technique can also be applied to systems which need numerical pivoting. To help visualize this, we show in Figure 11.11.1 the situation after an assembly, but prior to another set of eliminations. Blocks (1,1), (1,2), (2,1), and (2,2) correspond to the frontal matrix at this stage. Any entry whose row and column is fully summed (that is, any entry in block (1,1) of Figure 11.11.1) may be used as a pivot. For unsymmetric matrices, we may use the threshold criterion
where u is a given threshold, see Section 5.2. The pivot must be chosen from the
(1.1) block of Figure 11.11.1, but the maximum is taken over blocks (1,1) and
(2.1) . Note that if unsymmetric interchanges are included, the index list for the rows in the front will differ from the index list of the columns and will require separate storage. In the symmetric case, we may maintain symmetry by using either a diagonal pivot that satisfies inequality (11.11.1) or a 2x2 pivot
Fig. 11.11.1. Reduced submatrix after an assembly and prior to another set of eliminations. The block of the front that is partially summed is labelled ps and the parts that are fully summed are labelled fs.
all of whose coefficients are fully summed and that satisfies the inequality see inequality (5.2.9).
It is possible that we cannot choose pivots for the whole of the frontal matrix because of small entries in the front or large off-diagonal entries that lie outside the block of the fully-summed rows and columns (that is, because they lie in block (1,2) or block (2,1) of Figure 11.11.1). In this case, we simply leave the variables in the front, continue with the next assembly, and then try again. It is always possible to complete the factorization using this pivotal strategy because each entry eventually lies in a fully-summed row and in a fully-summed column, at which stage it may be chosen as a diagonal pivot or its row and column can define a 2x2 pivot. Naturally, if many eliminations are delayed, the order of the frontal matrix might be noticeably larger than it would have been without numerical pivoting. We will discuss this further in Section 12.8.
Note that this is an example of a posteriori ordering for stability. We choose an ordering for the variables that keeps the front small without worrying about the possibility of instability, and we ensure the stability during the numerical factorization. This is an approach that we shall use extensively in the next chapter.
|< Prev||CONTENTS||Next >|