| 摘要 |
One embodiment of the present invention provides a system for efficiently perform a modification (cmod) operation in solving a system of linear algebraic equations involving a sparse coefficient matrix. The system operates by identifying supernodes in the sparse matrix, wherein each supernode comprises a set of contiguous columns having a substantially similar pattern of non-zero elements. In solving the equation, the system performs a cmod operation between a source supernode and a destination supernode. As part of this cmod operation, the system determines a subset of the source supernode that will be used in creating an update for the destination supernode. The system partitions the subset 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. The system computes a corresponding portion of the update for the destination supernode using a cmod function for each tile in the plurality of tiles. This computation may involve using computer code that is specifically tailored to each tile's dimensions. In one embodiment of the present invention, the system pre-computes a computational performance for a plurality of different tile sizes.
|
