Hybrid representation scheme for factor L in sparse direct matrix factorization

摘要

A system that efficiently performs a CMOD operation in solving a system of equations involving a sparse coefficient matrix by identifying supernodes in the sparse matrix. Each supernode comprises a set of contiguous columns having a substantially similar pattern of non-zero elements. The system performs a CMOD operation on each supernode, by determining a structure for the supernode, and computing a function of the structure. The system uses a one-dimensional trapezoidal representation for the supernode during the CMOD operation, if the result of the function is lower than a threshold value, and otherwise uses a two-dimensional rectangular representation for the supernode. The function of the structure of the supernode is a function of a number of computational operations involved in computing a lower-triangular sub-block portion of the supernode and a number of computational operations involved in computing a rectangular sub-block portion of the supernode.