A Minimum Degree Ordering Algorithm using the Lower and Upper Bounds of Degrees
Chan-Kyoo Park, Seungyong Doh, Soondal Park, Woo-Je Kim · Management Science and Financial Engineering · 2002
Ordering is used to reduce the amount of fill-ins in the Cholesky factor of a symmetric positive definite matrix. One of the most efficient ordering methods is the minimum degree ordering algorithm (MDO). In this paper, we provide a few techniques that improve the performance of MDO implemented with the clique storage scheme. First the absorption of nodes in the cliques is developed which reduces the number of cliques and the amount of storage space required for MDO. Second, we present a modified minimum degree ordering algorithm of which the number of degree updates can be reduced by introducing the lower bounds of degrees. Third using both the lower and upper bounds of degrees, we develop an approximate minimum degree ordering algorithm. Experimental results show that the proposed algorithm is competitive with the minimum degree ordering algorithm that uses quotient graphs from the points of the ordering time and the nonzeros in the Cholesky factor.