Patent ID: 6470368
Filing Date: 2002-10-22
Classification: G06F

Abstract:
A method for efficiently solving a system of equations involving a sparse matrix, comprising:receiving the sparse matrix as part of an equation to solve; identifying a plurality of supernodes in the sparse matrix, each supernode comprising a set of contiguous columns having a substantially similar pattern of non-zero elements; splitting each supernode into vertical panels, wherein a size of a vertical panel is, at most, half of a cache size on a specified computer; and performing a modification (CMOD) operation between a source supernode and a destination supernode from the plurality of supernodes by, determining a subset of the source supernode that will be used in creating an update for the destination supernode, partitioning the subset of the source supernode into a plurality of tiles, each tile being a rectangular shape of fixed dimensions chosen so as to substantially optimize a computational performance of the CMOD operation on a particular computer architecture, and for each tile in the plurality of tiles, computing a corresponding portion of the update for the destination supernode using a Local dense CMOD operation; whereby splitting each supernode into vertical panels increases cache hits on the specified computer.