source: git/factory/facAbsFact.h @ 712a5a

jengelh-datetimespielwiese
Last change on this file since 712a5a was 712a5a, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: include issues
  • 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
89CFAFList absFactorize (const CanonicalForm& G);
90
91/*ENDPUBLIC*/
92
93/// absolute factorization of bivariate poly over Q
94///
95/// @return absFactorize returns a list whose entries contain three entities:
96///         an absolute irreducible factor, an irreducible univariate polynomial
97///         that defines the minimal field extension over which the irreducible
98///         factor is defined and the multiplicity of the absolute irreducible
99///         factor
100CFAFList absFactorize (const CanonicalForm& G ///<[in] bivariate poly over Q
101                      )
102{
103  //TODO handle homogeneous input
104  ASSERT (getNumVars (F) == 2, "expected bivariate input");
105  ASSERT (getCharacteristic() == 0 && isOn (SW_RATIONAL),
106          "expected poly over Q");
107
108  CFMap N;
109  CanonicalForm F= compress (G, N);
110  bool isRat= isOn (SW_RATIONAL);
111  if (isRat)
112    F *= bCommonDen (F);
113
114  Off (SW_RATIONAL);
115  F /= icontent (F);
116  if (isRat)
117    On (SW_RATIONAL);
118
119  CanonicalForm contentX= content (F, 1);
120  CanonicalForm contentY= content (F, 2);
121  F /= (contentX*contentY);
122  CFAFList contentXFactors, contentYFactors;
123  contentXFactors= uniAbsFactorize (contentX);
124  contentYFactors= uniAbsFactorize (contentY);
125
126  if (contentXFactors.getFirst().factor().inCoeffDomain())
127    contentXFactors.removeFirst();
128  if (contentYFactors.getFirst().factor().inCoeffDomain())
129    contentYFactors.removeFirst();
130  if (F.inCoeffDomain())
131  {
132    CFAFList result;
133    for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
134      result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
135                                i.getItem().exp()));
136    for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
137      result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(),
138                                i.getItem().exp()));
139    normalize (result);
140    result.insert (CFAFactor (Lc (G), 1, 1));
141    return result;
142  }
143  CFFList rationalFactors= factorize (F);
144
145  CFAFList result, resultBuf;
146
147  CFAFListIterator iter;
148  CFFListIterator i= rationalFactors;
149  i++;
150  for (; i.hasItem(); i++)
151  {
152    resultBuf= absFactorizeMain (i.getItem().factor());
153    for (iter= resultBuf; iter.hasItem(); iter++)
154      iter.getItem()= CFAFactor (iter.getItem().factor(),
155                                 iter.getItem().minpoly(), i.getItem().exp());
156    result= Union (result, resultBuf);
157  }
158
159  for (CFAFListIterator i= result; i.hasItem(); i++)
160    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
161                            i.getItem().exp());
162  for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
163    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
164                              i.getItem().exp()));
165  for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
166    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
167                              i.getItem().exp()));
168  normalize (result);
169  result.insert (CFAFactor (Lc(G), 1, 1));
170
171  return result;
172}
173
174#endif
Note: See TracBrowser for help on using the repository browser.