I have a standard set of linear equations $Ax=b$ where the Hessian matrix $A$ has the special block structure as shown:$A=\begin{pmatrix}T & U\\ U^T & V\end{pmatrix}$,$x=\begin{pmatrix}c\\ d\end{pmatrix}$Where $A$ is square Hessian matrix and each dimension is of size $n = c_n + d_n$. This compound dimension is quite large, typically $10^6-10^{10}$. The gradient vector $b$ has the same block structure as $x$. This set of equations is solved for a full Newton step to an iterative procedure.One can think of the matrices $T$ and $V$ as two different basis expansions of a given problem with the coupling between these two bases represented by $U$. This set of linear equations is usually solved through CG or an associated method as the matrix $A$ is too large to store.What is interesting about this is that the coupling block $U$ is quite small. Often, the $c$ and $d$ blocks are solved alternatively without consideration of $U$; however, this can lead to somewhat slow convergence. It would appear that this can be solved in a somewhat decoupled manner where were $Ax$ Hessian-vector guesses can be split as follows:$Ax_1 = T*c + U*d$$Ax_2 = U^T*c + V*d$For example, $Ax_1$ could be updated on every third iteration of $Ax_2$. As the computation of $Ax_1$ is much more costly than $Ax_2$ this would be quite advantageous. I assume that this kind of system is well described somewhere, but have been unable to google the correct combination of words. Does anyone know what this kind of system of equations is called?Also, if anyone has a good recommendation for material on approximate Newton methods for ill-conditioned systems that would be quite helpful as well.Full disclosure: I asked the same question here with a 100 point bounty without luck. I decided to try again here as this community has more experience with practical solutions.
Solving a set of linear equations with block structure and weak coupling
optimization;linear solver;nonlinear equations;newton method;conjugate gradient