Row elimination in sparse matrices using rotations
Esmond Ng · 1983
One way of solving a system of linear equations Ax = b, where A is an m by n matrix, is to use a QR-decomposition of A (or A('T) if m < n). In this thesis we consider the problem of computing the decomposition when A is large and sparse. The approach we use is based on row elimination using rotation matrices. The columns of A are permuted so that the triangular matrix R in the orthogonal decomposition is sparse, and the rows of A are arranged so that the cost of computing R is small. Then the rows of A are eliminated one at a time to generate R. A graph model for studying the row and column ordering problems is proposed. The model allows us to predict the worst possible nonzero structure of R and to relate column and row orderings. Experimental results indicate that the model is a good one in the sense that the predicted structure of R is very close to the actual structure. The graph-theoretic results obtained provide us with a mechanism of constructing good row and column orderings, and of identifying good row orderings for some column orderings. Two column orderings based on dissection techniques are examined and the induced row orderings are characterized. For each of the column orderings we investigate in this thesis, numerical experiments show that there is in general a saving in execution time when the induced row ordering is used. The methods described above assume that the matrix A('T)A is sparse. There are situations in which A('T)A is dense even though A is sparse. They often occur when A contains some dense rows. In those instances, it may be necessary to withhold the dense rows from the orthogonal decomposition. Algorithms for solving linear systems using the withheld rows and the orthogonal decomposition are presented.