find_good_divisor()

bool ReducedGB_Field_Local::find_good_divisor ( exponents_t h_exp, int h_comp, int h_deg, int & h_alpha, POLY & result_g, int & result_g_alpha )

protected

Definition at line 181 of file reducedgb-field-local.cpp.

{
  VECTOR(MonomialTable::mon_term *) divisors;
  MonomialTable *ringtable = originalR->get_quotient_MonomialTable();
 
  h_alpha = h_deg - wt->exponents_weight(h_exp, h_comp);
 
  int n0 = (ringtable ? ringtable->find_divisors(-1, h_exp, 1, &divisors) : 0);
  int n1 = T1->find_divisors(-1, h_exp, h_comp, &divisors);
  int n2 = T->find_divisors(-1, h_exp, h_comp, &divisors);
  int n = INTSIZE(divisors);
  if (n == 0) return false;
 
  divisor_info *div_info = newarray(divisor_info, divisors.size());
 
  int next = 0;
 
  // ring divisors
  for (int i = 0; i < n0; i++)
    {
      int id = divisors[i]->_val;
      div_info[next++] = ring_elems[id];
    }
  // new divisors
  for (int i = 0; i < n1; i++)
    {
      int id = divisors[n0 + i]->_val;
      div_info[next++] = new_poly_elems[id];
    }
  // gb divisors
  for (int i = 0; i < n2; i++)
    {
      int id = divisors[n0 + n1 + i]->_val;
      div_info[next++] = gb_elems[id];
    }
 
  if (M2_gbTrace >= 4)
    {
      buffer o;
      o << "\nfind good divisor:";
      if (n0 > 0)
        {
          o << "\n  ndivisors from quotient ring elements " << n0;
          for (int j = 0; j < n0; j++)
            {
              divisor_info &t = div_info[j];
              o << "\n    size " << t.size << " alpha " << t.alpha << " lead ";
              gbvector *f = R->gbvector_lead_term(-1, F, t.g.f);
              R->gbvector_text_out(o, F, f);
              R->gbvector_remove(f);
            }
        }
      if (n1 > 0)
        {
          o << "\n  ndivisors from appended elements " << n1;
          for (int j = 0; j < n1; j++)
            {
              divisor_info &t = div_info[n0 + j];
              o << "\n    size " << t.size << " alpha " << t.alpha << " lead ";
              gbvector *f = R->gbvector_lead_term(-1, F, t.g.f);
              R->gbvector_text_out(o, F, f);
              R->gbvector_remove(f);
            }
        }
      if (n2 > 0)
        {
          o << "\n  ndivisors from gb elements " << n1;
          for (int j = 0; j < n2; j++)
            {
              divisor_info &t = div_info[n0 + n1 + j];
              o << "\n    size " << t.size << " alpha " << t.alpha << " lead ";
              gbvector *f = R->gbvector_lead_term(-1, F, t.g.f);
              R->gbvector_text_out(o, F, f);
              R->gbvector_remove(f);
            }
        }
      emit(o.str());
    }
 
  // Now all of the desired elements are in div_info
  // First, find the minimum alpha value
  int min_alpha = div_info[0].alpha;
  for (int i = 1; i < n; i++)
    if (div_info[i].alpha < min_alpha) min_alpha = div_info[i].alpha;
  result_g_alpha = min_alpha;
 
  int min_size = -1;
  int result_i = -1;
  int nmatches = 0;
  // Now, out of the ones with this alpha, find the minimum size
  for (int i = 0; i < n; i++)
    {
      if (div_info[i].alpha == min_alpha)
        {
          int this_size = div_info[i].size;
          if (min_size < 0 || this_size < min_size)
            {
              min_size = this_size;
              result_i = i;
              nmatches = 1;
            }
          else if (this_size == min_size)
            {
              nmatches++;
            }
        }
    }
 
  if (nmatches > 1 && M2_gbTrace == 3)
    {
      buffer o;
      o << nmatches;
      emit_wrapped(o.str());
    }
 
  // At this point, result_i points to the element we wish to return
  assert(result_i >= 0);
  result_g = div_info[result_i].g;
 
  if (M2_gbTrace >= 4)
    {
      buffer o;
      if (nmatches > 1) o << "\n  nmatches " << n;
      o << "\n  chosen value: ";
      int size = R->gbvector_n_terms(result_g.f);
      o << "\n    size " << size << " alpha " << result_g_alpha << " lead ";
      gbvector *f = R->gbvector_lead_term(-1, F, result_g.f);
      R->gbvector_text_out(o, F, f);
      R->gbvector_remove(f);
      emit(o.str());
    }
 
  return true;
 
#if 0
 
  MonomialTable *ringtable = originalR->get_quotient_MonomialTable();
  if (ringtable)
    {
      n = ringtable->find_divisors(-1, h_exp, 1, &divisors);
 
      if (n > 0)
        {
          POLY p;
          p.fsyz = 0;
          for (int i=0; i<divisors.size(); i++)
            {
              MonomialTable::mon_term *t = divisors[i];
              int id = t->_val;
              p.f = const_cast<gbvector *>(originalR->quotient_gbvector(id));
              int g_alpha = ring_alpha[id];
              if (g_alpha <= h_alpha)
                {
                  result_g = p;
                  result_g_alpha = g_alpha;
                  return true;
                }
              if (min_alpha < 0 || g_alpha < min_alpha)
                {
                  min_alpha = g_alpha;
                  result_g = p;
                  result_g_alpha = g_alpha;
                }
            }
        }
    }
  divisors.clear();
 
  if (M2_gbTrace>=4)
    {
      buffer o;
      o << "\nfind good divisor:";
      emit(o.str());
    }
 
  // check the new polys
  n = T1->find_divisors(-1, h_exp, h_comp, &divisors);
  if (n > 0)
    {
      POLY p;
      if (M2_gbTrace>=4)
        {
          buffer o;
          o << "\n  ndivisors from appended elements " << n;
          for (int j=0; j<n; j++)
            {
              MonomialTable::mon_term *t = divisors[j];
              int id = t->_val;
              p = newpol[id];
              int g_alpha = newpol_alpha[id];
              int size = R->gbvector_n_terms(p.f);
              o << "\n    size " << size << " alpha " << g_alpha << " lead ";
              gbvector *f = R->gbvector_lead_term(-1,F,p.f);
              R->gbvector_text_out(o,F,f);
            }
          emit(o.str());
        }
      for (int i=0; i<divisors.size(); i++)
        {
          MonomialTable::mon_term *t = divisors[i];
          int id = t->_val;
          p = newpol[id];
          int g_alpha = newpol_alpha[id];
          if (result_g_alpha < 0 && g_alpha <= h_alpha)
            {
              result_g = p;
              result_g_alpha = g_alpha;
              min_alpha = g_alpha;
              //break; //return true;
            }
          if (min_alpha < 0 ||  g_alpha < min_alpha)
            {
              min_alpha = g_alpha;
              result_g = p;
              result_g_alpha = g_alpha;
            }
        }
    }
  divisors.clear();
 
  // Now check the GB itself
  n = T->find_divisors(-1, h_exp, h_comp, &divisors);
  if (n > 0)
    {
      POLY p;
      if (M2_gbTrace>=4)
        {
          buffer o;
          o << "\n  ndivisors from GB " << n;
          for (int j=0; j<n; j++)
            {
              MonomialTable::mon_term *t = divisors[j];
              int id = t->_val;
              p = polys[id];
              int g_alpha = alpha[id];
              int size = R->gbvector_n_terms(p.f);
              o << "\n     size " << size << " alpha " << g_alpha << " lead ";
              gbvector *f = R->gbvector_lead_term(-1,F,p.f);
              R->gbvector_text_out(o,F,f);
            }
          emit(o.str());
        }
 
      for (int i=0; i<divisors.size(); i++)
        {
          MonomialTable::mon_term *t = divisors[i];
          int id = t->_val;
          p = polys[id];
          int g_alpha = alpha[id];
          if (result_g_alpha < 0 && g_alpha <= h_alpha)
            {
              result_g = p;
              result_g_alpha = g_alpha;
              min_alpha = g_alpha;
              //break;
              //return true;
            }
          if (min_alpha < 0 || g_alpha < min_alpha)
            {
              min_alpha = g_alpha;
              result_g = p;
              result_g_alpha = g_alpha;
            }
        }
    }
  divisors.clear();
 
 
  if (M2_gbTrace>=4)
    {
      buffer o;
      o << "\n  chosen value: ";
      int size = R->gbvector_n_terms(result_g.f);
      o << "\n    size " << size << " alpha " << result_g_alpha << " lead ";
      gbvector *f = R->gbvector_lead_term(-1,F,result_g.f);
      R->gbvector_text_out(o,F,f);
      R->gbvector_remove(f);
      emit(o.str());
    }
 
  return (min_alpha >= 0);
#endif
}

References MonomialTable::mon_term::_val, ReducedGB_Field_Local::divisor_info::alpha, emit(), emit_wrapped(), ReducedGB::F, POLY::f, MonomialTable::find_divisors(), ReducedGB_Field_Local::divisor_info::g, INTSIZE, M2_gbTrace, newarray, ReducedGB::originalR, p, POLY, ReducedGB::R, ReducedGB_Field_Local::divisor_info::size, buffer::str(), ReducedGB_Field::T, T1, VECTOR, and wt.

Referenced by remainder(), and remainder().