Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Predicting Fill for Sparse Orthogonal Factorization
Authors: Coleman, Thomas F.
Edenbrandt, Anders
Gilbert, John R.
Keywords: computer science
technical report
Issue Date: Oct-1983
Publisher: Cornell University
Abstract: In solving large sparse linear least squares problems $Ax \cong b$, several different numeric methods involve computing the same upper triangular factor $R$ of $A$. It is of interest to be able to compute the nonzero structure of $R$, given only the structure of $A$. The solution to this problem comes from the theory of matchings in bipartite graphs. The structure of $A$ is modeled with a bipartite graph and it is shown how the rows and columns of $A$ can be rearranged into a structure from which the structure of its upper triangular factor can be correctly computed. Also, a new method for solving sparse least squares problems, called block back-substitution, is presented. This method assures that no unnecessary space is allocated for fill, and that no space is needed for intermediate fill.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
83-578.pdf1.94 MBAdobe PDFView/Open
83-578.ps537.06 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us