University of Victoria (Canada)
Ordering givens transformations for sparse QR factorization
Abstract
dc:description.abstractThe QR factorization of a matrix A is commonly used to solve least squares problems. One way to compute such a factorization is by using Givens transformations. When A is sparse, the precise order in which the transformations are applied can affect the amount of storage required. In this work we present an ordering for the Givens transformations that is optimal with regard to storage (a so-called "tight" ordering) and that preserves sparsity by restricting fill to those locations in R that are necessarily nonzero when A has the Hall property. This ordering is of particular interest when A does not have the strong Hall property and is not permuted into block upper trapezoidal form. We describe a bipartite graph model of sparse matrix structures, and summarize the characterization of the structures of the factors Q and R. We define the product of structures of matrices, determine the product of the structures of a sequence of Givens transformations, and define a tight ordering for the Givens transformations We then present a family of tight orderings for a given matrix structure.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 1992
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gillespie, Mary Irene
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1828/17895