BLOCK SPARSE CHOLESKY ALGORITHMS ON ADVANCED UNIPROCESSOR COMPUTERS

As with many other linear algebra algorithms, devising a portable impl ementation of sparse Cholesky factorization that performs well on the broad range of computer architectures currently available is a formida ble challenge. Even after limiting the attention to machines with only one processor, as has been done in this paper, there are still severa l interesting issues to consider. For dense matrices, it is well known that block factorization algorithms are the best means of achieving t his goal. This approach is taken for sparse factorization as well. Thi s paper has two primary goals. First, two sparse Cholesky factorizatio n algorithms, the multifrontal method and a blocked left-looking spars e Cholesky method, are examined in a systematic and consistent fashion , both to illustrate the strengths of the blocking techniques in gener al and to obtain a fair evaluation of the two approaches. Second, the impact of various implementation techniques on time and storage effici ency is assessed, paying particularly close attention to the work-stor age requirement of the two methods and their variants.