Back to search

University of British Columbia

Incomplete factorization preconditioners for least squares and linear and quadratic programming

Abstract

dc:description

Many algorithms for optimization are based on solving a sequence of symmetric indefinite linear systems. These systems are often large and sparse, and the main approaches to solving them are based on direct factorization or iterative Krylovbased methods. In this thesis, we explore how incomplete sparse factorizations can be used as preconditioners for the special case of quasi-definite linear systems that arise in regularized linear and quadratic programming, and the case of least-squares reformulations of these systems. We describe two types of incomplete factorizations for use as preconditioners. The first is based on an incomplete Cholesky-like factorization. The second is based on an incomplete Householder QR factorization. Our approximate factorizations allow the user to prescribe the amount of fill-in, and therefore have predictable storage requirements. We use these incomplete factorizations as preconditioners for SYMMLQ and LSQR, respectively, and present numerical results for matrices that arise within an interior-point context.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sirovljevic, Jelena

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/32071

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Sirovljevic, Jelena. Incomplete factorization preconditioners for least squares and linear and quadratic programming. master's thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/32071