source: git/factory/facAbsFact.h @ efd410

fieker-DuValspielwiese
Last change on this file since efd410 was efd410, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: top level abs factorization interface
  • Property mode set to 100644
File size: 3.9 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 "assert.h"
18
19#include "canonicalform.h"
20#include "cf_map.h"
21#include "cfNewtonPolygon.h"
22
23CFAFList absFactorizeMain (const CanonicalForm& F);
24
25static inline
26void normalize (CFAFList & L)
27{
28  for (CFAFListIterator i= L; i.hasItem(); i++)
29    i.getItem()= CFAFactor (i.getItem().factor()/Lc (i.getItem().factor()),
30                            i.getItem().minpoly(), i.getItem().exp());
31}
32
33static inline
34CFAFList uniAbsFactorize (const CanonicalForm& F)
35{
36  CFFList rationalFactors= factorize (F);
37  CFFListIterator i= rationalFactors;
38  i++;
39  CanonicalForm mipo;
40  CFAFList result;
41  for (; i.hasItem(); i++)
42  {
43    mipo= rootOf (i.getItem().factor());
44    result.append (CFAFactor (i.getItem().factor(), mipo, i.getItem().exp()));
45  }
46  result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1));
47  return result;
48}
49
50/*BEGINPUBLIC*/
51
52CFAFList absFactorize (const CanonicalForm& G);
53
54/*ENDPUBLIC*/
55
56CFAFList absFactorize (const CanonicalForm& G)
57{
58  //TODO handle homogeneous input
59  ASSERT (getNumVars (F) == 2, "expected bivariate input");
60  ASSERT (getCharacteristic() == 0 && isOn (SW_RATIONAL), "expected poly over Q");
61
62  CFMap N;
63  CanonicalForm F= compress (G, N);
64  bool isRat= isOn (SW_RATIONAL);
65  if (isRat)
66  {
67    F *= bCommonDen (F);
68    Off (SW_RATIONAL);
69  }
70  F /= icontent (F);
71  if (isRat)
72    On (SW_RATIONAL);
73
74  CanonicalForm contentX= content (F, 1);
75  CanonicalForm contentY= content (F, 2);
76  F /= (contentX*contentY);
77  CFAFList contentXFactors, contentYFactors;
78  contentXFactors= uniAbsFactorize (contentX);
79  contentYFactors= uniAbsFactorize (contentY);
80
81  if (contentXFactors.getFirst().factor().inCoeffDomain())
82    contentXFactors.removeFirst();
83  if (contentYFactors.getFirst().factor().inCoeffDomain())
84    contentYFactors.removeFirst();
85  if (F.inCoeffDomain())
86  {
87    CFAFList result;
88    for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
89      result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
90                                i.getItem().exp()));
91    for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
92      result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(),
93                                i.getItem().exp()));
94    normalize (result);
95    result.insert (CFAFactor (Lc (G), 1, 1));
96    return result;
97  }
98  CFFList rationalFactors= factorize (F);
99
100  CFAFList result, resultBuf;
101
102  CFAFListIterator iter;
103  CFFListIterator i= rationalFactors;
104  i++;
105  for (; i.hasItem(); i++)
106  {
107    resultBuf= absFactorizeMain (i.getItem().factor());
108    for (iter= resultBuf; iter.hasItem(); iter++)
109      iter.getItem()= CFAFactor (iter.getItem().factor(),
110                                 iter.getItem().minpoly(), i.getItem().exp());
111    result= Union (result, resultBuf);
112  }
113
114
115  for (CFAFListIterator i= result; i.hasItem(); i++)
116    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
117                            i.getItem().exp());
118  for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
119    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
120                              i.getItem().exp()));
121  for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
122    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
123                              i.getItem().exp()));
124  normalize (result);
125  result.insert (CFAFactor (Lc(G), 1, 1));
126  return result;
127}
128
129#endif
Note: See TracBrowser for help on using the repository browser.