TR-2008004: Additive Preconditioning for Matrix Computations

Versus the customary preconditioners, our weakly random ones are generated more readily and for a much larger class of input matrices. Furthermore our preconditioners have a wider range of applications, in particular to linear systems with rectangular and rank deficient coefficient matrices and to eigen-solving. We study the generation of such preconditioners and their impact on conditioning of the input matrix. Our analysis and experiments show the power of this approach even where we use weak randomization, with fewer random parameters, and choose sparse and structured preconditioners. 2000 Math. Subject Classification: 65F22, 65F35, 65A12