source: git/factory/facAbsFact.h @ 592154

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