source: git/factory/facAbsFact.h @ e4e36c

jengelh-datetimespielwiese
Last change on this file since e4e36c was e4e36c, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: in case there is no FLINT use NTL
  • Property mode set to 100644
File size: 5.8 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facAbsFact.h
5 *
6 * bivariate absolute factorization over Q described in "Modular Las Vegas
7 * Algorithms for Polynomial Absolute Factorization" by Bertone, ChÚze, Galligo
8 *
9 * @author Martin Lee
10 *
11 **/
12/*****************************************************************************/
13
14#ifndef FAC_ABS_FACT_H
15#define FAC_ABS_FACT_H
16
17#include "cf_assert.h"
18
19#include "cf_algorithm.h"
20#include "cf_map.h"
21
22/// main absolute factorization routine, expects bivariate poly which is
23/// primitive wrt. any of its variables and irreducible over Q
24///
25/// @return absFactorizeMain returns a list whose entries contain three entities:
26///         an absolute irreducible factor, an irreducible univariate polynomial
27///         that defines the minimal field extension over which the irreducible
28///         factor is defined and the multiplicity of the absolute irreducible
29///         factor
30CFAFList absFactorizeMain (const CanonicalForm& F ///<[in] s.a.
31                          );
32
33
34/// normalize factors, i.e. make factors monic
35static inline
36void normalize (CFAFList & L)
37{
38  for (CFAFListIterator i= L; i.hasItem(); i++)
39    i.getItem()= CFAFactor (i.getItem().factor()/Lc (i.getItem().factor()),
40                            i.getItem().minpoly(), i.getItem().exp());
41}
42
43/// univariate absolute factorization over Q
44///
45/// @return uniAbsFactorize returns a list whose entries contain three entities:
46///         an absolute irreducible factor, an irreducible univariate polynomial
47///         that defines the minimal field extension over which the irreducible
48///         factor is defined and the multiplicity of the absolute irreducible
49///         factor
50static inline
51CFAFList uniAbsFactorize (const CanonicalForm& F ///<[in] univariate poly over Q
52                         )
53{
54  CFFList rationalFactors= factorize (F);
55  CFFListIterator i= rationalFactors;
56  i++;
57  Variable alpha;
58  CFAFList result;
59  CFFList QaFactors;
60  CFFListIterator iter;
61  for (; i.hasItem(); i++)
62  {
63    if (degree (i.getItem().factor()) == 1)
64    {
65      result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp()));
66      continue;
67    }
68    alpha= rootOf (i.getItem().factor());
69    QaFactors= factorize (i.getItem().factor(), alpha);
70    iter= QaFactors;
71    if (iter.getItem().factor().inCoeffDomain())
72      iter++;
73    for (;iter.hasItem(); iter++)
74    {
75      if (degree (iter.getItem().factor()) == 1)
76      {
77        result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
78                                  i.getItem().exp()));
79        break;
80      }
81    }
82  }
83  result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1));
84  return result;
85}
86
87/*BEGINPUBLIC*/
88
89#ifdef HAVE_NTL
90CFAFList absFactorize (const CanonicalForm& G);
91#endif
92
93/*ENDPUBLIC*/
94
95/// absolute factorization of bivariate poly over Q
96///
97/// @return absFactorize returns a list whose entries contain three entities:
98///         an absolute irreducible factor, an irreducible univariate polynomial
99///         that defines the minimal field extension over which the irreducible
100///         factor is defined and the multiplicity of the absolute irreducible
101///         factor
102CFAFList absFactorize (const CanonicalForm& G ///<[in] bivariate poly over Q
103                      )
104{
105  //TODO handle homogeneous input
106  ASSERT (getNumVars (F) == 2, "expected bivariate input");
107  ASSERT (getCharacteristic() == 0 && isOn (SW_RATIONAL),
108          "expected poly over Q");
109
110  CFMap N;
111  CanonicalForm F= compress (G, N);
112  bool isRat= isOn (SW_RATIONAL);
113  if (isRat)
114    F *= bCommonDen (F);
115
116  Off (SW_RATIONAL);
117  F /= icontent (F);
118  if (isRat)
119    On (SW_RATIONAL);
120
121  CanonicalForm contentX= content (F, 1);
122  CanonicalForm contentY= content (F, 2);
123  F /= (contentX*contentY);
124  CFAFList contentXFactors, contentYFactors;
125  contentXFactors= uniAbsFactorize (contentX);
126  contentYFactors= uniAbsFactorize (contentY);
127
128  if (contentXFactors.getFirst().factor().inCoeffDomain())
129    contentXFactors.removeFirst();
130  if (contentYFactors.getFirst().factor().inCoeffDomain())
131    contentYFactors.removeFirst();
132  if (F.inCoeffDomain())
133  {
134    CFAFList result;
135    for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
136      result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
137                                i.getItem().exp()));
138    for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
139      result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(),
140                                i.getItem().exp()));
141    normalize (result);
142    result.insert (CFAFactor (Lc (G), 1, 1));
143    return result;
144  }
145  CFFList rationalFactors= factorize (F);
146
147  CFAFList result, resultBuf;
148
149  CFAFListIterator iter;
150  CFFListIterator i= rationalFactors;
151  i++;
152  for (; i.hasItem(); i++)
153  {
154    resultBuf= absFactorizeMain (i.getItem().factor());
155    for (iter= resultBuf; iter.hasItem(); iter++)
156      iter.getItem()= CFAFactor (iter.getItem().factor(),
157                                 iter.getItem().minpoly(), i.getItem().exp());
158    result= Union (result, resultBuf);
159  }
160
161  for (CFAFListIterator i= result; i.hasItem(); i++)
162    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
163                            i.getItem().exp());
164  for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
165    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
166                              i.getItem().exp()));
167  for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
168    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
169                              i.getItem().exp()));
170  normalize (result);
171  result.insert (CFAFactor (Lc(G), 1, 1));
172
173  return result;
174}
175
176#endif
Note: See TracBrowser for help on using the repository browser.