Tricki

## Revision of Divide and conquer from Fri, 24/04/2009 - 16: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.

### 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 for some fixed non-zero and some exponents . The integrand here exhibits three distinct modes of "bad" behavior: a singularity as , a singularity as , and a slow decay as . Rather than deal with all these modes at once, one can decompose the domain 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 into

• I. The region where ;

• II. The region where ;

• III. The region where .

In region I, the dominant mode of behavior is the singularity as . The term is comparable in magnitude here to the quantity , which is independent of 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 .

In region II, the dominant mode of behavior is the singularity as . The term is comparable in magnitude here to the quantity , and can be pulled out of the integral also, leaving one with the tractable integral .

In region III, the dominant mode of behavior is the decay as . Here, and are comparable in magnitude to each other, so the integral can be simplified (up to multiplicative constants) as . The additional restriction is not significantly helping us here (this is intuitively obvious after drawing a picture), and we can estimate this contribution by the tractable integral .

(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?)