facAlgExt.h File Reference

Univariate factorization over algebraic extension of Q using Trager's algorithm. More...

#include "cf_assert.h"
#include "canonicalform.h"

Go to the source code of this file.

Functions
CFList	AlgExtSqrfFactorize (const CanonicalForm &F, const Variable &alpha)
	factorize a univariate squarefree polynomial over algebraic extension of Q More...
CFFList	AlgExtFactorize (const CanonicalForm &F, const Variable &alpha)
	factorize a univariate polynomial over algebraic extension of Q More...

Detailed Description

Univariate factorization over algebraic extension of Q using Trager's algorithm.

Copyright:

(c) by The SINGULAR Team, see LICENSE file

Author

Martin Lee

Definition in file facAlgExt.h.

Function Documentation

AlgExtFactorize()

CFFList AlgExtFactorize	(	const CanonicalForm &	F,
		const Variable &	alpha
	)

factorize a univariate polynomial over algebraic extension of Q

Returns

AlgExtFactorize returns a list of factors of F with multiplicity

Parameters

[in]	F	a univariate polynomial
[in]	alpha	an algebraic variable

Definition at line 370 of file facAlgExt.cc.

{
  ASSERT (F.isUnivariate(), "univariate input expected");
  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
 
 
  if (F.inCoeffDomain())
    return CFFList (CFFactor (F, 1));
 
  bool save_rat=!isOn (SW_RATIONAL);
  On (SW_RATIONAL);
  TIMING_START (fac_alg_sqrf);
  CFFList sqrf= sqrFreeZ (F);
  TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
  CFList factorsSqrf;
  CFFList factors;
  CFListIterator j;
 
  CanonicalForm lcinv;
  for (CFFListIterator i= sqrf; i.hasItem(); i++)
  {
    if (i.getItem().factor().inCoeffDomain()) continue;
    TIMING_START (fac_alg_factor_sqrf);
    factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
    TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
                          "time to factor sqrf factors in Q(a)[x]: ");
    for (j= factorsSqrf; j.hasItem(); j++)
    {
      lcinv= 1/Lc (j.getItem());
      factors.append (CFFactor (j.getItem()*lcinv, i.getItem().exp()));
    }
  }
 
  factors.insert (CFFactor (Lc(F), 1));
  if (save_rat) Off(SW_RATIONAL);
  return factors;
}

AlgExtSqrfFactorize()

CFList AlgExtSqrfFactorize	(	const CanonicalForm &	F,
		const Variable &	alpha
	)

factorize a univariate squarefree polynomial over algebraic extension of Q

Returns

AlgExtSqrfFactorize returns a list of factors of F

Parameters

[in]	F	a univariate squarefree polynomial
[in]	alpha	an algebraic variable

Definition at line 148 of file facAlgExt.cc.

{
  ASSERT (F.isUnivariate(), "univariate input expected");
  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
 
  bool save_rat=!isOn (SW_RATIONAL);
  On (SW_RATIONAL);
  CanonicalForm f= F*bCommonDen (F);
  Variable y= f.mvar();
  int shift= 0, k= 0, count= 0;
  CanonicalForm norm, buf, factor, oldF;
  CFFList normFactors;
  bool save_sort= !isOn (SW_USE_NTL_SORT);
  CFList factors, tmp, tmp2;
  CFFListIterator i;
  CFListIterator iter;
  bool shiftBuf= false;
 
  tmp.append (f);
  do
  {
    tmp2= CFList();
    for (iter= tmp; iter.hasItem(); iter++)
    {
      oldF= iter.getItem()*bCommonDen (iter.getItem());
      if (shift == 0)
        f= oldF;
      else
      {
        f= oldF (y - shift*alpha, y);
        f *= bCommonDen (f);
      }
      TIMING_START (fac_alg_norm);
      norm= Norm (f, alpha);
      TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
      ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
 
      TIMING_START (fac_alg_factor_norm);
      On (SW_USE_NTL_SORT);
      normFactors= factorize (norm);
      if (save_sort)
        Off (SW_USE_NTL_SORT);
      TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
 
      if (normFactors.getFirst().factor().inCoeffDomain())
        normFactors.removeFirst();
      if (normFactors.length() < 2 && normFactors.getLast().exp() == 1)
      {
        factors.append (oldF);
        continue;
      }
 
      i= normFactors;
      shiftBuf= false;
      if (!(normFactors.length() == 2 &&
            degree (i.getItem().factor()) <= degree (f)))
      {
        TIMING_START (fac_alg_time_shift);
        if (shift != 0)
          buf= f;
        else
          buf= oldF;
        shiftBuf= true;
        TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
      }
      else
        buf= oldF;
 
      count= 0;
      for (; i.hasItem(); i++)
      {
        TIMING_START (fac_alg_gcd);
        if (shiftBuf)
          factor= gcd (buf, i.getItem().factor());
        else
        {
          if (shift == 0)
            factor= gcd (buf, i.getItem().factor());
          else
            factor= gcd (buf, i.getItem().factor() (y + shift*alpha, y));
        }
        buf /= factor;
        if (shiftBuf)
        {
          if (shift != 0)
            factor= factor (y + shift*alpha, y);
        }
        TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
        if (i.getItem().exp() == 1 || degree (factor) == 1)
          factors.append (factor);
        else
          tmp2.append (factor);
        if (buf.inCoeffDomain())
          break;
        count++;
        if (normFactors.length() - 1 == count)
        {
          if (shiftBuf)
          {
            if (normFactors.getLast().exp() == 1)
              factors.append (buf (y + shift*alpha, y));
            else
              tmp2.append (buf (y + shift*alpha, y));
          }
          else
          {
            if (normFactors.getLast().exp() == 1)
              factors.append (buf);
            else
              tmp2.append (buf);
          }
          buf= 1;
          break;
        }
      }
    }
    k++;
    if (shift == 0)
    {
      shift++;
      k= 1;
    }
    if (k == 2)
      shift= -shift;
    if (k == 3)
    {
      shift= -shift;
      shift++;
      k= 1;
    }
    tmp= tmp2;
  }
  while (!tmp.isEmpty());
 
  if (save_rat) Off(SW_RATIONAL);
  return factors;
}