Tricki
a repository of mathematical know-how

Revision of Divide and conquer from Fri, 24/04/2009 - 15:37

Quick description

When an mathematical object that exhibits many distinct features, each of which makes it more difficult to control that object effectively, try decomposing the object into better-behaved (and non-interacting) components, each of which only has one of the features dominating. Then control each of the components separately, and "sum up" to control the original object.

Note that in many cases, the components may be "messier" than the original object (because of the presence of cutoffs, mollifiers, truncations, etc.). Nevertheless, these messier components may be easier to control, especially if one is only seeking upper bounds or approximations rather than exact computations, particularly if one is prepared to lose multiplicative constants in the final bound.

Prerequisites

Undergraduate calculus

Example 1

The divide-and-conquer strategy is particularly good for estimating "linear" expressions, such as an integral over a domain. One can divide up the domain into several components where the integrand is exhibiting different behavior, and bound the contribution of each component separately.

For instance, suppose one wants to compute the convolution integral \int_{\R^n} \frac{1}{|y|^\alpha |x-y|^\beta}\ dy for some fixed non-zero x \in \R^n and some exponents \alpha, \beta > 0. The integrand here exhibits three distinct modes of "bad" behavior: a singularity as y \to 0, a singularity as y \to x, and a slow decay as y \to \infty. Rather than deal with all these modes at once, one can decompose the domain \R^n into three regions where one only sees one of these modes at a time. There are a number of ways to do this, but here is one way: decompose \R^n into

  • I. The region where |y| < |x|/2;

  • II. The region where |y-x| < |x|/2;

  • III. The region where |y|, |y-x| \geq |x|/2.

In region I, the dominant mode of behavior is the singularity as y \to 0. The \frac{1}{|x-y|^{\beta}} term is comparable in magnitude here to the quantity \frac{1}{|x|^\beta}, which is independent of y and can thus be pulled out of the integral (here we are using the trick "bound the integrand by something simpler"), leaving us with the (tractable) task of computing the integral \int_{|y| < |x|/2} \frac{1}{|y|^\beta}\ dy.

In region II, the dominant mode of behavior is the singularity as y \to x. The \frac{1}{|y|^\alpha} term is comparable in magnitude here to the quantity \frac{1}{|x|^\alpha}, and can be pulled out of the integral also, leaving one with the tractable integral \int_{|y-x| < |x|/2} \frac{1}{|x-y|^\alpha}\ dy.

In region III, the dominant mode of behavior is the decay as y \to \infty. Here, |y| and |x-y| are comparable in magnitude to each other, so the integral can be simplified (up to multiplicative constants) as \int_{|y|, |y-x| \geq |x|/2} \frac{1}{|y|^{\alpha + \beta}}\ dy. The additional restriction |y-x| \geq |x|/2 is not significantly helping us here (this is intuitively obvious after drawing a picture), and we can estimate this contribution by the tractable integral \int_{|y| \geq |x|/2} \frac{1}{|y|^{\alpha + \beta}}\ dy.

(Should this example be worked out more fully?)

General discussion

A particularly useful special case of the divide-and-conquer strategy is dyadic decomposition.

(Need some non-integration examples of divide-and-conquer strategies, e.g. in combinatorics. Suggestions?)

Comments

which parent for this child?

Divide and Conquer is currently a child of Estimating Integrals. However it seems that it should be a general principle that applies to many different situations. Thus it could be for example a child of Techniques for obtaining estimates which it is in a sense (it's a grandchild). However, if someone goes to the techniques for obtaining estimates and their problem has nothing to do with integrals, he/she might never end up seeing this article as its way is via Estimating Integrals. I understand that this is potentially a general problem for many different articles. They belong to many different places. Is it possible to have a more parallel structure here? That is, instead of a folder structure have a label structure (a bit like how gmail uses labels instead of folders so different things can of course belong to the same label). Of course this might already be the case without me knowing it. But in this case I guess the article divide and conquer that I'm using as an example should be linked from Techniques for obtaining estimates as well. I have another question. If I edit the article and add an extra 'parent', can a link automatically be created in the parent article? Otherwise how can one track the child from this new parent?

Parent/child links

There was an inconclusive forum discussion about this issue (under the topic of "Linking to front pages"). If I understand the current situation correctly, at the moment if you add a parent to an article, you have to manually edit that parent article and add the link.