Direct Sparse Interval Hull Computations for Thin Non-M-Matrices
Fernando L. Alvarado, Zian Wang · 1994
The computation of an enclosure for the solution of a sparse set of linear equations Ax = b with a thin matrix A and an interval right hand side b is considered. Gaussian elimination works well when the matrix is an M-matrix, but fails when the matrix is a general matrix. This paper illustrates how, for sparse matrices, an ordering intended to reduce the height of the elimination tree (and thus enhance parallelism of computations) can reduce the growth in the interval solution for general non-M-matrices. For banded matrices, it is shown that the growth in intervals is bounded by n, where n is the dimension of the matrix, rather than 2 n . This result appears to hold for other types of sparse matrices. A second method based on singleton right hand side representations of b is shown to yield the hull of the solution. Best results are obtained by a combination of the singleton solver with path length shortening permutations.