Marko Huhtanen
APPROXIMATE FACTORS FOR THE INVERSE

Institute of Mathematics
Helsinki University of Technology
Box 1100
FIN-02015
Finland
marko.huhtanen@tkk.fi

Let $\mathcal{W}$ and $\mathcal{V}_1$ be sparse matrix subspaces of $\mathbb{C}^{n \times n}$ containing invertible elements such that those of $\mathcal{V}_1$ are readily invertible. To precondition a large linear system involving a sparse nonsingular matrix $A\in \mathbb{C}^{n \times n}$, in this talk we consider

$$AW\approx V_1$$ (1)

with non-zero matrices $W \in \mathcal{W}$ and $V_1 \in \mathcal{V}_1$ both regarded as variables. The attainability of the possible equality can be verified by inspecting the nullspace of

$$W\longmapsto (I-P_1)AW,\, \, W\in \mathcal{W},$$ (2)

where $P_1$ is the orthogonal projection onto $\mathcal{V}_1$ [1].

Corresponding to the smallest singular values of (), we have $(I-P_1)AW \approx 0$ if and only if $AW\approx V_1=P_1AW$. This gives rise to the criterion

$$\min_{W\in \mathcal{W}, \left\vert\left\vert W\right\vert\right\vert _F=1} \left\vert\left\vert(I-P_1) AW\right\vert\right\vert _F$$

for a starting point to generate approximate factors $W$ and $V_1=P_1AW$. Then

$$\frac{\left\vert \left\vert AWV_1^{-1} -I\right\vert\right\vert }... ...{-1} -I\right\vert\right\vert \left\vert \left\vert V_1 \right\vert\right\vert$$

in the 2-norm, whenever $V_1$ is invertible. Consequently, the maximum gap between these two approximation problems is determined the condition number of $V_1$. In the special case $\mathcal{V}_1=\mathbb{C}I$ the equalities hold in general. This corresponds to the criterion

$$\min_{W\in \mathcal{W}}\left\vert\left\vert AW-I\right\vert\right\vert _F$$

which constitutes a starting point for constructing sparse approximate inverses.