\documentclass[a4paper,10pt]{article}
\usepackage{amsmath}
\usepackage{a4wide}
\parindent=0in
\def\bx#1{{\bf #1}}
\pagestyle{empty}
\begin{document}
\begin{center}
{\bf {\Large
An iterative solution method for Schur complement systems with inexact inner
solver}}
\vspace{0.2in}
{\small
Owe Axelsson and Maya Neytcheva\\
Department of Mathematics, University of Nijmegen,\\
Toernooiveld, 6525 ED Nijmegen, The Netherlands\\
e-mail: {\tt axelsson@sci.kun.nl}, {\tt neytchev\@sci.kun.nl}
}
\end{center}
\bigskip
Consider the following problem setting: a system of equations have to be
solved ($A\bx{x}=\bx{b}$)
and the corresponding matrix $A$ is partitioned into a two-by-two block
form, thus, we have to solve
\begin{equation}
\begin{bmatrix} A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}
\begin{bmatrix} \bx{x}_1\\ \bx{x}_2 \end{bmatrix} =
\begin{bmatrix} \bx{b}_1\\ \bx{b}_2 \end{bmatrix}\cdot
\label{eq1}
\end{equation}
Such matrix partitioning naturally arises in the Hierarchical Basis Functions
method and when using Domain Decomposition techniques.
Assume that $A_{11}$ is nonsingular and consider the solution of (\ref{eq1})
via the Schur complement system $S_{2}\bx{x}_2 = \tilde{\bx{b}}_2$, or
\begin{equation}
(A_{22} - A_{21}A_{11}^{-1}A_{12})\bx{x}_2 = \bx{b}_2 -
A_{21}A_{11}^{-1}\bx{b}_1.
\label{eq2}
\end{equation}
The matrix $A$ and, in particular, the block $A_{11}$ are considered very large
and sparse. Clearly, it is not computationally viable to form the Schur
complement matrix $S_2$ explicitly. Furthermore, due to the sparsity of
$A_{11}$, it is most efficient to solve systems with $A_{11}$ by an
iterative method also. Hence, (\ref{eq2}) will be solved by an inner-outer
iterative solution method.
When using an inner-outer solution procedure, the following (standard)
reasonings have to be balanced. On one side,
as the expense to solve systems with $A_{11}$ is considerable and,
furthermore, it is embedded in an outer solver, we must regulate the
accuracy with which this solution is done and try not to solve with a high
accuracy.
On the other side, at some point in the algorithm we must compute an
accurate action of $A_{11}$, otherwise we will solve a perturbed system,
thus, another problem.
For this purpose, a defect-correction algorithm is proposed, based on
computing the defects $\bx{d}_1$ and $\bx{d}_2$,
\begin{equation}
\bx{d}_1^{(k)} = \bx{b}_1 - A_{11}\bx{x}_1^{(k)} - A_{12}\bx{x}_2^{(k)},
\qquad
\bx{d}_2^{(k)} = \bx{b}_2 - A_{21}\bx{x}_1^{(k)} - A_{22}\bx{x}_2^{(k)},
\notag
\end{equation}
and then computing corresponding corrections $\delta\bx{x}_1$ and
$\delta\bx{x}_2$ from
%
\begin{align}
A_{11}\delta\bx{x}_1 & = \bx{d}_1^{(k)}, \notag \\
S_2\delta\bx{x}_2 & = \bx{d}_2^{(k)}, \label{eq4}
\end{align}
%
where the correction equation (\ref{eq4}) is solved using inexact actions of
$S_2$, i.e., the inner systems are solved with a low accuracy.
The observation is that the defects have to be computed accurately while the
corrections can be solved less accurately.
%
In the context of a domain decomposition method, the degrees of freedom in
$\bx{x}_2$ correspond to
a coarse mesh points (mesh parameter $H$) and those in $\bx{x}_1$ correspond
to interior and edge points of a fine mesh (mesh parameter $h$). Then, the
accuracies one works are $O(h^2)$ for the defect and $O(H^2)$ for the
corrections.
The presentation includes further considerations of the computational
complexity of the method and numerical experiments, including an example of
an ordering strategy which offers extra advantages with respect to the
structure of the matrix block $A_{11}$.
The approach is directly applicable to nonlinear systems of equations.
\end{document}