Can you compete with a supercomputer?
The challenge is to write super fast code for computing the permanent of a matrix of complex numbers.
In a paper from 2016 a team of coders managed to compute the permanent of a 40 by 40 complex matrix on 8192 nodes of what was at the time the world's fastest computer in about 14 seconds. Your challenge is to see how close you can get to this on my desktop.
The permanent of an n
-by-n
matrix A
= (a
i,j
) is defined as

Here S_n
represents the set of all permutations of [1, n]
.
As an example (from the wiki):

In this question matrices are all square.
Examples (these need updating to have complex entries)
Input:
[[ 1 -1 -1 1]
[-1 -1 -1 1]
[-1 1 -1 1]
[ 1 -1 -1 1]]
Permanent:
-4
Input:
[[-1 -1 -1 -1]
[-1 1 -1 -1]
[ 1 -1 -1 -1]
[ 1 -1 1 -1]]
Permanent:
0
Input:
[[ 1 -1 1 -1 -1 -1 -1 -1]
[-1 -1 1 1 -1 1 1 -1]
[ 1 -1 -1 -1 -1 1 1 1]
[-1 -1 -1 1 -1 1 1 1]
[ 1 -1 -1 1 1 1 1 -1]
[-1 1 -1 1 -1 1 1 -1]
[ 1 -1 1 -1 1 -1 1 -1]
[-1 -1 1 -1 1 1 1 1]]
Permanent:
192
Input:
[[1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1],
[1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1],
[-1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, -1],
[-1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1],
[-1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1],
[1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1],
[1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1],
[1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1],
[-1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1],
[-1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1],
[1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1],
[-1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, 1],
[1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
[1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1],
[-1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1],
[1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1],
[1, 1, 1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1],
[-1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1]]
Permanent:
1021509632
Add the 40 by 40 matrix here
The task
You should write code that, given an n
by n
complex matrix, outputs its permanent.
To make testing simpler, I will provide a single 40
by 40
complex matrix which you can hardcode into your code in any format of your choosing. Clearly, you are not allowed to precompute the answer however!
Scores and ties
I will test your code on the sample 40
by 40
complex matrix. Your score is your time in seconds divided by 14.
If two people are within 1 second of each other then the winner is the one posted first.
Languages and libraries
You can use any available language and libraries you like but no pre-existing function to compute the permanent. I will run your code under OS X so please give full instructions for how to compile and run it.
Reference implementations
There is already a codegolf question question with lots of code in different languages for computing the permanent for small matrices. There was also a related challenge on computing the permanent of matrices with only +-1 entries. The coding issues when you have complex entries and want things to run fast and multi-core are quite different however.
My Machine
The timings will be run on my Mac desktop. The CPU is Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
.
[tag:code-golf]
\$\endgroup\$ – DJMcMayhem♦ Aug 29 at 15:19