9.2. Sparse Matrices

Definition 9.1 (Sparse Matrix)

A sparse matrix is a matrix with a large number of zero elements, compared to the total number of elements. Alternatively, we say a matrix can be considered as sparse if the number of nonzero elements \(nnz \ll (N^{2} + N)/2\)

The Newton iteration solution technique introduces a large amount of computational overhead necessary to solve the linear algebraic system related to the Jacobian matrix of a stiff system of ODEs. Some matrices have particular structure that are more convenient for computational purposes, for example upper triangular matrices, lower triangular matrices and banded matrices. Ordering the columns of a matrix can often make its lower and upper (LU) factors sparser. The simplest such ordering is to sort of columns or rows by nonzero count (i.e by the nonzero elements). This is often a good ordering scheme for matrices with very irregular structure, especially if there is a great variation in the nonzero counts of rows or columns. Therefore, although by ordering of matrices the position of nonzero elements will be different and the resulting ordered matrix will have a completely different structure, this will not change the physical problem in any way and the reordering will have a significant impact on the solution techniques. As an example, if Gaussian Elimination method is used (e.g. in the GEAR, LSODE and VODE solvers) on an ordered matrix, then none or very few fill-ins (of originally zero entries) will occur in the factorization processes, i.e. the L and U parts of the LU factorization will have the same structures as the lower and upper parts of the original matrix, respectively. Thus, ordering allows the sparsity structure of the system to be preserved in the factorization processes.