Row-ordering schemes for sparse Givens transformations. II. Implicit graph model (Q1078976)

[For part I see ibid. 61, 55-81 (1984; Zbl 0557.65018.] Let A be a sparse \(m\times n\) matrix (m\(\geq n)\), let \(P_ r,P_ c\) be permutation matrices of order m and n respectively and let \(P_ rAP_ c\) be reduced to upper trapezoidal form R using Givens rotations. The sparsity structure of R depends only on the column ordering of A, i.e. on \(P_ c\). For a given \(P_ c\) the number of nontrivial rotations and therefore the number of arithmetic operations depends on the row ordering of A, i.e. on \(P_ r\). A graph model is presented for the row annihilation using Givens rotations. Symmetric graphs of \((a^ i)^ T(a^ i)\), where \(a^ i\) denotes the i-th row of A, are employed to study the row ordering problem for this elimination process. It is an implicit model in the sense that rows and columns of A are not explicitly represented in the graph. The graph theoretic results obtained are used to show how good row orderings can be obtained for width-1 and width-2 nested-dissection column orderings.