5
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ I would say that trying to keep the information that you need in each step local is a good idea if you want a fast algorithm. $\endgroup$ – adrianN Nov 28 '13 at 8:50
  • $\begingroup$ @adrianN are you talking about local variables? I think I'm talking about a higher-level description than that though. $\endgroup$ – Herng Yi Nov 28 '13 at 9:50
  • $\begingroup$ There is a similar thing in distributed computing. But it is not similar to divide and conquer. In distributed setting each process/node sees only its surrounding and decisions are based on local data. This survey might give you some ideas. cs.helsinki.fi/u/josuomel/doc/local-survey.pdf $\endgroup$ – Parham Nov 28 '13 at 10:31
  • $\begingroup$ @HerngYi no, I mean that in each step of the algorithm you only look at O(1) nodes and their neigborhoods instead of computing a flow between each pair of nodes. $\endgroup$ – adrianN Nov 28 '13 at 12:46
  • $\begingroup$ HerngYi, I think it might help us understand what you were asking if you could give us a few simple examples of algorithms that you consider to have been written or improved in this way, and explain why/how they fit your framework. $\endgroup$ – D.W.♦ Dec 8 '13 at 19:54
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ This answer is a little closer, but after the decomposition into local steps I do not want to run them sequentially, not in parallel. $\endgroup$ – Herng Yi Dec 14 '13 at 7:18
  • $\begingroup$ the theory on paralellism also relates/applies to running the decomposable pieces sequentially... $\endgroup$ – vzn Dec 14 '13 at 16:55
-2
$\begingroup$

The transformation that you are talking about is the very definition of Algorithm.

An algorithm is an effective method expressed as a finite list of well-defined instructions(Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987).) for calculating a function.

I don't think that there is a place for local or global definitions, but steps. Once you been able to create a well defined steps of your algorithm, not only that it will be easier to understand/implement it but also to improve it, by looking at each step individually.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ I am focusing on the data that the algorithm is manipulating, with a series of "local perturbations", where "local" refers to the geometry and/or topology of the data. $\endgroup$ – Herng Yi Dec 8 '13 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.