C++ with pthreads
This gets to n=14 in just under 1 minute on my machine. But since that's just a 2-core laptop, I hope that the 8-core test machine can finish n=15 in under 2 minutes. It takes about 4:20 minutes on my machine.
I was really hoping to come up with something more efficient. There has got to be a way to calculate the determinate of a binary matrix more efficiently. I wanted to come up with some kind of dynamic programming approach that counts the +1 and -1 terms in the determinant calculation. But it just hasn't quite come together so far.
Since the bounty is about to expire, I implemented the standard brute force approach:
- Loop over all possible Toeplitz matrices.
- Skip one of the two in each transposed matrix pair. Since the matrix is described by bitmask values, this is simple to do by skipping all values where the reverse of the bitmask is smaller than the bitmask itself.
- The determinate is calculated with a text book LR decomposition. Except for some minor performance tuning, the main improvement I made to the algorithm from my college numerical methods book is that I use a simpler pivot strategy.
- Parallelization is done with pthreads. Just using regular spacing for the values processed by each thread caused very bad load balancing, so I introduced some swizzling.
I tested this on Mac OS, but I used similar code on Ubuntu before, so I hope this will compile and run without a hitch:
- Save the code in a file with a
.cpp extension, e.g. optim.cpp.
- Compile with
gcc -Ofast optim.cpp -lpthread -lstdc++.
- Run with
time ./a.out 14 8. The first argument is the maximum n. 14 should finish in under 2 minutes for sure, but it would be great if you could try 15 as well. The second argument is the number of threads. Using the same value as the number of cores of the machine is normally a good start, but trying some variations could potentially improve the times.
Let me know if you have any problems building or running the code.
#include <stdint.h>
#include <pthread.h>
#include <cstdlib>
#include <iostream>
static int NMax = 14;
static int ThreadCount = 4;
static pthread_mutex_t ThreadMutex;
static pthread_cond_t ThreadCond;
static int BarrierCount = 0;
static float* MaxDetA;
static uint32_t* MaxDescrA;
static inline float absVal(float val)
{
return val < 0.0f ? -val : val;
}
static uint32_t reverse(int n, uint32_t descr)
{
uint32_t descrRev = 0;
for (int iBit = 0; iBit < 2 * n - 1; ++iBit)
{
descrRev <<= 1;
descrRev |= descr & 1;
descr >>= 1;
}
return descrRev;
}
static void buildMat(int n, float mat[], uint32_t descr)
{
int iDiag;
for (iDiag = 1 - n; iDiag < 0; ++iDiag)
{
float val = static_cast<float>(descr & 1);
descr >>= 1;
for (int iRow = 0; iRow < n + iDiag; ++iRow)
{
mat[iRow * (n + 1) - iDiag] = val;
}
}
for ( ; iDiag < n; ++iDiag)
{
float val = static_cast<float>(descr & 1);
descr >>= 1;
for (int iCol = 0; iCol < n - iDiag; ++iCol)
{
mat[iCol * (n + 1) + iDiag * n] = val;
}
}
}
static float determinant(int n, float mat[])
{
float det = 1.0f;
for (int k = 0; k < n - 1; ++k)
{
float maxVal = 0.0f;
int pk = 0;
for (int i = k; i < n; ++i)
{
float q = absVal(mat[i * n + k]);
if (q > maxVal)
{
maxVal = q;
pk = i;
}
}
if (pk != k)
{
det = -det;
for (int j = 0; j < n; ++j)
{
float t = mat[k * n + j];
mat[k * n + j] = mat[pk * n + j];
mat[pk * n + j] = t;
}
}
float s = mat[k * n + k];
det *= s;
s = 1.0f / s;
for (int i = k + 1; i < n; ++i)
{
mat[i * n + k] *= s;
for (int j = k + 1; j < n; ++j)
{
mat[i * n + j] -= mat[i * n + k] * mat[k * n + j];
}
}
}
det *= mat[n * n - 1];
return det;
}
static void threadBarrier()
{
pthread_mutex_lock(&ThreadMutex);
++BarrierCount;
if (BarrierCount <= ThreadCount)
{
pthread_cond_wait(&ThreadCond, &ThreadMutex);
}
else
{
pthread_cond_broadcast(&ThreadCond);
BarrierCount = 0;
}
pthread_mutex_unlock(&ThreadMutex);
}
static void* threadFunc(void* pData)
{
int* pThreadIdx = static_cast<int*>(pData);
int threadIdx = *pThreadIdx;
float* mat = new float[NMax * NMax];
for (int n = 1; n <= NMax; ++n)
{
uint32_t descrRange(1u << (2 * n - 1));
float maxDet = 0.0f;
uint32_t maxDescr = 0;
uint32_t descrInc = threadIdx;
for (uint32_t descrBase = 0;
descrBase + descrInc < descrRange;
descrBase += ThreadCount)
{
uint32_t descr = descrBase + descrInc;
descrInc = (descrInc + 1) % ThreadCount;
if (reverse(n, descr) > descr)
{
continue;
}
buildMat(n, mat, descr);
float det = determinant(n, mat);
if (det > maxDet)
{
maxDet = det;
maxDescr = descr;
}
}
MaxDetA[threadIdx] = maxDet;
MaxDescrA[threadIdx] = maxDescr;
threadBarrier();
// Let main thread output results.
threadBarrier();
}
delete[] mat;
return 0;
}
static void printMat(int n, float mat[])
{
for (int iRow = 0; iRow < n; ++iRow)
{
for (int iCol = 0; iCol < n; ++iCol)
{
std::cout << " " << mat[iRow * n + iCol];
}
std::cout << std::endl;
}
std::cout << std::endl;
}
int main(int argc, char* argv[])
{
if (argc > 1)
{
NMax = atoi(argv[1]);
if (NMax > 16)
{
NMax = 16;
}
}
if (argc > 2)
{
ThreadCount = atoi(argv[2]);
}
MaxDetA = new float[ThreadCount];
MaxDescrA = new uint32_t[ThreadCount];
pthread_mutex_init(&ThreadMutex, 0);
pthread_cond_init(&ThreadCond, 0);
int* threadIdxA = new int[ThreadCount];
pthread_t* threadA = new pthread_t[ThreadCount];
for (int iThread = 0; iThread < ThreadCount; ++iThread)
{
threadIdxA[iThread] = iThread;
pthread_create(threadA + iThread, 0, threadFunc, threadIdxA + iThread);
}
float* mat = new float[NMax * NMax];
for (int n = 1; n <= NMax; ++n)
{
threadBarrier();
float maxDet = 0.0f;
uint32_t maxDescr = 0;
for (int iThread = 0; iThread < ThreadCount; ++iThread)
{
if (MaxDetA[iThread] > maxDet)
{
maxDet = MaxDetA[iThread];
maxDescr = MaxDescrA[iThread];
}
}
std::cout << "n = " << n << " det = " << maxDet << std::endl;
buildMat(n, mat, maxDescr);
printMat(n, mat);
threadBarrier();
}
delete[] mat;
delete[] MaxDetA;
delete[] MaxDescrA;
delete[] threadIdxA;
delete[] threadA;
return 0;
}
n = 1..10: ghostbin.com/paste/axkpa \$\endgroup\$