An Optimal Ordering Algorithm for Sparse Matrix Applications

This paper presents a new, optimal (according to a criterion defined later), sparsity-oriented, ordering algorithm for application in sparse matrix calculations. A dynamic programming algorithm which determines an ordered elimination such that the total number of fill-in terms is minimum is developed. The ordering algorithm is shown to be better, i.e. less fill-in, than the clustering method of reference [4]. The algorithm, is valid for diagonally dominant matrices which are symmetric in pattern of nonzero elements. The method has been found practical for ordering matrices appearing in a wide variety of engineering applications. Presently, it can be efficiently applied to matrices of the order of 50 rows.