doLLL()

int LLLoperations::doLLL ( MutableMatrix * A, MutableMatrix * Achange, MutableMatrix * LLLstate, int nsteps = -1 )

staticprivate

Definition at line 241 of file LLL.cpp.

{
  size_t n = A->n_cols();
  if (n == 0) return COMP_DONE;
 
  // Extract the state from LLLstate:
  int k, kmax;
  ring_elem a, alphaTop, alphaBottom;
  buffer o;
 
  if (LLLstate->get_entry(0, n, a))
    {
      std::pair<bool, long> res = globalZZ->coerceToLongInteger(a);
      assert(res.first);
      k = static_cast<int>(res.second);
    }
  else
    k = 0;
 
  if (LLLstate->get_entry(0, n + 1, a))
    {
      std::pair<bool, long> res = globalZZ->coerceToLongInteger(a);
      assert(res.first);
      kmax = static_cast<int>(res.second);
    }
  else
    kmax = 0;
 
  LLLstate->get_entry(0, n + 2, alphaTop);  // Don't free alphaTop!
  LLLstate->get_entry(0, n + 3, alphaBottom);
 
  while (k < n && nsteps != 0 && !system_interrupted())
    {
      if (M2_gbTrace >= 1)
        {
          o.reset();
          o << ".";
          if (M2_gbTrace >= 2) o << k;
          if (nsteps % 20 == 0) o << newline;
          emit(o.str());
        }
      nsteps--;
 
      if (k > kmax)
        {
          if (M2_gbTrace == 1)
            {
              o.reset();
              o << "." << k;
              if (nsteps % 20 == 0) o << newline;
              emit(o.str());
            }
 
          kmax = k;
          for (int j = 0; j <= k; j++)
            {
              ring_elem u;
              A->dot_product(k, j, u);
              for (int i = 0; i <= j - 1; i++)
                {
                  // u = (D#i * u - lambda#(k,i) * lambda#(j,i)) // D#(i-1)
                  ring_elem Di, mki, mji, Di1;
                  LLLstate->get_entry(i, i, Di);
                  globalZZ->mult_to(u, Di);
                  if (LLLstate->get_entry(i, k, mki) &&
                      LLLstate->get_entry(i, j, mji))
                    {
                      ring_elem t1 = globalZZ->mult(mki, mji);
                      globalZZ->subtract_to(u, t1);
                    }
                  if (i > 0)
                    {
                      LLLstate->get_entry(
                          i - 1, i - 1, Di1);  // Cannot be zero!!
                      ring_elem t1 = globalZZ->divide(u, Di1);
                      globalZZ->remove(u);
                      u = t1;
                    }
                }
              // At this point we have our element:
              LLLstate->set_entry(j, k, u);
              if (j == k && globalZZ->is_zero(u))
                {
                  ERROR("LLL vectors not independent");
                  return COMP_ERROR;
                }
            }
        }  // end of the k>kmax initialization
      REDI(k, k - 1, A, Achange, LLLstate);
      if (Lovasz(LLLstate, k, alphaTop, alphaBottom))
        {
          SWAPI(k, kmax, A, Achange, LLLstate);
          k--;
          if (k == 0) k = 1;
        }
      else
        {
          for (int ell = k - 2; ell >= 0; ell--)
            REDI(k, ell, A, Achange, LLLstate);
          k++;
        }
    }
 
  // Before returning, reset k,kmax:
  LLLstate->set_entry(0, n, globalZZ->from_long(k));
  LLLstate->set_entry(0, n + 1, globalZZ->from_long(kmax));
 
  if (k >= n) return COMP_DONE;
  if (nsteps == 0) return COMP_DONE_STEPS;
  return COMP_INTERRUPTED;
}

References COMP_DONE, COMP_DONE_STEPS, COMP_ERROR, COMP_INTERRUPTED, MutableMatrix::dot_product(), emit(), ERROR, MutableMatrix::get_entry(), globalZZ, Lovasz(), M2_gbTrace, MutableMatrix::n_cols(), newline, REDI(), buffer::reset(), MutableMatrix::set_entry(), buffer::str(), SWAPI(), and system_interrupted().

Referenced by LLL().