The solution of large sparse positive definite linear systems of equations is a problem frequently encountered in many applications in scientific computing. The dimension of typical problems has grown substantially over the recent years and there is no reason to believe that we have reached the end of this growth. Therefore, there is a substantial demand for fast and reliable algorithms to solve such equations. Many modern algorithms in this context are based on Cholesky decompositions. This paper describes CHOLMOD, a package of subroutines built for handling such decompositions, the required preprocessing and postprocessing, and related issues.
CHOLMOD contains 134 user-callable routines that cover all potential problems that one can encounter in such a context. Moreover, the routines give the user a great deal of opportunity to choose the specific version of the algorithm that best suits the concrete application at hand. A particularly important question in this respect is the ordering strategy for the algorithm. A poor choice here may lead to a highly inefficient and slow procedure. Therefore, a very useful feature that CHOLMOD offers is not only various possible ordering methods--including (approximate) minimum degree ordering, nested dissection, and METIS--but also some tools for the user that allow him or her to find a good method.
The description of the package is very detailed and complete. The numerical examples provided indicate that it performs very well. It should be a very useful tool for anyone who needs to deal with large sparse positive definite systems--an observation confirmed by the fact that CHOLMOD has been integrated into MATLAB.