#include <stdlib.h>
+#include <omp.h>
// Index matrix (by columns)
-int mi(int i, int j, int d1, int d2)
-{
- return j*d1 + i;
-}
+#define mi(i, j, d1, d2) (j*d1 + i)
// Index 3-tensor (by columns, matrices ordered by last dim)
-int ti(int i, int j, int k, int d1, int d2, int d3)
-{
- return k*d1*d2 + j*d1 + i;
-}
+#define ti(i, j, k, d1, d2, d3) (k*d1*d2 + j*d1 + i)
// Empirical cross-moment of order 2 between X size nxd and Y size n
void Moments_M2(double* X, double* Y, int* pn, int* pd, double* M2)
}
}
-#include <stdio.h>
-
// W = 1/N sum( t(g(Zi,theta)) g(Zi,theta) )
// with g(Zi, theta) = i-th contribution to all moments (size dim) - real moments
-//void Compute_Omega(double* X, int* Y, double* M, int* pn, int* pd, double* W)
-//{
-// int n=*pn, d=*pd;
-// int dim = d + d*d + d*d*d;
-// //double* W = (double*)malloc(dim*dim*sizeof(double));
-//
-// // (Re)Initialize W:
-// for (int j=0; j<dim; j++)
-// {
-// for (int k=0; k<dim; k++)
-// W[j*dim+k] = 0.0;
-// }
-// double* g = (double*)malloc(dim*sizeof(double));
-// for (int i=0; i<n; i++)
-// {
-// // g == gi:
-// for (int j=0; j<d; j++)
-// g[j] = Y[i] * X[mi(i,j,n,d)] - M[j];
-// for (int j=d; j<d+(d*d); j++)
-// {
-// int idx1 = (j-d) % d; //num row
-// int idx2 = ((j-d) - idx1) / d; //num col
-// g[j] = 0.0;
-// if (idx1 == idx2)
-// g[j] -= Y[i];
-// g[j] += Y[i] * X[mi(i,idx1,n,d)]*X[mi(i,idx2,n,d)] - M[j];
-// }
-// for (int j=d+d*d; j<dim; j++)
-// {
-// int idx1 = (j-d-d*d) % d; //num row
-// int idx2 = ((j-d-d*d - idx1) / d) %d; //num col
-// int idx3 = (((j-d-d*d - idx1) / d) - idx2) / d; //num "depth"
-// g[j] = 0.0;
-// if (idx1 == idx2)
-// g[j] -= Y[i] * X[mi(i,idx3,n,d)];
-// if (idx1 == idx3)
-// g[j] -= Y[i] * X[mi(i,idx2,n,d)];
-// if (idx2 == idx3)
-// g[j] -= Y[i] * X[mi(i,idx1,n,d)];
-// g[j] += Y[i] * X[mi(i,idx1,n,d)]*X[mi(i,idx2,n,d)]*X[mi(i,idx3,n,d)] - M[j];
-// }
-// // Add 1/n t(gi) %*% gi to W
-// for (int j=0; j<dim; j++)
-// {
-// for (int k=0; k<dim; k++)
-// W[j*dim+k] += g[j] * g[k] / n;
-// }
-// }
-// free(g);
-//}
-
-// Optimisation attempt:
-void Compute_Omega(double* X, int* Y, double* M, int* pn, int* pd, double* W)
+void Compute_Omega(double* X, int* Y, double* M, int* pnc, int* pn, int* pd, double* W)
{
- int n=*pn, d=*pd;
+ int nc=*pnc, n=*pn, d=*pd;
int dim = d + d*d + d*d*d;
//double* W = (double*)malloc(dim*dim*sizeof(double));
W[j*dim+k] = 0.0;
}
double* g = (double*)malloc(dim*sizeof(double));
+ omp_set_num_threads(nc >= 1 ? nc : omp_get_num_procs());
+ #pragma omp parallel for
for (int i=0; i<n; i++)
{
- printf("i: %i\n",i);
// g == gi:
for (int j=0; j<d; j++)
- g[j] = (Y[i] ? X[mi(i,j,n,d)] - M[j] : 0.0);
+ g[j] = Y[i] * X[mi(i,j,n,d)] - M[j];
for (int j=d; j<d+(d*d); j++)
{
int idx1 = (j-d) % d; //num row
int idx2 = ((j-d) - idx1) / d; //num col
g[j] = 0.0;
- if (Y[i])
- {
- if (idx1 == idx2)
- g[j]--;
- g[j] += X[mi(i,idx1,n,d)]*X[mi(i,idx2,n,d)] - M[j];
- }
+ if (idx1 == idx2)
+ g[j] -= Y[i];
+ g[j] += Y[i] * X[mi(i,idx1,n,d)]*X[mi(i,idx2,n,d)] - M[j];
}
for (int j=d+d*d; j<dim; j++)
{
int idx2 = ((j-d-d*d - idx1) / d) %d; //num col
int idx3 = (((j-d-d*d - idx1) / d) - idx2) / d; //num "depth"
g[j] = 0.0;
- if (Y[i])
- {
- if (idx1 == idx2)
- g[j] -= X[mi(i,idx3,n,d)];
- if (idx1 == idx3)
- g[j] -= X[mi(i,idx2,n,d)];
- if (idx2 == idx3)
- g[j] -= X[mi(i,idx1,n,d)];
- g[j] += X[mi(i,idx1,n,d)]*X[mi(i,idx2,n,d)]*X[mi(i,idx3,n,d)] - M[j];
- }
+ if (idx1 == idx2)
+ g[j] -= Y[i] * X[mi(i,idx3,n,d)];
+ if (idx1 == idx3)
+ g[j] -= Y[i] * X[mi(i,idx2,n,d)];
+ if (idx2 == idx3)
+ g[j] -= Y[i] * X[mi(i,idx1,n,d)];
+ g[j] += Y[i] * X[mi(i,idx1,n,d)]*X[mi(i,idx2,n,d)]*X[mi(i,idx3,n,d)] - M[j];
}
// Add 1/n t(gi) %*% gi to W
for (int j=0; j<dim; j++)
{
- for (int k=0; k<dim; k++)
- W[j*dim+k] += g[j] * g[k] / n;
+ // This final nested loop is very costly. Some basic optimisations:
+ double gj = g[j];
+ int baseIdx = j * dim;
+ #pragma GCC unroll 32
+ for (int k=j; k>=0; k--)
+ W[baseIdx+k] += gj * g[k];
}
}
+ // Normalize W: x 1/n
+ for (int j=0; j<dim; j++)
+ {
+ for (int k=j; k<dim; k++)
+ W[mi(j,k,dim,dim)] /= n;
+ }
+ // Symmetrize W: W[k,j] = W[j,k] for k > j
+ for (int j=0; j<dim; j++)
+ {
+ for (int k=j+1; k<dim; k++)
+ W[mi(k,j,dim,dim)] = W[mi(j,k,dim,dim)];
+ }
free(g);
}