idamnjanovic@53: /**************************************************************************
idamnjanovic@53:  *
idamnjanovic@53:  * File name: ompcore.c
idamnjanovic@53:  *
idamnjanovic@53:  * Ron Rubinstein
idamnjanovic@53:  * Computer Science Department
idamnjanovic@53:  * Technion, Haifa 32000 Israel
idamnjanovic@53:  * ronrubin@cs
idamnjanovic@53:  *
idamnjanovic@53:  * Last Updated: 25.8.2009
idamnjanovic@53:  *
idamnjanovic@53:  *************************************************************************/
idamnjanovic@53: 
idamnjanovic@53: 
idamnjanovic@53: #include "ompcore.h"
idamnjanovic@53: #include "omputils.h"
idamnjanovic@53: #include "ompprof.h"
idamnjanovic@53: #include "myblas.h"
idamnjanovic@53: #include <math.h>
idamnjanovic@53: #include <string.h>
idamnjanovic@53: 
idamnjanovic@53: 
idamnjanovic@53: 
idamnjanovic@53: /******************************************************************************
idamnjanovic@53:  *                                                                            *
idamnjanovic@53:  *                           Batch-OMP Implementation                         *
idamnjanovic@53:  *                                                                            *
idamnjanovic@53:  ******************************************************************************/  
idamnjanovic@53: 
idamnjanovic@53: mxArray* ompcore(double D[], double x[], double DtX[], double XtX[], double G[], mwSize n, mwSize m, mwSize L,
idamnjanovic@53:                  int T, double eps, int gamma_mode, int profile, double msg_delta, int erroromp)
idamnjanovic@53: {
idamnjanovic@53:   
idamnjanovic@53:   profdata pd;
idamnjanovic@53:   mxArray *Gamma;
idamnjanovic@53:   mwIndex i, j, signum, pos, *ind, *gammaIr, *gammaJc, gamma_count;
idamnjanovic@53:   mwSize allocated_coefs, allocated_cols;
idamnjanovic@53:   int DtX_specified, XtX_specified, batchomp, standardomp, *selected_atoms;
idamnjanovic@53:   double *alpha, *r, *Lchol, *c, *Gsub, *Dsub, sum, *gammaPr, *tempvec1, *tempvec2; 
idamnjanovic@53:   double eps2, resnorm, delta, deltaprev, secs_remain;
idamnjanovic@53:   int mins_remain, hrs_remain;
idamnjanovic@53:   clock_t lastprint_time, starttime;
idamnjanovic@53:  
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /*** status flags ***/
idamnjanovic@53:   
idamnjanovic@53:   DtX_specified = (DtX!=0);   /* indicates whether D'*x was provided */
idamnjanovic@53:   XtX_specified = (XtX!=0);   /* indicates whether sum(x.*x) was provided */
idamnjanovic@53:   
idamnjanovic@53:   standardomp = (G==0);       /* batch-omp or standard omp are selected depending on availability of G */
idamnjanovic@53:   batchomp = !standardomp;
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /*** allocate output matrix ***/
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   if (gamma_mode == FULL_GAMMA) {
idamnjanovic@53:     
idamnjanovic@53:     /* allocate full matrix of size m X L */
idamnjanovic@53:     
idamnjanovic@53:     Gamma = mxCreateDoubleMatrix(m, L, mxREAL);
idamnjanovic@53:     gammaPr = mxGetPr(Gamma);
idamnjanovic@53:     gammaIr = 0;
idamnjanovic@53:     gammaJc = 0;
idamnjanovic@53:   }
idamnjanovic@53:   else {
idamnjanovic@53:     
idamnjanovic@53:     /* allocate sparse matrix with room for allocated_coefs nonzeros */
idamnjanovic@53:     
idamnjanovic@53:     /* for error-omp, begin with L*sqrt(n)/2 allocated nonzeros, otherwise allocate L*T nonzeros */
idamnjanovic@53:     allocated_coefs = erroromp ? (mwSize)(ceil(L*sqrt((double)n)/2.0) + 1.01) : L*T;
idamnjanovic@53:     Gamma = mxCreateSparse(m, L, allocated_coefs, mxREAL);
idamnjanovic@53:     gammaPr = mxGetPr(Gamma);
idamnjanovic@53:     gammaIr = mxGetIr(Gamma);
idamnjanovic@53:     gammaJc = mxGetJc(Gamma);
idamnjanovic@53:     gamma_count = 0;
idamnjanovic@53:     gammaJc[0] = 0;
idamnjanovic@53:   }
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /*** helper arrays ***/
idamnjanovic@53:   
idamnjanovic@53:   alpha = (double*)mxMalloc(m*sizeof(double));        /* contains D'*residual */
idamnjanovic@53:   ind = (mwIndex*)mxMalloc(n*sizeof(mwIndex));        /* indices of selected atoms */
idamnjanovic@53:   selected_atoms = (int*)mxMalloc(m*sizeof(int));     /* binary array with 1's for selected atoms */
idamnjanovic@53:   c = (double*)mxMalloc(n*sizeof(double));            /* orthogonal projection result */
idamnjanovic@53:   
idamnjanovic@53:   /* current number of columns in Dsub / Gsub / Lchol */
idamnjanovic@53:   allocated_cols = erroromp ? (mwSize)(ceil(sqrt((double)n)/2.0) + 1.01) : T;
idamnjanovic@53:   
idamnjanovic@53:   /* Cholesky decomposition of D_I'*D_I */
idamnjanovic@53:   Lchol = (double*)mxMalloc(n*allocated_cols*sizeof(double));
idamnjanovic@53: 
idamnjanovic@53:   /* temporary vectors for various computations */
idamnjanovic@53:   tempvec1 = (double*)mxMalloc(m*sizeof(double));
idamnjanovic@53:   tempvec2 = (double*)mxMalloc(m*sizeof(double));
idamnjanovic@53:   
idamnjanovic@53:   if (batchomp) {
idamnjanovic@53:     /* matrix containing G(:,ind) - the columns of G corresponding to the selected atoms, in order of selection */
idamnjanovic@53:     Gsub = (double*)mxMalloc(m*allocated_cols*sizeof(double));
idamnjanovic@53:   }
idamnjanovic@53:   else {
idamnjanovic@53:     /* matrix containing D(:,ind) - the selected atoms from D, in order of selection */
idamnjanovic@53:     Dsub = (double*)mxMalloc(n*allocated_cols*sizeof(double));
idamnjanovic@53:     
idamnjanovic@53:     /* stores the residual */
idamnjanovic@53:     r = (double*)mxMalloc(n*sizeof(double));        
idamnjanovic@53:   }
idamnjanovic@53:   
idamnjanovic@53:   if (!DtX_specified) {
idamnjanovic@53:     /* contains D'*x for the current signal */
idamnjanovic@53:     DtX = (double*)mxMalloc(m*sizeof(double));  
idamnjanovic@53:   }
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /*** initializations for error omp ***/
idamnjanovic@53:   
idamnjanovic@53:   if (erroromp) {
idamnjanovic@53:     eps2 = eps*eps;        /* compute eps^2 */
idamnjanovic@53:     if (T<0 || T>n) {      /* unspecified max atom num - set max atoms to n */
idamnjanovic@53:       T = n;
idamnjanovic@53:     }
idamnjanovic@53:   }
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /*** initialize timers ***/
idamnjanovic@53:   
idamnjanovic@53:   initprofdata(&pd);             /* initialize profiling counters */
idamnjanovic@53:   starttime = clock();           /* record starting time for eta computations */
idamnjanovic@53:   lastprint_time = starttime;    /* time of last status display */
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /**********************   perform omp for each signal   **********************/
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   for (signum=0; signum<L; ++signum) {
idamnjanovic@53:     
idamnjanovic@53:     
idamnjanovic@53:     /* initialize residual norm and deltaprev for error-omp */
idamnjanovic@53:     
idamnjanovic@53:     if (erroromp) {
idamnjanovic@53:       if (XtX_specified) {
idamnjanovic@53:         resnorm = XtX[signum];
idamnjanovic@53:       }
idamnjanovic@53:       else {
idamnjanovic@53:         resnorm = dotprod(x+n*signum, x+n*signum, n);
idamnjanovic@53:         addproftime(&pd, XtX_TIME);
idamnjanovic@53:       }
idamnjanovic@53:       deltaprev = 0;     /* delta tracks the value of gamma'*G*gamma */
idamnjanovic@53:     }
idamnjanovic@53:     else {
idamnjanovic@53:       /* ignore residual norm stopping criterion */
idamnjanovic@53:       eps2 = 0;
idamnjanovic@53:       resnorm = 1;
idamnjanovic@53:     }
idamnjanovic@53:     
idamnjanovic@53:     
idamnjanovic@53:     if (resnorm>eps2 && T>0) {
idamnjanovic@53:       
idamnjanovic@53:       /* compute DtX */
idamnjanovic@53:       
idamnjanovic@53:       if (!DtX_specified) {
idamnjanovic@53:         matT_vec(1, D, x+n*signum, DtX, n, m);
idamnjanovic@53:         addproftime(&pd, DtX_TIME);
idamnjanovic@53:       }
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /* initialize alpha := DtX */
idamnjanovic@53:       
idamnjanovic@53:       memcpy(alpha, DtX + m*signum*DtX_specified, m*sizeof(double));
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /* mark all atoms as unselected */
idamnjanovic@53:       
idamnjanovic@53:       for (i=0; i<m; ++i) {
idamnjanovic@53:         selected_atoms[i] = 0;
idamnjanovic@53:       }
idamnjanovic@53:       
idamnjanovic@53:     }
idamnjanovic@53:     
idamnjanovic@53: 
idamnjanovic@53:     /* main loop */
idamnjanovic@53:     
idamnjanovic@53:     i=0;
idamnjanovic@53:     while (resnorm>eps2 && i<T) {
idamnjanovic@53: 
idamnjanovic@53:       /* index of next atom */
idamnjanovic@53:       
idamnjanovic@53:       pos = maxabs(alpha, m);
idamnjanovic@53:       addproftime(&pd, MAXABS_TIME);
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /* stop criterion: selected same atom twice, or inner product too small */
idamnjanovic@53:       
idamnjanovic@53:       if (selected_atoms[pos] || alpha[pos]*alpha[pos]<1e-14) {
idamnjanovic@53:         break;
idamnjanovic@53:       }
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /* mark selected atom */
idamnjanovic@53:       
idamnjanovic@53:       ind[i] = pos;
idamnjanovic@53:       selected_atoms[pos] = 1;
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /* matrix reallocation */
idamnjanovic@53:       
idamnjanovic@53:       if (erroromp && i>=allocated_cols) {
idamnjanovic@53:         
idamnjanovic@53:         allocated_cols = (mwSize)(ceil(allocated_cols*MAT_INC_FACTOR) + 1.01);
idamnjanovic@53:         
idamnjanovic@53:         Lchol = (double*)mxRealloc(Lchol,n*allocated_cols*sizeof(double));
idamnjanovic@53:         
idamnjanovic@53:         batchomp ? (Gsub = (double*)mxRealloc(Gsub,m*allocated_cols*sizeof(double))) :
idamnjanovic@53:                    (Dsub = (double*)mxRealloc(Dsub,n*allocated_cols*sizeof(double))) ;
idamnjanovic@53:       }
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /* append column to Gsub or Dsub */
idamnjanovic@53:       
idamnjanovic@53:       if (batchomp) {
idamnjanovic@53:         memcpy(Gsub+i*m, G+pos*m, m*sizeof(double));
idamnjanovic@53:       }
idamnjanovic@53:       else {
idamnjanovic@53:         memcpy(Dsub+i*n, D+pos*n, n*sizeof(double));
idamnjanovic@53:       }
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /*** Cholesky update ***/
idamnjanovic@53:       
idamnjanovic@53:       if (i==0) {
idamnjanovic@53:         *Lchol = 1;
idamnjanovic@53:       }
idamnjanovic@53:       else {
idamnjanovic@53:         
idamnjanovic@53:         /* incremental Cholesky decomposition: compute next row of Lchol */
idamnjanovic@53:         
idamnjanovic@53:         if (standardomp) {
idamnjanovic@53:           matT_vec(1, Dsub, D+n*pos, tempvec1, n, i);      /* compute tempvec1 := Dsub'*d where d is new atom */
idamnjanovic@53:           addproftime(&pd, DtD_TIME);
idamnjanovic@53:         }
idamnjanovic@53:         else {
idamnjanovic@53:           vec_assign(tempvec1, Gsub+i*m, ind, i);          /* extract tempvec1 := Gsub(ind,i) */
idamnjanovic@53:         }
idamnjanovic@53:         backsubst('L', Lchol, tempvec1, tempvec2, n, i);   /* compute tempvec2 = Lchol \ tempvec1 */
idamnjanovic@53:         for (j=0; j<i; ++j) {                              /* write tempvec2 to end of Lchol */
idamnjanovic@53:           Lchol[j*n+i] = tempvec2[j];
idamnjanovic@53:         }
idamnjanovic@53:         
idamnjanovic@53:         /* compute Lchol(i,i) */
idamnjanovic@53:         sum = 0;
idamnjanovic@53:         for (j=0; j<i; ++j) {         /* compute sum of squares of last row without Lchol(i,i) */
idamnjanovic@53:           sum += SQR(Lchol[j*n+i]);
idamnjanovic@53:         }
idamnjanovic@53:         if ( (1-sum) <= 1e-14 ) {     /* Lchol(i,i) is zero => selected atoms are dependent */
idamnjanovic@53:           break;
idamnjanovic@53:         }
idamnjanovic@53:         Lchol[i*n+i] = sqrt(1-sum);
idamnjanovic@53:       }
idamnjanovic@53:       
idamnjanovic@53:       addproftime(&pd, LCHOL_TIME);
idamnjanovic@53: 
idamnjanovic@53:       i++;
idamnjanovic@53:       
idamnjanovic@53:       
idamnjanovic@53:       /* perform orthogonal projection and compute sparse coefficients */
idamnjanovic@53:       
idamnjanovic@53:       vec_assign(tempvec1, DtX + m*signum*DtX_specified, ind, i);   /* extract tempvec1 = DtX(ind) */
idamnjanovic@53:       cholsolve('L', Lchol, tempvec1, c, n, i);                     /* solve LL'c = tempvec1 for c */
idamnjanovic@53:       addproftime(&pd, COMPCOEF_TIME);
idamnjanovic@53:       
idamnjanovic@53: 
idamnjanovic@53:       /* update alpha = D'*residual */
idamnjanovic@53:       
idamnjanovic@53:       if (standardomp) {
idamnjanovic@53:         mat_vec(-1, Dsub, c, r, n, i);             /* compute r := -Dsub*c */
idamnjanovic@53:         vec_sum(1, x+n*signum, r, n);              /* compute r := x+r */
idamnjanovic@53:         
idamnjanovic@53:         
idamnjanovic@53:         /*memcpy(r, x+n*signum, n*sizeof(double));   /* assign r := x */
idamnjanovic@53:         /*mat_vec1(-1, Dsub, c, 1, r, n, i);         /* compute r := r-Dsub*c */
idamnjanovic@53:         
idamnjanovic@53:         addproftime(&pd, COMPRES_TIME);
idamnjanovic@53:         matT_vec(1, D, r, alpha, n, m);            /* compute alpha := D'*r */
idamnjanovic@53:         addproftime(&pd, DtR_TIME);
idamnjanovic@53:         
idamnjanovic@53:         /* update residual norm */
idamnjanovic@53:         if (erroromp) {
idamnjanovic@53:           resnorm = dotprod(r, r, n);
idamnjanovic@53:           addproftime(&pd, UPDATE_RESNORM_TIME);
idamnjanovic@53:         }
idamnjanovic@53:       }
idamnjanovic@53:       else {
idamnjanovic@53:         mat_vec(1, Gsub, c, tempvec1, m, i);                              /* compute tempvec1 := Gsub*c */
idamnjanovic@53:         memcpy(alpha, DtX + m*signum*DtX_specified, m*sizeof(double));    /* set alpha = D'*x */
idamnjanovic@53:         vec_sum(-1, tempvec1, alpha, m);                                  /* compute alpha := alpha - tempvec1 */
idamnjanovic@53:         addproftime(&pd, UPDATE_DtR_TIME);
idamnjanovic@53:         
idamnjanovic@53:         /* update residual norm */
idamnjanovic@53:         if (erroromp) {
idamnjanovic@53:           vec_assign(tempvec2, tempvec1, ind, i);      /* assign tempvec2 := tempvec1(ind) */
idamnjanovic@53:           delta = dotprod(c,tempvec2,i);               /* compute c'*tempvec2 */
idamnjanovic@53:           resnorm = resnorm - delta + deltaprev;       /* residual norm update */
idamnjanovic@53:           deltaprev = delta;
idamnjanovic@53:           addproftime(&pd, UPDATE_RESNORM_TIME);
idamnjanovic@53:         }
idamnjanovic@53:       }
idamnjanovic@53:     }
idamnjanovic@53:     
idamnjanovic@53:     
idamnjanovic@53:     /*** generate output vector gamma ***/
idamnjanovic@53: 
idamnjanovic@53:     if (gamma_mode == FULL_GAMMA) {    /* write the coefs in c to their correct positions in gamma */
idamnjanovic@53:       for (j=0; j<i; ++j) {
idamnjanovic@53:         gammaPr[m*signum + ind[j]] = c[j];
idamnjanovic@53:       }
idamnjanovic@53:     }
idamnjanovic@53:     else {
idamnjanovic@53:       /* sort the coefs by index before writing them to gamma */
idamnjanovic@53:       quicksort(ind,c,i);
idamnjanovic@53:       addproftime(&pd, INDEXSORT_TIME);
idamnjanovic@53:       
idamnjanovic@53:       /* gamma is full - reallocate */
idamnjanovic@53:       if (gamma_count+i >= allocated_coefs) {
idamnjanovic@53:         
idamnjanovic@53:         while(gamma_count+i >= allocated_coefs) {
idamnjanovic@53:           allocated_coefs = (mwSize)(ceil(GAMMA_INC_FACTOR*allocated_coefs) + 1.01);
idamnjanovic@53:         }
idamnjanovic@53:         
idamnjanovic@53:         mxSetNzmax(Gamma, allocated_coefs);
idamnjanovic@53:         mxSetPr(Gamma, mxRealloc(gammaPr, allocated_coefs*sizeof(double)));
idamnjanovic@53:         mxSetIr(Gamma, mxRealloc(gammaIr, allocated_coefs*sizeof(mwIndex)));
idamnjanovic@53:         
idamnjanovic@53:         gammaPr = mxGetPr(Gamma);
idamnjanovic@53:         gammaIr = mxGetIr(Gamma);
idamnjanovic@53:       }
idamnjanovic@53:       
idamnjanovic@53:       /* append coefs to gamma and update the indices */
idamnjanovic@53:       for (j=0; j<i; ++j) {
idamnjanovic@53:         gammaPr[gamma_count] = c[j];
idamnjanovic@53:         gammaIr[gamma_count] = ind[j];
idamnjanovic@53:         gamma_count++;
idamnjanovic@53:       }
idamnjanovic@53:       gammaJc[signum+1] = gammaJc[signum] + i;
idamnjanovic@53:     }
idamnjanovic@53:     
idamnjanovic@53:     
idamnjanovic@53:     
idamnjanovic@53:     /*** display status messages ***/
idamnjanovic@53:     
idamnjanovic@53:     if (msg_delta>0 && (clock()-lastprint_time)/(double)CLOCKS_PER_SEC >= msg_delta)
idamnjanovic@53:     {
idamnjanovic@53:       lastprint_time = clock();
idamnjanovic@53:       
idamnjanovic@53:       /* estimated remainig time */
idamnjanovic@53:       secs2hms( ((L-signum-1)/(double)(signum+1)) * ((lastprint_time-starttime)/(double)CLOCKS_PER_SEC) ,
idamnjanovic@53:         &hrs_remain, &mins_remain, &secs_remain);
idamnjanovic@53:       
idamnjanovic@53:       mexPrintf("omp: signal %d / %d, estimated remaining time: %02d:%02d:%05.2f\n",        
idamnjanovic@53:         signum+1, L, hrs_remain, mins_remain, secs_remain);
idamnjanovic@53:       mexEvalString("drawnow;");
idamnjanovic@53:     }
idamnjanovic@53:     
idamnjanovic@53:   }
idamnjanovic@53:   
idamnjanovic@53:   /* end omp */
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /*** print final messages ***/
idamnjanovic@53:   
idamnjanovic@53:   if (msg_delta>0) {
idamnjanovic@53:     mexPrintf("omp: signal %d / %d\n", signum, L);
idamnjanovic@53:   }
idamnjanovic@53:   
idamnjanovic@53:   if (profile) {
idamnjanovic@53:     printprofinfo(&pd, erroromp, batchomp, L);
idamnjanovic@53:   }
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   
idamnjanovic@53:   /* free memory */
idamnjanovic@53:   
idamnjanovic@53:   if (!DtX_specified) {
idamnjanovic@53:     mxFree(DtX);
idamnjanovic@53:   }
idamnjanovic@53:   if (standardomp) {
idamnjanovic@53:     mxFree(r);
idamnjanovic@53:     mxFree(Dsub);
idamnjanovic@53:   }
idamnjanovic@53:   else {
idamnjanovic@53:     mxFree(Gsub);
idamnjanovic@53:   }  
idamnjanovic@53:   mxFree(tempvec2);
idamnjanovic@53:   mxFree(tempvec1);
idamnjanovic@53:   mxFree(Lchol);
idamnjanovic@53:   mxFree(c);
idamnjanovic@53:   mxFree(selected_atoms);
idamnjanovic@53:   mxFree(ind);
idamnjanovic@53:   mxFree(alpha);
idamnjanovic@53:   
idamnjanovic@53:   return Gamma;
idamnjanovic@53: }