Patent ID: 6601080
Filing Date: 2003-07-29
Classification: G06F

Abstract:
A method for efficiently solving a system of equations involving a sparse matrix, comprising: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; and performing a complex modification (CMOD) operation on the plurality of supernodes including doing the following for each supernode, determining a structure of the supernode, using a one-dimensional trapezoidal representation for the supernode during the CMOD operation if a result of a function on the structure of the supernode is lower than a threshold value, and using a two-dimensional rectangular representation for the supernode during the CMOD operation if the result of the function on the structure of the supernode is greater than the threshold value; wherein the function on the structure of the supernode is a function of memory requirements for storing the supernode in the two-dimensional rectangular representation and rnemoirX requirements for storing the supernode in the one-dimnensional trapezoidal representation; and wherein choosing between the one-dimensional trapezoidal representation and the two-dimensional rectangular representation automatically adapts the method to a problem structure and machine characteristics at run-time of a computer system.