Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose a 4-connected regular grid


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 ...

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.