source: git/factory/facAlgExt.cc @ e4fe2b

spielwiese
Last change on this file since e4fe2b was e4fe2b, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
FIX: Fixed huge BUG in cf_gmp.h CHG: starting to cleanup factory
  • Property mode set to 100644
File size: 4.2 KB
RevLine 
[59a7ca1]1// -*- c++ -*-
2//*****************************************************************************
3/** @file facAlgExt.cc
4 *
5 * @author Martin Lee
[806c18]6 * @date
[59a7ca1]7 *
[1b38e5d]8 * Univariate factorization over algebraic extension of Q using Trager's
9 * algorithm
[59a7ca1]10 *
11 * @par Copyright:
12 *   (c) by The SINGULAR Team, see LICENSE file
13 *
[806c18]14 * @internal
[59a7ca1]15 * @version \$Id$
16 *
17**/
18//*****************************************************************************
19
[e4fe2b]20#include "config.h"
[59a7ca1]21
[650f2d8]22#include "cf_assert.h"
[59a7ca1]23#include "debug.h"
24#include "timing.h"
25
26#include "canonicalform.h"
27#include "cf_random.h"
28#include "cf_algorithm.h"
29#include "facFqBivarUtil.h"
30#include "facAlgExt.h"
[35eb6c]31#include "cfModResultant.h"
[59a7ca1]32
[1b38e5d]33// squarefree part of F
[59a7ca1]34CanonicalForm
[35eb6c]35uniSqrfPart (const CanonicalForm& F)
[59a7ca1]36{
37  ASSERT (F.isUnivariate(), "univariate input expected");
38  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
39  CanonicalForm G= deriv (F, F.mvar());
40  G= gcd (F, G);
[806c18]41  return F/G;
[59a7ca1]42}
43
[1b38e5d]44// i is an integer such that Norm (F (x-i*alpha)) is squarefree
[59a7ca1]45CanonicalForm sqrfNorm (const CanonicalForm& F, const Variable& alpha, int& i)
46{
47  Variable x= Variable (F.level() + 1);
48  Variable y= F.mvar();
49  CanonicalForm g= F (x, alpha);
50  CanonicalForm mipo= getMipo (alpha);
51  mipo= mipo (x, alpha);
[50a2aa9]52  mipo *= bCommonDen (mipo);
[806c18]53
[35eb6c]54  int degg= degree (g);
55  int degmipo= degree (mipo);
56  CanonicalForm norm;
57  if (degg >= 8 || degmipo >= 8)
58    norm= resultantZ (g, mipo, x);
59  else
60    norm= resultant (g, mipo, x);
61
[59a7ca1]62  i= 0;
63  int k;
64  if (degree (gcd (deriv (norm, y), norm)) <= 0)
65    return norm;
66  i= 1;
67  do
68  {
69    k= 1;
70    while (k < 3)
71    {
72      if (k == 1)
73      {
74        g= F (y - i*alpha, y);
[50a2aa9]75        g *= bCommonDen (g);
[35eb6c]76        if (degg >= 8 || degmipo >= 8)
77          norm= resultantZ (g (x, alpha), mipo, x);
78        else
79          norm= resultant (g (x, alpha), mipo, x);
[59a7ca1]80      }
81      else
82      {
83        g= F (y + i*alpha, y);
[50a2aa9]84        g *= bCommonDen (g);
[35eb6c]85        if (degg >= 8 || degmipo >= 8)
86          norm= resultantZ (g (x, alpha), mipo, x);
87        else
88          norm= resultant (g (x, alpha), mipo, x);
[59a7ca1]89      }
90      if (degree (gcd (deriv (norm, y), norm)) <= 0)
91      {
92        if (k == 2)
93          i= -i;
94        return norm;
95      }
96      k++;
97    }
98    i++;
99  } while (1);
100}
101
102CFList
103AlgExtSqrfFactorize (const CanonicalForm& F, const Variable& alpha)
104{
105  ASSERT (F.isUnivariate(), "univariate input expected");
106  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
[806c18]107
[9fd0b1]108  bool save_rat=!isOn (SW_RATIONAL);
109  On (SW_RATIONAL);
[35eb6c]110  CanonicalForm f= F*bCommonDen (F);
[59a7ca1]111  int shift;
112  CanonicalForm norm= sqrfNorm (f, alpha, shift);
113  ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
[50a2aa9]114  CFFList normFactors= factorize (norm);
[59a7ca1]115  CFList factors;
116  if (normFactors.length() <= 2)
[9fd0b1]117  {
118    if (save_rat) Off(SW_RATIONAL);
[35eb6c]119    return CFList (F);
[9fd0b1]120  }
[806c18]121
[59a7ca1]122  normFactors.removeFirst();
123  CanonicalForm buf;
124  if (shift != 0)
125    buf= f (f.mvar() - shift*alpha, f.mvar());
126  else
[806c18]127    buf= f;
[59a7ca1]128  CanonicalForm factor;
129  for (CFFListIterator i= normFactors; i.hasItem(); i++)
130  {
131    ASSERT (i.getItem().exp() == 1, "norm not squarefree");
132    factor= gcd (buf, i.getItem().factor());
133    buf /= factor;
134    if (shift != 0)
[806c18]135      factor= factor (f.mvar() + shift*alpha, f.mvar());
[59a7ca1]136    factors.append (factor);
[806c18]137  }
[59a7ca1]138  ASSERT (degree (buf) <= 0, "incomplete factorization");
[9fd0b1]139  if (save_rat) Off(SW_RATIONAL);
[59a7ca1]140  return factors;
141}
142
[806c18]143CFFList
[59a7ca1]144AlgExtFactorize (const CanonicalForm& F, const Variable& alpha)
145{
146  ASSERT (F.isUnivariate(), "univariate input expected");
147  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
[806c18]148
[35eb6c]149
[59a7ca1]150  if (F.inCoeffDomain())
151    return CFFList (CFFactor (F, 1));
152
[50a2aa9]153  bool save_rat=!isOn (SW_RATIONAL);
154  On (SW_RATIONAL);
[5f9b47]155  CFFList sqrf= sqrFreeZ (F);
156  CFList factorsSqrf;
[59a7ca1]157  CFFList factors;
[5f9b47]158  CFListIterator j;
159
160  for (CFFListIterator i= sqrf; i.hasItem(); i++)
[59a7ca1]161  {
[5f9b47]162    if (i.getItem().factor().inCoeffDomain()) continue;
163    factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
164    for (j= factorsSqrf; j.hasItem(); j++)
165      factors.append (CFFactor (j.getItem()/Lc (j.getItem()), i.getItem().exp()));
[806c18]166  }
[5f9b47]167
[59a7ca1]168  factors.insert (CFFactor (Lc(F), 1));
169  ASSERT (degree (buf) <= 0, "bug in AlgExtFactorize");
[50a2aa9]170  if (save_rat) Off(SW_RATIONAL);
[806c18]171  return factors;
[59a7ca1]172}
173
Note: See TracBrowser for help on using the repository browser.