A generalized form of the envelope method is proposed for the solution of large sparse symmetric and positive definite matrices by rows. The method is demonstated to have practical advantages over the conventional column-oriented factorization using compressed column storage or the multifrontal method using full frontal submatrices.

This paper provides an efficient algorithm for generating an ordering suitable for the parallel elimination of nodes in chordal graphs. The time complexity of the reordering algorithm is shown to be linear in the size of the chordal graph. The basic parallel pivoting strategy is originally by Jess and Kees [IEEE Trans. Comput., C-31 (1982), pp. 231–239]. The relevance of the reordering to parallel factorization of sparse matrices (not necessarily chordal) is also discussed.

A heuristic graph partitioning scheme is presented to determine effective node separators for undirected graphs. An initial separator is first obtained from the minimum degree ordering, an algorithm designed originally to produce fill-reducing orderings for sparse matrices. The separator is then improved by an iterative strategy based on some known results from bipartite graph matching. This gives an overall practical scheme in partitioning graphs. Experimental results are provided to demonstrate the effectiveness of this heuristic algorithm on graphs arising from sparse matrix applications.

In this paper, we show that the multifrontal method can have significant advantage over the conventional sparse column-Cholesky scheme on a paged virtual memory system. A more than tenfold reduction in paging activities can be achieved, which saves as much as 20 percent in factorization time. We also introduce a hybrid sparse factorization method, which uses a mixture of column-Cholesky and submatrix-Cholesky operations. By switching to the use of frontal matrices from column-Cholesky operations at appropriate columns, we demonstrate that the proposed hybrid scheme has an advantage over the sparse column-Cholesky method in reducing paging activities and over the multifrontal method in its adaptability to the amount of available working storage.

It is well known that the partial pivoting strategy by Bunch and Kaufman is very effective for factoring dense symmetric indefinite matrices using the diagonal pivoting method. In this paper, we study a threshold version of the strategy for sparse symmetric matrix decomposition. The use of this scheme is explored in the multifrontal method of Duff and Reid for sparse indefinite systems. Experimental results show that it is at least as effective as the existing pivoting strategy used in the current multifrontal implementation.

A simple modification to the numerical pivot selection criteria in the multifrontal scheme of Duff and Reid for sparse symmetric matrix factorization is presented. For a given threshold value, the modification allows a broader choice of block 2 X 2 pivots owing to a less restrictive pivoting condition. It also extends the range of permissible threshold values from [0, 1/2) to [0, 0.6404). Moreover, the bound on element growth for stability consideration in the modified scheme is nearly the same as that of the original strategy.

Two techniques are introduced to reduce the working storage requirement for the recent multifrontal method of Duff and Reid used in the sparse out-of-core factorization of symmetric matrices. For a given core size, the reduction in working storage allows some large problems to be solved without having to use auxiliary storage for the working arrays. Even if the working arrays exceed the core size, it will reduce the amount of input-output traffic necessary to manipulate the working vectors. Experimental results are provided to demonstrate significant storage reduction on practical problems using the proposed techniques.

The most widely used ordering scheme to reduce fills and operations in sparse matrix computation is the minimum-degree algorithm. The notion of multiple elimination is introduced here as a modification to the conventional scheme. The motivation is discussed using the k -by- k grid model problem. Experimental results indicate that the modified version retains the fill-reducing property of (and is often better than) the original ordering algorithm and yet requires less computer time. The reduction in ordering time is problem dependent, and for some problems the modified algorithm can run a few times faster than existing implementations of the minimum-degree algorithm. The use of external degree in the algorithm is also introduced.

A fundamental problem in the computer solution of a sparse, N by N, positive definite system of equations $Ax = b$ is, given the structure of A, to determine the structure of its Cholesky factor L, where $A = LL^T $. This problem arises because it is often desirable to set up a data structure for L before the numerical computation is performed, and in order to do this we must know the positions of the nonzeros of L. We describe a representation$\mathcal {R}_L $ for L which typically requires far fewer data items than the number of nonzeros in L, and an algorithm is then described which generates $\mathcal {R}_L $. The time and space complexity of the algorithm is shown to be $O(|A|,|\mathcal {R}_L |)$, and can never be worse than $O(|L|)$. Here $|\mathcal {R|}_L |$ denotes the number of items in the data structure for L, and $|A|$ (and $|L|$ denote the number of nonzeros in A and L respectively. For a certain class of problems, we show that the execution time of the algorithm is $O(N)$, even though $|L|$ is $O(N\log N)$. We also provide some numerical results showing that the algorithm can be implemented so that the program performance reflects its theoretically predicted behavior.

This paper describes a very fast implementation of the m~n~mum degree algorithm, which is an effective heuristm scheme for fmding low-fill ordermgs for sparse positive definite matrices.This implementation has two important features: first, in terms of speed, it is competitive with other unplementations known to the authors, and, second, its storage requirements are independent of the amount of fill suffered by the matrix during its symbolic factorization.Some numerical experiments which compare the performance of this new scheme to some existing minimum degree programs are provided.

Umversity of

The need to find nodes with large eccentricity arises in many heuristic algorithms for ordering sparse matrix equations.A computer program is presented here for finding such nodes, based on an algorithm due to Gibbs, Poole, and Stockmeyer.Several changes have been made to their original method, and experiments suggest that these changes improve its reliability and execution time.