Row-ordering schemes for sparse givens transformations. I. bipartite graph model |
| |
Authors: | Alan George Joseph Liu Esmond Ng |
| |
Institution: | Department of Computer Science University of Waterloo Waterloo, Ontario, Canada N2L 3G1;Department of Computer Science York University Downsview, Ontario, Canada M3J 1P3;Department of Computer Science University of Waterloo Waterloo, Ontario, Canada N2L 3G1 |
| |
Abstract: | Let A be an m-by-n matrix, m?n, and let Pr and Pc be permutation matrices of order m and n respectively. Suppose PrAPc is reduced to upper trapezoidal form using Givens rotations, where R is n by n and upper triangular. The sparsity structure of R depends only on Pc. For a fixed Pc, the number of arithmetic operations required to compute R depends on Pr. In this paper, we consider row-ordering strategies which are appropriate when Pc is obtained from nested-dissection orderings of ATA. Recently, it was shown that so-called “width-2” nested-dissection orderings of ATA 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|