Back to search

University of Victoria (Canada)

Ordering givens transformations for sparse QR factorization

Abstract

dc:description.abstract

The 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 opti­mal 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 × 1

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1828/17895

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gillespie, Mary Irene. Ordering givens transformations for sparse QR factorization. Master of Science M.Sc. thesis, 1992. https://hdl.handle.net/1828/17895