  As it has become common to use many computer cores in routine applications,
finding good ways to parallelize popular algorithms has become increasingly
important. In this paper, we present a parallelization scheme for Markov chain
Monte Carlo (MCMC) methods based on spectral clustering of the underlying state
space, generalizing earlier work on parallelization of MCMC methods by state
space partitioning. We show empirically that this approach speeds up MCMC
sampling for multimodal distributions and that it can be usefully applied in
greater generality than several related algorithms. Our algorithm converges
under reasonable conditions to an `optimal' MCMC algorithm. We also show that
our approach can be asymptotically far more efficient than naive
parallelization, even in situations such as completely flat target
distributions where no unique optimal algorithm exists. Finally, we combine
theoretical and empirical bounds to provide practical guidance on the choice of
tuning parameters.
