Row-ordering schemes for sparse givens transformation. III. analyses for a model problem

AbstractIn [7,8], we showed that a good row ordering can be obtained from a width-1 nested-dissection column ordering in the orthogonal decomposition of sparse matrices using Givens transformations. The objective of this paper is to analyze a model k×k grid problem and to show that the number of multiplicative operations required to transform the sparse rectangular matrix associated with the model problem is O(k3) if width-1-nested dissection column ordering and the associated good row ordering are used. We also demonstrate that if the column ordering is a (width-1 or width-2) nested-dissection ordering, there exists a row ordering such that the cost of the computation is at least O(k4)