Row-ordering schemes for sparse Givens transformations. I. Bipartite graph model (Q761765)

Row-ordering schemes are studied for Givens transformations in the computation of the QR decomposition of a large sparse \(m\times n\) matrix, where \(m\geq n\). Row-orderings do not effect the sparsity of the upper triangular factor but can have significant impact on the amount of computation required to compute the decomposition. The reduction is modeled by a sequence of bipartite graphs, and the number of nontrivial rotations and the number of arithmetic operations are both expressed in terms of adjacency relations in this sequence of bipartite graphs. This suggests several ways in which good row-orderings can be determined.