Row-ordering schemes for sparse givens transformations. II. implicit graph model

AbstractA new graph model is presented to study the row annihilation and row ordering problems in the QR decomposition of sparse matrices using Givens rotations. The graph-theoretic results obtained can be used to derive good row orderings for certain column orderings, such as width-1 and width-2 nested dissection orderings. This model is different from the bipartite-graph model introduced in [6]. We refer to the new model as implicit because the rows are not represented explicitly by nodes, in contrast to the bipartite-graph model, where the rows are represented by nodes in a bipartite graph