source: git/factory/facAbsFact.h @ 81626e

jengelh-datetimespielwiese
Last change on this file since 81626e was 81626e, checked in by Martin Lee <martinlee84@…>, 10 years ago
fix: check in assert
  • 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 (G) <= 2, "expected bivariate input");
107  ASSERT (getCharacteristic() == 0, "expected poly over Q");
108
109  CFMap N;
110  CanonicalForm F= compress (G, N);
111  bool isRat= isOn (SW_RATIONAL);
112  if (isRat)
113    F *= bCommonDen (F);
114
115  Off (SW_RATIONAL);
116  F /= icontent (F);
117  if (isRat)
118    On (SW_RATIONAL);
119
120  CanonicalForm contentX= content (F, 1);
121  CanonicalForm contentY= content (F, 2);
122  F /= (contentX*contentY);
123  CFAFList contentXFactors, contentYFactors;
124  contentXFactors= uniAbsFactorize (contentX);
125  contentYFactors= uniAbsFactorize (contentY);
126
127  if (contentXFactors.getFirst().factor().inCoeffDomain())
128    contentXFactors.removeFirst();
129  if (contentYFactors.getFirst().factor().inCoeffDomain())
130    contentYFactors.removeFirst();
131  if (F.inCoeffDomain())
132  {
133    CFAFList result;
134    for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
135      result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
136                                i.getItem().exp()));
137    for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
138      result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(),
139                                i.getItem().exp()));
140    normalize (result);
141    result.insert (CFAFactor (Lc (G), 1, 1));
142    return result;
143  }
144  CFFList rationalFactors= factorize (F);
145
146  CFAFList result, resultBuf;
147
148  CFAFListIterator iter;
149  CFFListIterator i= rationalFactors;
150  i++;
151  for (; i.hasItem(); i++)
152  {
153    resultBuf= absFactorizeMain (i.getItem().factor());
154    for (iter= resultBuf; iter.hasItem(); iter++)
155      iter.getItem()= CFAFactor (iter.getItem().factor(),
156                                 iter.getItem().minpoly(), i.getItem().exp());
157    result= Union (result, resultBuf);
158  }
159
160  for (CFAFListIterator i= result; i.hasItem(); i++)
161    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
162                            i.getItem().exp());
163  for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
164    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
165                              i.getItem().exp()));
166  for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
167    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
168                              i.getItem().exp()));
169  normalize (result);
170  result.insert (CFAFactor (Lc(G), 1, 1));
171
172  return result;
173}
174
175#endif
Note: See TracBrowser for help on using the repository browser.