dc.contributor.author Coleman, Thomas F. en_US dc.contributor.author Edenbrandt, Anders en_US dc.contributor.author Gilbert, John R. en_US dc.date.accessioned 2007-04-23T16:49:28Z dc.date.available 2007-04-23T16:49:28Z dc.date.issued 1983-10 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-578 en_US dc.identifier.uri https://hdl.handle.net/1813/6418 dc.description.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. en_US dc.format.extent 1986760 bytes dc.format.extent 549953 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Predicting Fill for Sparse Orthogonal Factorization en_US dc.type technical report en_US
﻿