HouseholderDecomposition.cc

Go to the documentation of this file.

#include "Calibration/Tools/interface/HouseholderDecomposition.h"
#include <cfloat>
#include <cmath>
#include <cstdlib>

HouseholderDecomposition::HouseholderDecomposition(int squareMode_, int mineta_, int maxeta_, int minphi_, int maxphi_)
    : squareMode(squareMode_), countEvents(0), mineta(mineta_), maxeta(maxeta_), minphi(minphi_), maxphi(maxphi_) {
  Neta = maxeta - mineta + 1;
  if (mineta * maxeta < 0)
    Neta--;  // there's no eta index = 0
  Nphi = maxphi - minphi + 1;
  if (Nphi < 0)
    Nphi += 360;

  Nchannels = Neta * Nphi;  // no. of channels, get it from edges of the region

  Nxtals = squareMode * squareMode;  // no. of xtals in one event

  sigmaReplacement = 0.00001;  // the sum of columns is replaced by this value in case it is zero (e.g. dead crystal)
}

HouseholderDecomposition::~HouseholderDecomposition() {}

std::vector<float> HouseholderDecomposition::runRegional(const std::vector<std::vector<float> >& eventMatrix,
                                                         const std::vector<int>& VmaxCeta,
                                                         const std::vector<int>& VmaxCphi,
                                                         const std::vector<float>& energyVector,
                                                         const int& nIter,
                                                         const int& regLength) {
  // make regions
  makeRegions(regLength);

  Nevents = eventMatrix.size();  // Number of events to calibrate with

  std::vector<float> totalSolution(Nchannels, 1.);
  std::vector<float> iterSolution(Nchannels, 1.);
  std::vector<std::vector<float> > myEventMatrix(eventMatrix);

  // loop over nIter
  for (int iter = 1; iter <= nIter; iter++) {
    // loop over regions
    for (unsigned int ireg = 0; ireg < regMinEta.size(); ireg++) {
      std::vector<float> regIterSolution, regEnergyVector;
      std::vector<int> regVmaxCeta, regVmaxCphi;
      std::vector<std::vector<float> > regEventMatrix;

      // initialize new instance with regional min,max indices
      HouseholderDecomposition regionalHH(
          squareMode, regMinEta[ireg], regMaxEta[ireg], regMinPhi[ireg], regMaxPhi[ireg]);

      // copy all events in region into new eventmatrix, energyvector, VmaxCeta, VmaxCphi
      for (unsigned int ia = 0; ia < VmaxCeta.size(); ia++) {
        if ((VmaxCeta[ia] >= regMinEta[ireg]) && (VmaxCeta[ia] <= regMaxEta[ireg]) &&
            (VmaxCphi[ia] >= regMinPhi[ireg]) && (VmaxCphi[ia] <= regMaxPhi[ireg])) {
          // save event, calculate new eventmatrix(truncated) and energy
          regVmaxCeta.push_back(VmaxCeta[ia]);
          regVmaxCphi.push_back(VmaxCphi[ia]);

          std::vector<float> regEvent = myEventMatrix[ia];
          float regEnergy = energyVector[ia];
          for (int i2 = 0; i2 < Nxtals; i2++) {
            int iFullReg = regionalHH.indexSqr2Reg(i2, VmaxCeta[ia], VmaxCphi[ia]);
            if (iFullReg < 0)  // crystal outside
            {
              regEnergy -= regEvent[i2];
              regEvent[i2] = 0.;
            }
          }
          regEventMatrix.push_back(regEvent);
          regEnergyVector.push_back(regEnergy);
        }
      }

      // calibrate
      //      std::cout << "HouseholderDecomposition::runRegional - Starting calibration of region " << ireg << ": eta "
      //           << regMinEta[ireg] << " to " << regMaxEta[ireg] << ", phi " << regMinPhi[ireg] << " to " << regMaxPhi[ireg] << std::endl;
      regIterSolution = regionalHH.iterate(regEventMatrix, regVmaxCeta, regVmaxCphi, regEnergyVector);
      //      std::cout << "HouseholderDecomposition::runRegional - calibration of region finished. " << std::endl;

      // save solution into global iterSolution
      // don't forget to delete the ones that are on the border !
      for (unsigned int i1 = 0; i1 < regIterSolution.size(); i1++) {
        int regFrame = regLength / 2;
        int currRegPhiRange = regMaxPhi[ireg] - regMinPhi[ireg] + 1;
        int currRegEta = i1 / currRegPhiRange + regMinEta[ireg];
        int currRegPhi = i1 % currRegPhiRange + regMinPhi[ireg];
        int newindex = -100;
        // if crystal well inside:
        if ((currRegEta >= (regMinEta[ireg] + regFrame * (!(regMinEta[ireg] == mineta)))) &&
            (currRegEta <= (regMaxEta[ireg] - regFrame * (!(regMaxEta[ireg] == maxeta)))) &&
            (currRegPhi >= (regMinPhi[ireg] + regFrame * (!(regMinPhi[ireg] == minphi)))) &&
            (currRegPhi <= (regMaxPhi[ireg] - regFrame * (!(regMaxPhi[ireg] == maxphi))))) {
          newindex = (currRegEta - mineta) * Nphi + currRegPhi - minphi;
          iterSolution[newindex] = regIterSolution[i1];
        }
      }
    }  // end loop over regions

    if (iterSolution.empty())
      return iterSolution;

    // re-calibrate eventMatrix with solution
    for (int ievent = 0; ievent < Nevents; ievent++) {
      myEventMatrix[ievent] = recalibrateEvent(myEventMatrix[ievent], VmaxCeta[ievent], VmaxCphi[ievent], iterSolution);
    }

    // save solution into theCalibVector
    for (int i = 0; i < Nchannels; i++) {
      totalSolution[i] *= iterSolution[i];
    }

  }  // end loop over nIter

  return totalSolution;
}

std::vector<float> HouseholderDecomposition::iterate(const std::vector<std::vector<float> >& eventMatrix,
                                                     const std::vector<int>& VmaxCeta,
                                                     const std::vector<int>& VmaxCphi,
                                                     const std::vector<float>& energyVector,
                                                     const int& nIter,
                                                     const bool& normalizeFlag) {
  Nevents = eventMatrix.size();  // Number of events to calibrate with

  std::vector<float> totalSolution(Nchannels, 1.);
  std::vector<float> iterSolution;
  std::vector<std::vector<float> > myEventMatrix(eventMatrix);
  std::vector<float> myEnergyVector(energyVector);

  int i, j;

  // Iterate the correction
  for (int iter = 1; iter <= nIter; iter++) {
    // if normalization flag is set, normalize energies
    float sumOverEnergy;
    if (normalizeFlag) {
      float scale = 0.;

      for (i = 0; i < Nevents; i++) {
        sumOverEnergy = 0.;
        for (j = 0; j < Nxtals; j++) {
          sumOverEnergy += myEventMatrix[i][j];
        }
        sumOverEnergy /= myEnergyVector[i];
        scale += sumOverEnergy;
      }
      scale /= Nevents;

      for (i = 0; i < Nevents; i++) {
        myEnergyVector[i] *= scale;
      }
    }  // end normalize energies

    // now the real work starts:
    iterSolution = iterate(myEventMatrix, VmaxCeta, VmaxCphi, myEnergyVector);

    if (iterSolution.empty())
      return iterSolution;

    // re-calibrate eventMatrix with solution
    for (int ievent = 0; ievent < Nevents; ievent++) {
      myEventMatrix[ievent] = recalibrateEvent(myEventMatrix[ievent], VmaxCeta[ievent], VmaxCphi[ievent], iterSolution);
    }

    for (int i = 0; i < Nchannels; i++) {
      // save solution into theCalibVector
      totalSolution[i] *= iterSolution[i];
    }

  }  // end iterate correction

  return totalSolution;
}

std::vector<float> HouseholderDecomposition::iterate(const std::vector<std::vector<float> >& eventMatrix,
                                                     const std::vector<int>& VmaxCeta,
                                                     const std::vector<int>& VmaxCphi,
                                                     const std::vector<float>& energyVectorOrig) {
  std::vector<float> solution;

  Nevents = eventMatrix.size();  // Number of events to calibrate with

  if (Nchannels > Nevents) {
    std::cout << "Householder::runIter(): more channels to calibrate than events available. " << std::endl;
    std::cout << "  Nchannels=" << Nchannels << std::endl;
    std::cout << "  Nevents=" << Nevents << std::endl;
    std::cout << " ******************    ERROR   *********************" << std::endl;
    return solution;  // empty vector
  }

  // input: eventMatrixOrig - the unzipped matrix
  eventMatrixOrig = unzipMatrix(eventMatrix, VmaxCeta, VmaxCphi);

  if (eventMatrixOrig.size() != energyVectorOrig.size()) {
    std::cout << "Householder::runIter(): matrix dimensions non-conformant. " << std::endl;
    std::cout << "  energyVectorOrig.size()=" << energyVectorOrig.size() << std::endl;
    std::cout << "  eventMatrixOrig.size()=" << eventMatrixOrig.size() << std::endl;
    std::cout << " ******************    ERROR   *********************" << std::endl;
    return solution;  // empty vector
  }

  int i, j;
  eventMatrixProc = eventMatrixOrig;
  energyVectorProc = energyVectorOrig;  // copy energyVectorOrig vector
  std::vector<float> e(Nchannels);
  alpha.assign(Nchannels, 0.);
  pivot.assign(Nchannels, 0);

  //--------------------
  bool decomposeSuccess = decompose();

  if (!decomposeSuccess) {
    std::cout << "Householder::runIter(): Failed: Singular condition in decomposition." << std::endl;
    std::cout << "***************** PROBLEM in DECOMPOSITION *************************" << std::endl;
    return solution;  // empty vector
  }

  /* DBL_EPSILON: Difference between 1.0 and the minimum float greater than 1.0 */
  float mydbleps = 2.22045e-16;  //DBL_EPSILON;
  float etasqr = mydbleps * mydbleps;
  //  std::cout << "LOOK at DBL_EPSILON :" << mydbleps <<std::endl;

  //--------------------
  // apply transformations to rhs - find solution vector
  solution.assign(Nchannels, 0.);
  solve(solution);

  // compute residual vector energyVectorProc
  for (i = 0; i < Nevents; i++) {
    energyVectorProc[i] = energyVectorOrig[i];
    for (j = 0; j < Nchannels; j++) {
      energyVectorProc[i] -= eventMatrixOrig[i][j] * solution[j];
    }
  }

  //--------------------
  // compute first correction vector e
  solve(e);

  float normy0 = 0.;
  float norme1 = 0.;
  float norme0;

  for (i = 0; i < Nchannels; i++) {
    normy0 += solution[i] * solution[i];
    norme1 += e[i] * e[i];
  }

  //  std::cout << "Householder::runIter(): applying first correction";
  //  std::cout << " normy0 = " << normy0;
  //  std::cout << " norme1 = " << norme1 << std::endl;

  // not attempt at obtaining the solution is made unless the norm of the first
  // correction  is significantly smaller than the norm of the initial solution
  if (norme1 > (0.0625 * normy0)) {
    //      std::cout << "Householder::runIter(): first correction is too large. Failed." << std::endl;
  }

  // improve the solution
  for (i = 0; i < Nchannels; i++) {
    solution[i] += e[i];
  }

  //  std::cout << "Householder::runIter(): improving solution...." << std::endl;

  //--------------------
  // only continue iteration if the correction was significant
  while (norme1 > (etasqr * normy0)) {
    //      std::cout << "Householder::runIter(): norme1 = " << norme1 << std::endl;

    for (i = 0; i < Nevents; i++) {
      energyVectorProc[i] = energyVectorOrig[i];
      for (j = 0; j < Nchannels; j++) {
        energyVectorProc[i] -= eventMatrixOrig[i][j] * solution[j];
      }
    }

    // compute next correction vector
    solve(e);

    norme0 = norme1;
    norme1 = 0.;

    for (i = 0; i < Nchannels; i++) {
      norme1 += e[i] * e[i];
    }

    // terminate iteration if the norm of the new correction failed to decrease
    // significantly compared to the norm of the previous correction
    if (norme1 > (0.0625 * norme0))
      break;

    // apply correction vector
    for (i = 0; i < Nchannels; i++) {
      solution[i] += e[i];
    }
  }

  //clean up
  eventMatrixOrig.clear();
  eventMatrixProc.clear();
  energyVectorProc.clear();
  alpha.clear();
  pivot.clear();

  return solution;
}

bool HouseholderDecomposition::decompose() {
  int i, j, jbar, k;
  float beta, sigma, alphak, eventMatrixkk;
  std::vector<float> y(Nchannels);
  std::vector<float> sum(Nchannels);

  //  std::cout << "Householder::decompose() started" << std::endl;

  for (j = 0; j < Nchannels; j++) {
    // jth column sum: squared sum for each crystal
    sum[j] = 0.;
    for (i = 0; i < Nevents; i++)
      sum[j] += eventMatrixProc[i][j] * eventMatrixProc[i][j];

    // bookkeeping vector
    pivot[j] = j;
  }

  for (k = 0; k < Nchannels; k++) {
    // kth Householder transformation
    sigma = sum[k];
    jbar = k;

    // go through all following columns
    // find the largest sumSquared in the following columns
    for (j = k + 1; j < Nchannels; j++) {
      if (sum[j] > sigma) {
        sigma = sum[j];
        jbar = j;
      }
    }

    if (jbar != k) {
      // column interchange:
      //     interchange within: bookkeeping vector, squaredSum, eventMatrixProc

      i = pivot[k];
      pivot[k] = pivot[jbar];
      pivot[jbar] = i;

      sum[jbar] = sum[k];
      sum[k] = sigma;

      for (i = 0; i < Nevents; i++) {
        sigma = eventMatrixProc[i][k];
        eventMatrixProc[i][k] = eventMatrixProc[i][jbar];
        eventMatrixProc[i][jbar] = sigma;
      }
    }  // end column interchange

    // now store in sigma the squared sum of the readoutEnergies for this column(crystal)
    sigma = 0.;
    for (i = k; i < Nevents; i++) {
      sigma += eventMatrixProc[i][k] * eventMatrixProc[i][k];
    }

    // found a zero-column, bail out
    if (sigma == 0.) {
      //      std::cout << "Householder::decompose() failed" << std::endl;
      //      return false;
      // rof 14.12.2006: workaround to avoid failure of algorithm because of dead crystals:
      sigma = sigmaReplacement;
      //      std::cout << "Householder::decompose - found zero column " << jbar << ", replacing sum of column elements by " << sigma << std::endl;
    }

    // the following paragraph acts only on the diagonal element:
    // if element=0, then calculate alpha & beta

    // take the diagonal element
    eventMatrixkk = eventMatrixProc[k][k];

    if (eventMatrixkk < 0.)
      alpha[k] = sqrt(sigma);
    else
      alpha[k] = sqrt(sigma) * (-1.);

    alphak = alpha[k];

    beta = 1 / (sigma - eventMatrixkk * alphak);
    // replace it
    eventMatrixProc[k][k] = eventMatrixkk - alphak;

    for (j = k + 1; j < Nchannels; j++) {
      y[j] = 0.;

      for (i = k; i < Nevents; i++) {
        y[j] += eventMatrixProc[i][k] * eventMatrixProc[i][j];
      }

      y[j] *= beta;
    }

    for (j = k + 1; j < Nchannels; j++) {
      for (i = k; i < Nevents; i++) {
        eventMatrixProc[i][j] -= eventMatrixProc[i][k] * y[j];
        sum[j] -= eventMatrixProc[k][j] * eventMatrixProc[k][j];
      }
    }
  }  // end of kth householder transformation

  //  std::cout << "Householder::decompose() finished" << std::endl;

  return true;
}

void HouseholderDecomposition::solve(std::vector<float>& y) {
  std::vector<float> z(Nchannels, 0.);

  float gamma;
  int i, j;

  //  std::cout << "Householder::solve() begin" << std::endl;

  for (j = 0; j < Nchannels; j++) {
    // apply jth transformation to the right hand side
    gamma = 0.;
    for (i = j; i < Nevents; i++) {
      gamma += eventMatrixProc[i][j] * energyVectorProc[i];
    }
    gamma /= (alpha[j] * eventMatrixProc[j][j]);

    for (i = j; i < Nevents; i++) {
      energyVectorProc[i] += gamma * eventMatrixProc[i][j];
    }
  }

  z[Nchannels - 1] = energyVectorProc[Nchannels - 1] / alpha[Nchannels - 1];

  for (i = Nchannels - 2; i >= 0; i--) {
    z[i] = energyVectorProc[i];
    for (j = i + 1; j < Nchannels; j++) {
      z[i] -= eventMatrixProc[i][j] * z[j];
    }
    z[i] /= alpha[i];
  }

  for (i = 0; i < Nchannels; i++) {
    y[pivot[i]] = z[i];
  }

  //  std::cout << "Householder::solve() finished." << std::endl;
}

std::vector<float> HouseholderDecomposition::recalibrateEvent(const std::vector<float>& eventSquare,
                                                              const int& maxCeta,
                                                              const int& maxCphi,
                                                              const std::vector<float>& recalibrateVector) {
  std::vector<float> newEventSquare(eventSquare);
  int iFull;

  for (int i = 0; i < Nxtals; i++) {
    iFull = indexSqr2Reg(i, maxCeta, maxCphi);
    if (iFull >= 0)
      newEventSquare[i] *= recalibrateVector[iFull];
  }
  return newEventSquare;
}

int HouseholderDecomposition::indexSqr2Reg(const int& sqrIndex, const int& maxCeta, const int& maxCphi) {
  int regionIndex;

  // get the current eta, phi indices
  int curr_eta = maxCeta - squareMode / 2 + sqrIndex % squareMode;
  if (curr_eta * maxCeta <= 0) {
    if (maxCeta > 0)
      curr_eta--;
    else
      curr_eta++;
  }  // JUMP over 0

  int curr_phi = maxCphi - squareMode / 2 + sqrIndex / squareMode;
  if (curr_phi < 1)
    curr_phi += 360;
  if (curr_phi > 360)
    curr_phi -= 360;

  bool negPhiDirection = (maxphi < minphi);
  int iFullphi;

  regionIndex = -1;

  if (curr_eta >= mineta && curr_eta <= maxeta)
    if ((!negPhiDirection && (curr_phi >= minphi && curr_phi <= maxphi)) ||
        (negPhiDirection && !(curr_phi >= minphi && curr_phi <= maxphi))) {
      iFullphi = curr_phi - minphi;
      if (iFullphi < 0)
        iFullphi += 360;
      regionIndex = (curr_eta - mineta) * (maxphi - minphi + 1 + 360 * negPhiDirection) + iFullphi;
    }

  return regionIndex;
}

std::vector<std::vector<float> > HouseholderDecomposition::unzipMatrix(
    const std::vector<std::vector<float> >& eventMatrix,
    const std::vector<int>& VmaxCeta,
    const std::vector<int>& VmaxCphi) {
  std::vector<std::vector<float> > fullMatrix;

  int iFull;

  for (int i = 0; i < Nevents; i++) {
    std::vector<float> foo(Nchannels, 0.);
    for (int k = 0; k < Nxtals; k++) {
      iFull = indexSqr2Reg(k, VmaxCeta[i], VmaxCphi[i]);
      if (iFull >= 0)
        foo[iFull] = eventMatrix[i][k];
    }
    fullMatrix.push_back(foo);
  }

  return fullMatrix;
}

void HouseholderDecomposition::makeRegions(const int& regLength) {
  //  int regFrame = regLength/2;
  int regFrame = squareMode / 2;
  // first eta:
  int remEta = Neta % regLength;
  if (remEta > regLength / 2)
    remEta -= regLength;
  int numSubRegEta = Neta / regLength + (remEta < 0) * 1;

  int addtoEta = remEta / numSubRegEta;
  int addtomoreEta =
      remEta % numSubRegEta;  // add "addtomore" number of times (addto+1), remaining times add just (addto)

  // then phi:
  int remPhi = Nphi % regLength;
  if (remPhi > regLength / 2)
    remPhi -= regLength;
  int numSubRegPhi = Nphi / regLength + (remPhi < 0) * 1;

  int addtoPhi = remPhi / numSubRegPhi;
  int addtomorePhi =
      remPhi % numSubRegPhi;  // add "addtomore" number of times (addto+-1), remaining times add just (addto)

  // now put it all together
  int addedLengthEta = 0;
  int addedLengthPhi = 0;
  int startIndexEta = mineta;
  int startIndexPhi;
  int endIndexEta = 0;
  int endIndexPhi;
  for (int i = 0; i < numSubRegEta; i++) {
    addedLengthEta = regLength + addtoEta + addtomoreEta / abs(addtomoreEta) * (i < abs(addtomoreEta));
    endIndexEta = startIndexEta + addedLengthEta - 1;

    startIndexPhi = minphi;
    endIndexPhi = 0;
    for (int j = 0; j < numSubRegPhi; j++) {
      addedLengthPhi = regLength + addtoPhi + addtomorePhi / abs(addtomorePhi) * (j < abs(addtomorePhi));
      endIndexPhi = startIndexPhi + addedLengthPhi - 1;

      regMinPhi.push_back(startIndexPhi - regFrame * (j != 0));
      regMaxPhi.push_back(endIndexPhi + regFrame * (j != (numSubRegPhi - 1)));
      regMinEta.push_back(startIndexEta - regFrame * (i != 0));
      regMaxEta.push_back(endIndexEta + regFrame * (i != (numSubRegEta - 1)));

      startIndexPhi = endIndexPhi + 1;
    }
    startIndexEta = endIndexEta + 1;
  }

  //  // print it all
  //  std::cout << "Householder::makeRegions created the following regions for calibration:" << std::endl;
  //  for (int i=0; i<regMinEta.size(); i++)
  //    std::cout << "Region " << i << ": eta = " << regMinEta[i] << " to " << regMaxEta[i] << ", phi = " << regMinPhi[i] << " to " << regMaxPhi[i] << std::endl;
}