On Vectorizing Incomplete Factorization and SSOR Preconditioners

Abstract

We consider the problem of vectorizing the recursive calculations found in modified incomplete factorizations and SSOR preconditioners for the conjugate gradient method. We examine matrix problems derived from partial differential equations which are discretized on regular 2-D and 3-D grids, where the grid nodes are ordered in the natural ordering. By performing data dependency analyses of the computations, we show that there is concurrency in both the factorization and the forward and backsolves. The computations may be performed with an average vector length of $O(n)$ on an $n^2 $ or $n^3 $ grid in two and three dimensions. Numerical studies on four model problems show that the conjugate gradient method using these vectorized implementations of the modified incomplete factorizations and SSOR preconditioners achieves overall speeds approaching 100 megaflops on a Cray X-MP/24 vector computer. Furthermore, these methods require considerably less overall execution time than diagonal scaling and no-fill red-black incomplete factorization preconditioners, both of which allow full vectorization but are not as convergent.