The average parallel complexity of cholesky factorization

AbstractWe analyze the average parallel complexity of the solution of large sparse positive definite linear systems. More precisely, using probabilistic techniques, we study the Cholesky factorization with the application of the minimum degree algorithm. Main results are the estimation of the evolution of sparsity during the factorization and a characterization of the elimination tree in terms of depth and number of leaves. We also conjecture that the number of parallel steps needed to perform the factorization is linear with respect to the matrix size