RECURSIVE ALGORITHM AND IMPROVEMENT FOR CHOLESKY FACTORIZATION

Recursion is a new effective method for computing dense linear algebra. It allows for efficient utilization of memory hierarchies of today’s high performance computers. The recursive algorithm for Cholesky factorization is studied in this paper. A detailed derivation of the recursive Cholesky algorithm is given. The algorithm is then implemented in Fortran 90 that supports recursion as a language feature. The efficiency of the recursive algorithm is further improved by using a method of matrix element reordering. The resulting algorithms are 15%~25% faster than the currently used block algorithm.