Row-ordering schemes for sparse givens transformations. I. bipartite graph model

Let A be an m-by-n matrix, m?n, and let P_r and P_c be permutation matrices of order m and n respectively. Suppose P_rAP_c is reduced to upper trapezoidal form $\text{(}\text{R}\text{O}\text{)}$ using Givens rotations, where R is n by n and upper triangular. The sparsity structure of R depends only on P_c. For a fixed P_c, the number of arithmetic operations required to compute R depends on P_r. In this paper, we consider row-ordering strategies which are appropriate when P_c is obtained from nested-dissection orderings of A^TA. Recently, it was shown that so-called “width-2” nested-dissection orderings of A^TA could be used to simultaneously obtain good row and column orderings for A. In this series of papers, we show that the conventional (width-1) nested-dissection orderings can also be used to induce good row orderings. In this first paper, we analyze the application of Givens rotations to a sparse matrix A using a bipartite-graph model.