Optimal preconditioners of a given sparsity pattern (Q581999)

The authors consider the problem of finding ``optimal'' symmetric positive definite preconditioning matrices N of a given form - e.g. having nonzero elements only in specified positions - for a symmetric positive definite matrix A. Optimality is defined in terms of the condition number \(\kappa_ 2(M^{-1}A):=\lambda_{\max}(M^{- 1}A)/\lambda_{\min}(M^{-1}A)\), because this number enters into an upper bound for the iteration error, which is sharp for the Chebyshev method and a good estimate for the conjugate gradients method as well. Firstly theoretical results are given. Then it is shown how the problem can be expressed as one of minimizing a convex function and how an optimization code can be used to solve the problem numerically. Results are presented showing optimal preconditioners of varius sparsity patterns. One will not normally use an optimization code as a practical method for finding a good preconditioner for a given problem, but the results are interesting for becoming insight into the properties of preconditioners and had led to some conjectures.