IMPLEMENTING GAUSSIAN ELIMINATION WITH SYMBOLIC FACTORIZE

We discuss implementation techniques for sparse Gaussian elimination, based on an analysis of the sparsity pattern without regard to numerical values. This includes a discussion of data structures for pivot selection, the use of cliques, and the use of both dynamic and static data structures. We examine the division of the solution into the distinct phases of reordering, symbolic factorization, numerical factorization, and solution, indicating the high efficiency with which these steps can now be performed.

Introduction

The difference between this chapter and the previous one is that here an initial pivotal sequence is chosen from the sparsity pattern alone and is used unmodified or only slightly modified in the actual factorization. When it is applicable, this approach can exhibit a significant advantage over the methods of Chapter 10. Here, ANALYSE will usually be less expensive than FACTORIZE, rather than very much more expensive. Additionally, ANALYSE can usually be performed in place, which allows it to be implemented in static storage. At the completion of ANALYSE, we can compute the work and storage requirements for FACTORIZE provided no numerical pivoting is performed.

We begin (Sections 11.2 and 11.3) with the implementation of pivot selection by the minimum degree and approximate minimum degree algorithms, which were introduced in Section 7.3. We then look at pivot selection by the dissection schemes from Chapter 9 and their combination with minimum degree. Using one of these orderings for the actual factorization of a matrix is considered in Section 11.5. The case where additional pivoting for numerical stability is needed is considered in Section 11.6.

We described the data structures used to carry out the ordering of a matrix to band and variable band form in Sections 8.2 and 8.3. In Sections 11.7 and 11.8, we describe the data structures to carry out the numerical factorization efficiently using these orderings. We note that these are very different from the data structures used for minimum degree, dissection, and their variants in Sections 11.5 and 11.6.

The frontal method is a variation of the variable-band technique that was developed for finite-element problems though it is not restricted to them. It is most straightforward for symmetric and positive-definite systems. The frontal method is described in Sections 11.9-11.12.

Because of the power of these methods, we can apply them in cases where diagonal pivot selection might be numerically unstable, but that requires a two- step process. We select the initial ordering in the ANALYSE phase as discussed, but then allow for modifications of the selected sequence in the FACTORIZE phase. This extension can apply for dissection, banded, and frontal methods, so we have considered this option in the discussion of the various methods. The added complication is that numerical pivoting may create additional fill-in, or widen the band in the case of banded systems, but does not necessarily do so. It does increase the times for FACTORIZE, however, and the work and storage forecasts from ANALYSE need not be sustained in FACTORIZE.

We conclude the chapter with some remarks on parallelism in Section 11.13.