Performance of distributed sparse Cholesky factorization with pre-scheduling

Abstract

We propose a sparse Cholesky factorization scheme based on a static task and communication schedule generated by symbolic preprocessing of the intercolumn dependencies. This information is used to reduce the overheads of maintaining data structures and the communication costs incurred in message passing during the numerical factorization step. We introduce three primitives which encapsulate these optimizations and alleviate the user's programming effort. Performance results obtained on the iPSC/860 show that an implementation using these primitives results in 30% to 40% savings over one that does not use any static communication structure information.