Row-ordering schemes for sparse Givens transformations. III. Analyses for a model problem (Q1078977)

In part I [ibid. 61, 55-81 (1984; Zbl 0557.65018)] and part II [ibid. 75, 203-223 (1986; reviewed above)] two graph models are introduced to study the row ordering problem for the QR decomposition of a sparse matrix using Givens rotations. In this paper these two graph models are used to analyse a model problem. It is a large sparse overdetermined linear system with \(4(k-1)^ 2\) equations and \(k^ 2\) unknowns, where each row of the coefficient matrix contains only 4 nonzero entries. It is shown that for a good row ordering induced by the width-1 nested dissection column ordering the number of multiplications required in computing the QR decomposition with rotation is \(O(k^ 3)\). This is comparable with the number of multiplications required if a width-2 nested dissection column labeling and the induced row ordering is used. It is also demonstrated that for a width-1 or a width-2 nested dissection column ordering there exist row orderings for which the computation needs at least \(O(k^ 4)\) multiplications.