Graph embedding techniques for bounding condition numbers of incomplete factor preconditioners

We extend graph embedding techniques for bounding the spectral condition number of preconditioned systems involving symmetric, irreducibly diagonally dominant M-matrices to systems where the precondi-tioner is not diagonally dominant. In particular, this allows us to bound the spectral condition number when the preconditioner is based on an incomplete factorization. We provide a review of previous techniques, describe our extension, and give examples both of a bound for a model problem, and of ways in which our techniques give intuitive way of looking at incomplete factor preconditioners. Key words. incomplete Cholesky factorization, graph eigenvalues and eigenvectors, preconditioning Subject classification. Computer Scienc