Parallel computation [permutations]

François Perron is visiting me for two months from Montréal and, following a discussion about the parallel implementation of MCMC algorithms—to which he also contributed with Yves Atchadé in 2005—, he remarked that a deterministic choice of permutations with the maximal contrast should do better than random or even half-random permutations. Assuming p processors or threads, with p+1 a prime number, his solution is to take element (i,j) of the permutation table as (ij) mod (n+1): here are a few examples


> ((1:10)%*%t(1:10))%%11
 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]    1    2    3    4    5    6    7    8    9    10
 [2,]    2    4    6    8   10    1    3    5    7     9
 [3,]    3    6    9    1    4    7   10    2    5     8
 [4,]    4    8    1    5    9    2    6   10    3     7
 [5,]    5   10    4    9    3    8    2    7    1     6
 [6,]    6    1    7    2    8    3    9    4   10     5
 [7,]    7    3   10    6    2    9    5    1    8     4
 [8,]    8    5    2   10    7    4    1    9    6     3
 [9,]    9    7    5    3    1   10    8    6    4     2
[10,]   10    9    8    7    6    5    4    3    2     1

> ((1:16)%*%t(1:16))%%17
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
 [1,]    1    2    3    4    5    6    7    8    9    10    11
 [2,]    2    4    6    8   10   12   14   16    1     3     5
 [3,]    3    6    9   12   15    1    4    7   10    13    16
 [4,]    4    8   12   16    3    7   11   15    2     6    10
 [5,]    5   10   15    3    8   13    1    6   11    16     4
 [6,]    6   12    1    7   13    2    8   14    3     9    15
 [7,]    7   14    4   11    1    8   15    5   12     2     9
 [8,]    8   16    7   15    6   14    5   13    4    12     3
 [9,]    9    1   10    2   11    3   12    4   13     5    14
[10,]   10    3   13    6   16    9    2   12    5    15     8
[11,]   11    5   16   10    4   15    9    3   14     8     2
[12,]   12    7    2   14    9    4   16   11    6     1    13
[13,]   13    9    5    1   14   10    6    2   15    11     7
[14,]   14   11    8    5    2   16   13   10    7     4     1
[15,]   15   13   11    9    7    5    3    1   16    14    12
[16,]   16   15   14   13   12   11   10    9    8     7     6

which show that the scheme provides an interestingly diverse repartition of the indices. We certainly have to try this in the revision.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.