Maintaining dependencies among supernodes during repeated matrix factorizations

Patent metadata

Field	Value
Publication number	US-8938484-B2
Application number	US-201213487048-A
Country	US
Kind code	B2
Filing date	Jun 1, 2012
Priority date	Jun 1, 2012
Publication date	Jan 20, 2015
Grant date	Jan 20, 2015

Abstract

Advantageously, embodiments of the invention provide techniques for determining dependency relationships between matrix supernodes by storing a list of dependencies for each supernode in a data structure and augmenting this list as needed when a column is moved from one supernode to another while factorizing a series A i of symmetric matrices. As iterating over all supernodes to determine which supernodes a given supernode depends on at the beginning of each factorization adds significant overhead to the computation, embodiments described above maintains a supernode dependency data structure used for each successive factorization, greatly reducing the overhead of the dependency determination.

First claim

What is claimed is:

1. A computer-implemented method for maintaining dependencies among supernodes during repeated matrix factorizations of sparse matrices, comprising:
determining a set of supernodes of the sparse matrices;
for each determined supernode, determining a set of zero or more supernodes on which the supernode depends;
during one or more successive rounds of factorizing the sparse matrices:
deferring at least a column assigned to a first one of the supernodes to a…

Assignees

• Starhill Philip M
• IBM

Inventors

• Starhill Philip M

Classifications

• G06F17/16 Primary

  Physics · mapped topic