Row-ordering schemes for sparse Givens transformations. II. Implicit graph model
type: Item
instance of: scholarly article
title: Row-ordering schemes for sparse Givens transformations. II. Implicit graph model
zbMATH Open document ID: 0596.65011
DOI: 10.1016/0024-3795(86)90190-4
author: B. George
published in: Linear Algebra and its Applications
publication date: 1986-01-01T00:00:00Z
review text: [For part I see ibid. 61, 55-81 (1984; Zbl 0557.65018.] Let A be a sparse \(m\times n\) matrix (m\(\geq n)\), let \(P_ r,P_ c\) be permutation matrices of order m and n respectively and let \(P_ rAP_ c\) be reduced to upper trapezoidal form R using Givens rotations. The sparsity structure of R depends only on the column ordering of A, i.e. on \(P_ c\). For a given \(P_ c\) the number of nontrivial rotations and therefore the number of arithmetic operations depends on the row ordering of A, i.e. on \(P_ r\). A graph model is presented for the row annihilation using Givens rotations. Symmetric graphs of \((a^ i)^ T(a^ i)\), where \(a^ i\) denotes the i-th row of A, are employed to study the row ordering problem for this elimination process. It is an implicit model in the sense that rows and columns of A are not explicitly represented in the graph. The graph theoretic results obtained are used to show how good row orderings can be obtained for width-1 and width-2 nested-dissection column orderings.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 3960863
zbMATH Keywords: QR decomposition
zbMATH Keywords: Givens rotations
zbMATH Keywords: graph model
zbMATH Keywords: Symmetric graphs
zbMATH Keywords: row ordering
zbMATH Keywords: elimination
zbMATH Keywords: width-1 and width-2 nested-dissection column orderings
describes a project that uses: symrcm
MaRDI profile type: Publication
full work available at URL: 0024-3795(86)90190-4
OpenAlex ID: W4251673455
cites work: Q4101346
cites work: Nested Dissection of a Regular Finite Element Mesh
cites work: Solution of sparse linear least squares problems using Givens rotations
cites work: An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
cites work: Q3664299
cites work: Row-ordering schemes for sparse Givens transformations. I. Bipartite graph model
cites work: Row-ordering schemes for sparse Givens transformations. III. Analyses for a model problem
cites work: On Row and Column Orderings for Sparse Least Squares Problems
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
Wikidata QID: Q126321647
description: scientific article; zbMATH DE number 3960863