Decomposing an Algorithm into Local Transformations/Perturbations Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/perturbation in a confined neighborhood of the data while fixing the rest?

One benefit of this "breakdown" is improved conceptual understanding, and it also facilitates induction proofs (possibly based on invariants that are preserved by each step). Does this "decomposition" have a name in algorithm design? The idea might be similar to Divide and Conquer.

One might say that every individual step in an algorithm, like deleting an edge or labeling a vertex of a graph, is small enough to be considered "local", but I'm talking more about the "decomposition" in a higher-level description, like how truncating a polyhedron is local but sorting a list is not (even though at the lowest level, comparisons, insertions and deletions are local).

Examples of decomposing into local transformations


Augustin Cauchy's proof of his Rigidity Theorem relied on his "Arm Lemma" that opened up a convex planar chain by sequentially opening at each vertex. Although his proof was found to be wrong, he decomposed the opening algorithm into a series of "local opening moves", and he tried to prove that each local move preserved convexity of the chain. By induction, convexity would still hold after iterating over all vertices.
The pivot algorithm for self-avoiding walks (SAW) transforms a SAW into another by rotating or reflecting part of the original SAW. Markov Chain Monte Carlo can employ this transformation as a transition between SAW states to sample the space of SAWs.
As an application of the above, one technique of protein folding prediction is to force an amino acid chain into several known protein structures, choose the one with the lowest energy (due to intermolecular forces), then let the chosen structure "relax" into a configuation with lower energy. Relaxation involves the prescription of a few "local moves", where small parts of the chain can "wriggle around" (e.g. subchains pivoting around their ends), and random wriggles are allowed for a period of time to let the chain "stabilize". Modelling the chain as an SAW allows pivots to be used as a "wriggle".
there are several ways to measure this "local vs global" decomposition dichotomy of problems which does show up in a wide variety of CS contexts.


how many local minima there are versus a global minimum for optimization problems. if there are many local minima it is harder to find the global minimum. roughly this is also a measure of how effective greedy algorithms are on that problem.
algorithmic speedup due to parallelism. this metric is sensitive to both the problem and the algorithm chosen. for example the problem may not be very "decomposable", or a problem may be decomposable but it is not solved with a most efficient algorithm. for more decomposable problems, algorithmic speedup is nearly linear in increasing processors. for less decomposable problems, it is more an asymptotic sub-linear relationship.
communication overhead of parallel processing. the decomposability is known as "granularity". for problems that are not as granular, there is more communication required between separate parallel threads or processors. problems with very "fine" granularity ie not requiring much or any communication between processors are called embarrassingly parallel.
NC is the class of efficiently parallelizable algorithms. NC=?P is an open question. ie in short are all P-time algorithm efficiently parallelizable, or not?


one paper that does attempt to study these concepts more formally/systematically within the context of parallel computing is Landscape of parallel computing, the view from Berkeley. see eg "7+ dwarves" for the basic algorithmic patterns that seem to appear in practice and commentary on their decomposability wrt parallelism.

another influential researcher recently looking into the inherent limits/ceilings/gains of parallelism in CPU design (ie multicore) which relates to the general decomposability of everyday running code is Esmaeilzadeh.