José Mas
Inverse Sherman-Morrison factorization and the NBIF preconditioner

Cami de Vera 14
Edifici 3I
Universitat Politecnica de Valencia
Valencia
46022 SPAIN
jmasm@mat.upv.es
Rafael Bru
José Marin
Miroslav Tuma

The Inverse Sherman-Morrison factorization of an invertible matrix $A$, for a positive parameter $s$, is given by

$$s^{-1}I - {A}^{-1} = s^{-2} Z_s D_s^{-1} V_s^T$$

where

$$z_k=e_k-\sum_{i=1}^{k-1}\frac{v_i^T e_k}{s r_i} z_i \ v_k=y_k-\sum_{i=1}^{k-1}\frac{y^T_k z_i}{sr_i}v_i, \ \ r_k=1+y^T_kz_k/s=1+v^T_k e_k/s$$

for $k=1,2,\ldots,n$, where $e_k$ and $y_k$ are the columns of the identity matrix $I$ and $Y=A^T-sI$, respectively.

It is known that from this factorization some factors of the LDU factorization can be recovered, at the same time the inverse factors of the LDU factorization are already computed, as can be deduced from the following relations

$${D}=s^{-1}D_s, \quad {U}= Z^{-1}, \quad V_s = {U}^T {D} - s {L}^{-T},$$

Since the ISM factorization is highly parametrizable we analyze also some relations of the factors for different choices of the parameter $s$, and relations with scaling of $A$.

We also present an algorithm (NBIF) to compute a preconditioner using the ISM factorization and the dropping strategies of Bollhöfer, taking advantage of more deep relations between both factorizations. We also prove existence properties of these preconditioners and present some numerical results.

This work was supported by Spanish grant MTM 2007-64477, also by the project No. IAA100300802 of the Grant Agency of the Academy of Sciences of the Czech Republic and partially by the international collaboration support M100300902 of AS CR.