Massive parallelization of simulated annealing.

Summary We will start with the generalization to potential-free annealing of some results of large deviations of olivier catoni and we will establish the expression of the optimal exponent for triangular sequences of temperature patterns depending on the horizon. We give an algorithm for computing the critical constants through an effective decomposition according to the wentzell and freidlin cycles. We then consider massively parallel forms of simulated annealing for spaces of configurations defined by a family of labels indexed by a finite set of sites. After giving a general framework of massively parallel annealing, we develop fixed rate parallelization where at each iteration a site can be frozen with a fixed probability. We will focus on the role of the parallelization rate and the neighborhood structure in the low temperature behavior of the algorithm and in the efficiency of the parallelization. We will also show the singularity of the totally parallel algorithm. Finally, we will study a form of parallelization of simulated annealing where we dynamically control the simultaneous renewals of neighboring sites. We will show for this last algorithm the convergence to global minima and we will conduct a numerical comparison with the parallel annealing by classical coding.