Multiplicative correction of a matrix on a sequence of subspaces. I: Basic algorithms and theory for general unsymmetric matrices

The paper considers the problem of a guaranteed improvement of matrix properties by preconditioning. An algorithm for constructing the so-called basic correctors, differing from the identity matrix by a small-rank term, is suggested. A basic corrector improves the matrix action on a subspace of small dimension and provides a possibility of controlling its action on the complementary subspace. In the algorithm suggested, basic correctors are computed by using the operation of multiplying the original matrix by a vector. The resulting preconditioner is a composition of basic correctors. Its nonsingularity is guaranteed in the general unsymmetric and indefinite case, and estimates enabling one to predict the convergence properties of the corresponding iterative algorithm are obtained. In order to reduce the arithmetic and memory costs, it is suggested to replace basic correctors by their approximations. Estimates for the resulting deterioration of the preconditioning quality are presented.