An efficient minimum degree ordering method using the lower bounds of degrees

Ordering is used to reduce the amount of fill-ins in the Cholesky factor of an symmetric definite matrix. One of most efficient ordering methods is the minimum degree ordering method. In this paper, we propose the two techniques to improve the performance of the minimum degree ordering which are implemented using clique storage structure. One is node absorption which is a generalized version of clique absorption. The other technique is using the lower bounds of degree to suspend the degree updates of nodes. Finally, we provide computational results on the problems on NETLIB. These results show that the proposed techniques reduce the number of degree updates and the computational time considerably.