source: git/factory/facAlgExt.cc @ 1ddcde9

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