# Divide and conquer possible on linear equation systems?

Suppose a 4-connected regular grid

$$\mathcal{G}=(\mathcal{E},\mathcal{V}),$$

where $\mathcal{E}$ and $\mathcal{V}$ denote the set of edges and vertices of that grid, respectively.

Given this graph $\mathcal{G}$, we determine a new set of vertices $\mathcal{V}'$, such that it minimizes a quadratic error function $E_{\mathcal{G}}(\mathcal{V})$ defined on $\mathcal{G}$, i.e. we solve the optimization problem

$$\underset{\mathcal{V}'}{\text{argmin}}~~ E_{\mathcal{G}}$$

by constructing and solving a linear equation system $\mathbf{A}\mathbf{x}=\mathbf{b}$ with $N$ unknowns, using a direct or iterative solver. The number of vertices in $\mathcal{V}$ determines the number unknowns $N=|\mathcal{V}|$.

My question:

I wonder if it is possible, to break this large system of linear equations $\mathbf{A}\mathbf{x}=\mathbf{b}$ into several smaller ones, which can then be solved independently and iteratively?

That is, I have a large regular grid $\mathcal{G}$ and would split it into several smaller ones (a grid of grid, if you will) while letting these smaller grids overlap their neighbours a bit (how much?). For each of these smaller grids I solve an optimization problem just like the one described above. However, each of them would have to solved multiple times based on the solution of the previous iteration. Eventually, because of the overlap between them, should this not converge to a similar solution (or even the same one) as if I solved the "global" optimization problem described above?

Why do I ask? Because I was wondering, if it is a good idea to have GPU solver solve a large number of small systems of linear equations rather than a (CPU) solver working on one very large optimization problem.

Even if you don't know the answer, but recognize this class of problem, I would already appreciate any kind of new keywords that might help me to improve my google queries ...

-
You've seen this? – J. M. Oct 5 '12 at 13:18
Yes, I have. However, in contrast to the local and independent equation systems, the blocks in the Block LU decomposition are not overlapping. So, it's not entirely the same thing. – nils Oct 11 '12 at 14:03