source: git/factory/facAlgExt.cc @ 72bfc8

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