My Project
Loading...
Searching...
No Matches
Functions
facAlgExt.h File Reference

Univariate factorization over algebraic extension of Q using Trager's algorithm. More...

#include "cf_assert.h"
#include "canonicalform.h"

Go to the source code of this file.

Functions

CFList AlgExtSqrfFactorize (const CanonicalForm &F, const Variable &alpha)
 factorize a univariate squarefree polynomial over algebraic extension of Q More...
 
CFFList AlgExtFactorize (const CanonicalForm &F, const Variable &alpha)
 factorize a univariate polynomial over algebraic extension of Q More...
 

Detailed Description

Univariate factorization over algebraic extension of Q using Trager's algorithm.

Copyright:
(c) by The SINGULAR Team, see LICENSE file
Author
Martin Lee

Definition in file facAlgExt.h.

Function Documentation

◆ AlgExtFactorize()

CFFList AlgExtFactorize ( const CanonicalForm F,
const Variable alpha 
)

factorize a univariate polynomial over algebraic extension of Q

Returns
AlgExtFactorize returns a list of factors of F with multiplicity
Parameters
[in]Fa univariate polynomial
[in]alphaan algebraic variable

Definition at line 370 of file facAlgExt.cc.

371{
372 ASSERT (F.isUnivariate(), "univariate input expected");
373 ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
374
375
376 if (F.inCoeffDomain())
377 return CFFList (CFFactor (F, 1));
378
379 bool save_rat=!isOn (SW_RATIONAL);
380 On (SW_RATIONAL);
381 TIMING_START (fac_alg_sqrf);
382 CFFList sqrf= sqrFreeZ (F);
383 TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
384 CFList factorsSqrf;
385 CFFList factors;
387
388 CanonicalForm lcinv;
389 for (CFFListIterator i= sqrf; i.hasItem(); i++)
390 {
391 if (i.getItem().factor().inCoeffDomain()) continue;
392 TIMING_START (fac_alg_factor_sqrf);
393 factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
394 TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
395 "time to factor sqrf factors in Q(a)[x]: ");
396 for (j= factorsSqrf; j.hasItem(); j++)
397 {
398 lcinv= 1/Lc (j.getItem());
399 factors.append (CFFactor (j.getItem()*lcinv, i.getItem().exp()));
400 }
401 }
402
403 factors.insert (CFFactor (Lc(F), 1));
404 if (save_rat) Off(SW_RATIONAL);
405 return factors;
406}
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
bool isUnivariate() const
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
CFList AlgExtSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate squarefree polynomial over algebraic extension of Q
Definition: facAlgExt.cc:148
const Variable & alpha
Definition: facAlgExt.cc:53
int j
Definition: facHensel.cc:110
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:49
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94

◆ AlgExtSqrfFactorize()

CFList AlgExtSqrfFactorize ( const CanonicalForm F,
const Variable alpha 
)

factorize a univariate squarefree polynomial over algebraic extension of Q

Returns
AlgExtSqrfFactorize returns a list of factors of F
Parameters
[in]Fa univariate squarefree polynomial
[in]alphaan algebraic variable

Definition at line 148 of file facAlgExt.cc.

149{
150 ASSERT (F.isUnivariate(), "univariate input expected");
151 ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
152
153 bool save_rat=!isOn (SW_RATIONAL);
154 On (SW_RATIONAL);
156 Variable y= f.mvar();
157 int shift= 0, k= 0, count= 0;
159 CFFList normFactors;
160 bool save_sort= !isOn (SW_USE_NTL_SORT);
161 CFList factors, tmp, tmp2;
164 bool shiftBuf= false;
165
166 tmp.append (f);
167 do
168 {
169 tmp2= CFList();
170 for (iter= tmp; iter.hasItem(); iter++)
171 {
172 oldF= iter.getItem()*bCommonDen (iter.getItem());
173 if (shift == 0)
174 f= oldF;
175 else
176 {
177 f= oldF (y - shift*alpha, y);
178 f *= bCommonDen (f);
179 }
180 TIMING_START (fac_alg_norm);
181 norm= Norm (f, alpha);
182 TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
183 ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
184
185 TIMING_START (fac_alg_factor_norm);
187 normFactors= factorize (norm);
188 if (save_sort)
190 TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
191
192 if (normFactors.getFirst().factor().inCoeffDomain())
193 normFactors.removeFirst();
194 if (normFactors.length() < 2 && normFactors.getLast().exp() == 1)
195 {
196 factors.append (oldF);
197 continue;
198 }
199
200 i= normFactors;
201 shiftBuf= false;
202 if (!(normFactors.length() == 2 &&
203 degree (i.getItem().factor()) <= degree (f)))
204 {
205 TIMING_START (fac_alg_time_shift);
206 if (shift != 0)
207 buf= f;
208 else
209 buf= oldF;
210 shiftBuf= true;
211 TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
212 }
213 else
214 buf= oldF;
215
216 count= 0;
217 for (; i.hasItem(); i++)
218 {
219 TIMING_START (fac_alg_gcd);
220 if (shiftBuf)
221 factor= gcd (buf, i.getItem().factor());
222 else
223 {
224 if (shift == 0)
225 factor= gcd (buf, i.getItem().factor());
226 else
227 factor= gcd (buf, i.getItem().factor() (y + shift*alpha, y));
228 }
229 buf /= factor;
230 if (shiftBuf)
231 {
232 if (shift != 0)
233 factor= factor (y + shift*alpha, y);
234 }
235 TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
236 if (i.getItem().exp() == 1 || degree (factor) == 1)
237 factors.append (factor);
238 else
240 if (buf.inCoeffDomain())
241 break;
242 count++;
243 if (normFactors.length() - 1 == count)
244 {
245 if (shiftBuf)
246 {
247 if (normFactors.getLast().exp() == 1)
248 factors.append (buf (y + shift*alpha, y));
249 else
250 tmp2.append (buf (y + shift*alpha, y));
251 }
252 else
253 {
254 if (normFactors.getLast().exp() == 1)
255 factors.append (buf);
256 else
257 tmp2.append (buf);
258 }
259 buf= 1;
260 break;
261 }
262 }
263 }
264 k++;
265 if (shift == 0)
266 {
267 shift++;
268 k= 1;
269 }
270 if (k == 2)
271 shift= -shift;
272 if (k == 3)
273 {
274 shift= -shift;
275 shift++;
276 k= 1;
277 }
278 tmp= tmp2;
279 }
280 while (!tmp.isEmpty());
281
282 if (save_rat) Off(SW_RATIONAL);
283 return factors;
284}
int degree(const CanonicalForm &f)
List< CanonicalForm > CFList
int k
Definition: cfEzgcd.cc:99
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:39
FILE * f
Definition: checklibs.c:9
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
T getLast() const
Definition: ftmpl_list.cc:309
int isEmpty() const
Definition: ftmpl_list.cc:267
factory's class for variables
Definition: variable.h:33
CFFListIterator iter
Definition: facAbsBiFact.cc:53
CanonicalForm factor
Definition: facAbsFact.cc:97
mipo *CanonicalForm norm
Definition: facAlgExt.cc:61
Variable y
Definition: facAlgExt.cc:55
CFList tmp2
Definition: facFqBivar.cc:72
int status int void size_t count
Definition: si_signals.h:59
int status int void * buf
Definition: si_signals.h:59
int gcd(int a, int b)
Definition: walkSupport.cc:836