[enupten]

It is a multivariate (co-ordinate wise) version of MH. You can paralleize it because the Bayes net allows a decomposition of the p.d.

I feel like while your comment on Global-optimization algorithms may indeed be true, I don't quite yet believe that the hacks they involve are quite that general yet.

MH wasn't designed for Global optimization, and there is only one "particle". I guess this what you meant by "parallel" ?

[stellographer]

Yeah, that's what I meant, the one particle bit.

Frequently you'll see things along the lines of "we ran 10,000 MCMC iterations to find the solution" and my first thought is "that must be a lot of wasted cycles."

I think I see what you mean now about the parallelization by decomposing the variables (splitting the problem into i separate problems which can be chained independently?)-- I didn't know that was a possibility. I'll have to look at that.

[tel]

Well, you can run multiple simultaneous particle chains and sum their results. There's some wasted work since each will need to burn in, but modern algorithms can make that go quite quickly.

[enupten]

Sure - but that's not what the OP is referring to. There is no "sync" step in multiple parallel chains, unlike particle swarm & genetic algorithms.

MCMC is also used for finding MAP solutions, an operation which is strictly less difficult than computing the partition function.