Email RIS file
Bookmark
Report an Issue

An efficient algorithm to compute row and column counts for sparse Cholesky factorization [electronic resource].

Published
Washington, D.C. : United States. Dept. of Energy, 1992.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
Physical Description
29 pages : digital, PDF file
Additional Creators
Oak Ridge National Laboratory, United States. Department of Energy, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Free-to-read Unrestricted online access
Summary
Let an undirected graph G be given, along with a specified depth- first spanning tree T. We give almost-linear-time algorithms to solve the following two problems: First, for every vertex v, compute the number of descendants w of v for which some descendant of w is adjacent (in G) to v. Second, for every vertx v, compute the number of ancestors of v that are adjacent (in G) to at least one descendant of v. These problems arise in Cholesky and QR factorizations of sparse matrices. Our algorithms can be used to determine the number of nonzero entries in each row and column of the triangular factor of a matrix from the zero/nonzero structure of the matrix. Such a prediction makes storage allocation for sparse matrix factorizations more efficient. Our algorithms run in time linear in the size of the input times a slowly-growing inverse of Ackermann`s function. The best previously known algorithms for these problems ran in time linear in the sum of the nonzero counts, which is usually much larger. We give experimental results demonstrating the practical efficiency of the new algorithms.
Report Numbers
E 1.99:ornl/tm--12195
ornl/tm--12195
Subject(s)
Other Subject(s)
Note
Published through SciTech Connect.
09/01/1992.
"ornl/tm--12195"
"DE93001254"
Gilbert, J.R.; Ng, E.G.; Peyton, B.W.
Type of Report and Period Covered Note
Topical; 09/01/1992 - 09/01/1992
Funding Information
AC05-84OR21400
View MARC record | catkey: 14351722