On the Minimum FLOPs Problem in the Sparse Cholesky Factorization
Robert Luce, Esmond G. Ng · SIAM Journal on Matrix Analysis and Applications · 2014
Prior to computing the Cholesky factorization of a sparse symmetric positive definite matrix, a reordering of the rows and columns is computed so as to reduce both the number of fill elements in Cholesky factor and the number of arithmetic operations (FLOPs) in the numerical factorization. These two metrics are clearly somehow related and yet it is suspected that these two problems are different. However, no rigorous theoretical treatment of the relation of these two problems seems to have been given yet. In this paper we show by means of an explicit, scalable construction that the two problems are different in a very strict sense: no ordering is optimal for both fill and FLOPs in the constructed graph. Further, it is commonly believed that minimizing the number of FLOPs is no easier than minimizing the fill (in the complexity sense), but so far no proof appears to be known. We give a reduction chain that shows the NP hardness of minimizing the number of arithmetic operations in the Cholesky factorization.