Context Navigation

source: git/factory/facFqFactorize.h @ 6deedd

spielwiese

Last change on this file since 6deedd was 6036d90, checked in by Martin Lee <martinlee84@…>, 12 years ago
added heuristic for sparse lifting and updated tests
Property mode set to `100644`
File size: 23.9 KB

Line
1	/*****************************************************************************\
2	* Computer Algebra System SINGULAR
3	\*****************************************************************************/
4	/** @file facFqFactorize.h
5	*
6	* This file provides functions for factorizing a multivariate polynomial over
7	* \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF.
8	*
9	* @author Martin Lee
10	*
11	* @internal @version \$Id$
12	*
13	**/
14	/*****************************************************************************/
15
16	#ifndef FAC_FQ_FACTORIZE_H
17	#define FAC_FQ_FACTORIZE_H
18
19	// #include "config.h"
20
21	#include "facFqBivar.h"
22	#include "DegreePattern.h"
23	#include "ExtensionInfo.h"
24	#include "cf_util.h"
25	#include "facFqSquarefree.h"
26	#include "facFqBivarUtil.h"
27
28	/// Factorization over a finite field
29	///
30	/// @return @a multiFactorize returns a factorization of F
31	/// @sa biFactorize(), extFactorize()
32	CFList
33	multiFactorize (const CanonicalForm& F, ///< [in] poly to be factored
34	const ExtensionInfo& info ///< [in] info about extension
35	);
36
37	/// factorize a squarefree multivariate polynomial over \f$ F_{p} \f$
38	///
39	/// @return @a FpSqrfFactorize returns a list of monic factors, the first
40	/// element is the leading coefficient.
41	/// @sa FqSqrfFactorize(), GFSqrfFactorize()
42	#ifdef HAVE_NTL
43	inline
44	CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
45	)
46	{
47	if (getNumVars (F) == 2)
48	return FpBiSqrfFactorize (F);
49	ExtensionInfo info= ExtensionInfo (false);
50	CFList result= multiFactorize (F, info);
51	result.insert (Lc(F));
52	return result;
53	}
54
55	/// factorize a squarefree multivariate polynomial over \f$ F_{p} (\alpha ) \f$
56	///
57	/// @return @a FqSqrfFactorize returns a list of monic factors, the first
58	/// element is the leading coefficient.
59	/// @sa FpSqrfFactorize(), GFSqrfFactorize()
60	inline
61	CFList FqSqrfFactorize (const CanonicalForm & F, ///< [in] a multivariate poly
62	const Variable& alpha ///< [in] algebraic variable
63	)
64	{
65	if (getNumVars (F) == 2)
66	return FqBiSqrfFactorize (F, alpha);
67	ExtensionInfo info= ExtensionInfo (alpha, false);
68	CFList result= multiFactorize (F, info);
69	result.insert (Lc(F));
70	return result;
71	}
72
73	/// factorize a squarefree multivariate polynomial over GF
74	///
75	/// @return @a GFSqrfFactorize returns a list of monic factors, the first
76	/// element is the leading coefficient.
77	/// @sa FpSqrfFactorize(), FqSqrfFactorize()
78	inline
79	CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
80	)
81	{
82	ASSERT (CFFactory::gettype() == GaloisFieldDomain,
83	"GF as base field expected");
84	if (getNumVars (F) == 2)
85	return GFBiSqrfFactorize (F);
86	ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
87	CFList result= multiFactorize (F, info);
88	result.insert (Lc(F));
89	return result;
90	}
91
92	/// factorize a multivariate polynomial over \f$ F_{p} \f$
93	///
94	/// @return @a FpFactorize returns a list of monic factors with
95	/// multiplicity, the first element is the leading coefficient.
96	/// @sa FqFactorize(), GFFactorize()
97	inline
98	CFFList FpFactorize (const CanonicalForm& F ///< [in] a multivariate poly
99	)
100	{
101	if (getNumVars (F) == 2)
102	return FpBiFactorize (F);
103	ExtensionInfo info= ExtensionInfo (false);
104	Variable a= Variable (1);
105	CanonicalForm LcF= Lc (F);
106	CanonicalForm pthRoot, A;
107	CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, a);
108	CFList buf, bufRoot;
109	CFFList result, resultRoot;
110	int p= getCharacteristic();
111	int l;
112	if (degree (pthRoot) > 0)
113	{
114	pthRoot= maxpthRoot (pthRoot, p, l);
115	result= FpFactorize (pthRoot);
116	result.removeFirst();
117	for (CFFListIterator i= result; i.hasItem(); i++)
118	i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
119	result.insert (CFFactor (LcF, 1));
120	return result;
121	}
122	else
123	{
124	buf= multiFactorize (sqrfP, info);
125	A= F/LcF;
126	result= multiplicity (A, buf);
127	}
128	if (degree (A) > 0)
129	{
130	resultRoot= FpFactorize (A);
131	resultRoot.removeFirst();
132	result= Union (result, resultRoot);
133	}
134	result.insert (CFFactor (LcF, 1));
135	return result;
136	}
137
138	/// factorize a multivariate polynomial over \f$ F_{p} (\alpha ) \f$
139	///
140	/// @return @a FqFactorize returns a list of monic factors with
141	/// multiplicity, the first element is the leading coefficient.
142	/// @sa FpFactorize(), GFFactorize()
143	inline
144	CFFList FqFactorize (const CanonicalForm& F, ///< [in] a multivariate poly
145	const Variable& alpha ///< [in] algebraic variable
146	)
147	{
148	if (getNumVars (F) == 2)
149	return FqBiFactorize (F, alpha);
150	ExtensionInfo info= ExtensionInfo (alpha, false);
151	CanonicalForm LcF= Lc (F);
152	CanonicalForm pthRoot, A;
153	CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha);
154	CFList buf, bufRoot;
155	CFFList result, resultRoot;
156	int p= getCharacteristic();
157	int q= ipower (p, degree (getMipo (alpha)));
158	int l;
159	if (degree (pthRoot) > 0)
160	{
161	pthRoot= maxpthRoot (pthRoot, q, l);
162	result= FqFactorize (pthRoot, alpha);
163	result.removeFirst();
164	for (CFFListIterator i= result; i.hasItem(); i++)
165	i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
166	result.insert (CFFactor (LcF, 1));
167	return result;
168	}
169	else
170	{
171	buf= multiFactorize (sqrfP, info);
172	A= F/LcF;
173	result= multiplicity (A, buf);
174	}
175	if (degree (A) > 0)
176	{
177	resultRoot= FqFactorize (A, alpha);
178	resultRoot.removeFirst();
179	result= Union (result, resultRoot);
180	}
181	result.insert (CFFactor (LcF, 1));
182	return result;
183	}
184
185	/// factorize a multivariate polynomial over GF
186	///
187	/// @return @a GFFactorize returns a list of monic factors with
188	/// multiplicity, the first element is the leading coefficient.
189	/// @sa FpFactorize(), FqFactorize()
190	inline
191	CFFList GFFactorize (const CanonicalForm& F ///< [in] a multivariate poly
192	)
193	{
194	ASSERT (CFFactory::gettype() == GaloisFieldDomain,
195	"GF as base field expected");
196	if (getNumVars (F) == 2)
197	return GFBiFactorize (F);
198	Variable a= Variable (1);
199	ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
200	CanonicalForm LcF= Lc (F);
201	CanonicalForm pthRoot, A;
202	CanonicalForm sqrfP= sqrfPart (F/LcF, pthRoot, a);
203	CFList buf;
204	CFFList result, resultRoot;
205	int p= getCharacteristic();
206	int q= ipower (p, getGFDegree());
207	int l;
208	if (degree (pthRoot) > 0)
209	{
210	pthRoot= maxpthRoot (pthRoot, q, l);
211	result= GFFactorize (pthRoot);
212	result.removeFirst();
213	for (CFFListIterator i= result; i.hasItem(); i++)
214	i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
215	result.insert (CFFactor (LcF, 1));
216	return result;
217	}
218	else
219	{
220	buf= multiFactorize (sqrfP, info);
221	A= F/LcF;
222	result= multiplicity (A, buf);
223	}
224	if (degree (A) > 0)
225	{
226	resultRoot= GFFactorize (A);
227	resultRoot.removeFirst();
228	result= Union (result, resultRoot);
229	}
230	result.insert (CFFactor (LcF, 1));
231	return result;
232	}
233
234	#endif
235
236	/// Naive factor recombination for multivariate factorization over an extension
237	/// of the initial field. No precomputed is used to exclude combinations.
238	///
239	/// @return @a extFactorRecombination returns a list of factors of @a F, whose
240	/// shift to zero is reversed.
241	/// @sa factorRecombination()
242	CFList
243	extFactorRecombination (
244	const CFList& factors, ///< [in] list of lifted factors
245	///< that are monic wrt Variable (1)
246	const CanonicalForm& F, ///< [in] poly to be factored
247	const CFList& M, ///< [in] a list of powers of
248	///< Variables
249	const ExtensionInfo& info, ///< [in] info about extension
250	const CFList& evaluation ///< [in] evaluation point
251	);
252
253	/// Naive factor recombination for multivariate factorization.
254	/// No precomputed is used to exclude combinations.
255	///
256	/// @return @a factorRecombination returns a list of factors of @a F
257	/// @sa extFactorRecombination()
258	CFList
259	factorRecombination (const CanonicalForm& F,///< [in] poly to be factored
260	const CFList& factors, ///< [in] list of lifted factors
261	///< that are monic wrt Variable (1)
262	const CFList& M ///< [in] a list of powers of
263	///< Variables
264	);
265
266	/// Lift bound adaption. Essentially an early factor detection but only the lift
267	/// bound is adapted.
268	///
269	/// @return @a liftBoundAdaption returns an adapted lift bound.
270	/// @sa earlyFactorDetect(), earlyFactorDetection()
271	int
272	liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly
273	const CFList& factors, ///< [in] list of list of lifted
274	///< factors that are monic wrt
275	///< Variable (1)
276	bool& success, ///< [in,out] indicates that no
277	///< further lifting is necessary
278	const int deg, ///< [in] stage of Hensel lifting
279	const CFList& MOD, ///< [in] a list of powers of
280	///< Variables
281	const int bound ///< [in] initial lift bound
282	);
283
284	/// Lift bound adaption over an extension of the initial field. Essentially an
285	///early factor detection but only the lift bound is adapted.
286	///
287	/// @return @a liftBoundAdaption returns an adapted lift bound.
288	/// @sa earlyFactorDetect(), earlyFactorDetection()
289	int
290	extLiftBoundAdaption (
291	const CanonicalForm& F, ///< [in] a poly
292	const CFList& factors, ///< [in] list of list of lifted
293	///< factors that are monic wrt
294	bool& success, ///< [in,out] indicates that no further
295	///< lifting is necessary
296	const ExtensionInfo& info, ///< [in] info about extension
297	const CFList& eval, ///< [in] evaluation point
298	const int deg, ///< [in] stage of Hensel lifting
299	const CFList& MOD, ///< [in] a list of powers of
300	///< Variables
301	const int bound ///< [in] initial lift bound
302	);
303
304	/// detects factors of @a F at stage @a deg of Hensel lifting.
305	/// No combinations of more than one factor are tested. Lift bound is adapted.
306	///
307	/// @return @a earlyFactorDetect returns a list of factors of F (possibly
308	/// incomplete), in case of success. Otherwise an empty list.
309	/// @sa factorRecombination(), extEarlyFactorDetect()
310	CFList
311	earlyFactorDetect (
312	CanonicalForm& F, ///< [in,out] poly to be factored,
313	///< returns poly divided by detected
314	///< factors in case of success
315	CFList& factors, ///< [in,out] list of factors lifted up
316	///< to @a deg, returns a list of factors
317	///< without detected factors
318	int& adaptedLiftBound, ///< [in,out] adapted lift bound
319	bool& success, ///< [in,out] indicating success
320	const int deg, ///< [in] stage of Hensel lifting
321	const CFList& MOD, ///< [in] a list of powers of
322	///< Variables
323	const int bound ///< [in] initial lift bound
324	);
325
326	/// detects factors of @a F at stage @a deg of Hensel lifting.
327	/// No combinations of more than one factor are tested. Lift bound is adapted.
328	///
329	/// @return @a extEarlyFactorDetect returns a list of factors of F (possibly
330	/// incomplete), whose shift to zero is reversed, in case of success.
331	/// Otherwise an empty list.
332	/// @sa factorRecombination(), earlyFactorDetection()
333	CFList
334	extEarlyFactorDetect (
335	CanonicalForm& F, ///< [in,out] poly to be factored,
336	///< returns poly divided by detected
337	///< factors in case of success
338	CFList& factors, ///< [in,out] list of factors lifted up
339	///< to @a deg, returns a list of factors
340	///< without detected factors
341	int& adaptedLiftBound, ///< [in,out] adapted lift bound
342	bool& success, ///< [in,out] indicating succes
343	const ExtensionInfo& info, ///< [in] info about extension
344	const CFList& eval, ///< [in] evaluation point
345	const int deg, ///< [in] stage of Hensel lifting
346	const CFList& MOD, ///< [in] a list of powers of Variables
347	const int bound ///< [in] initial lift bound
348	);
349
350	/// evaluation point search for multivariate factorization,
351	/// looks for a (F.level() - 1)-tuple such that the resulting univariate
352	/// polynomial has main variable Variable (1), is squarefree and its degree
353	/// coincides with degree(F) and the bivariate one is primitive wrt.
354	/// Variable(1), and successively evaluated polynomials have the same degree in
355	/// their main variable as F has, fails if there are no valid evaluation points,
356	/// eval contains the intermediate evaluated polynomials.
357	///
358	/// @return @a evalPoints returns an evaluation point, which is valid if and
359	/// only if fail == false.
360	CFList
361	evalPoints (const CanonicalForm& F, ///< [in] a compressed poly
362	CFList & eval, ///< [in,out] an empty list, returns @a F
363	///< successive evaluated
364	const Variable& alpha, ///< [in] algebraic variable
365	CFList& list, ///< [in,out] a list of points already
366	///< considered, a point is encoded as a
367	///< poly of degree F.level()-1 in
368	///< Variable(1)
369	const bool& GF, ///< [in] GF?
370	bool& fail ///< [in,out] indicates failure
371	);
372
373	/// hensel Lifting and early factor detection
374	///
375	/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
376	/// factors without factors which have been detected at an early stage
377	/// of Hensel lifting
378	/// @sa earlyFactorDetectn(), extEarlyFactorDetect()
379	CFList
380	henselLiftAndEarly (
381	CanonicalForm& A, ///< [in,out] poly to be factored,
382	///< returns poly divided by detected
383	///< factors, in case of success
384	CFList& MOD, ///< [in,out] a list of powers of
385	///< Variables
386	int*& liftBounds, ///< [in,out] initial lift bounds, returns
387	///< adapted lift bounds
388	bool& earlySuccess, ///< [in,out] indicating success
389	CFList& earlyFactors, ///< [in,out] early factors
390	const CFList& Aeval, ///< [in] @a A successively evaluated at
391	///< elements of @a evaluation
392	const CFList& biFactors, ///< [in] bivariate factors
393	const CFList& evaluation, ///< [in] evaluation point
394	const ExtensionInfo& info ///< [in] info about extension
395	);
396
397	/// Factorization over an extension of initial field
398	///
399	/// @return @a extFactorize returns factorization of F over initial field
400	/// @sa extBiFactorize(), multiFactorize()
401	CFList
402	extFactorize (const CanonicalForm& F, ///< [in] poly to be factored
403	const ExtensionInfo& info ///< [in] info about extension
404	);
405
406	/// compute the LCM of the contents of @a A wrt to each variable occuring in @a
407	/// A.
408	///
409	/// @return @a lcmContent returns the LCM of the contents of @a A wrt to each
410	/// variable occuring in @a A.
411	CanonicalForm
412	lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly
413	CFList& contentAi ///< [in,out] an empty list, returns a list
414	///< of the contents of @a A wrt to each
415	///< variable occuring in @a A starting from
416	///< @a A.mvar().
417	);
418
419	/// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and
420	/// no gaps between the variables occur
421	///
422	/// @return a compressed poly with the above properties
423	CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly
424	CFMap& N ///< [in,out] a map to
425	///< decompress
426	);
427
428	/// evaluate a poly A with main variable at level 1 at an evaluation point in
429	/// K^(n-1) wrt different second variables. If this evaluation is valid (see
430	/// evalPoints) then Aeval contains A successively evaluated at this point,
431	/// otherwise this entry is empty
432	void
433	evaluationWRTDifferentSecondVars (
434	CFList*& Aeval, ///<[in,out] an array of length n-2
435	///< if variable at level i > 2
436	///< admits a valid evaluation
437	///< this entry contains A
438	///< successively evaluated at this
439	///< point otherwise an empty list
440	const CFList& evaluation,///<[in] a valid evaluation point
441	///< for main variable at level 1
442	///< and second variable at level 2
443	const CanonicalForm& A ///<[in] some poly
444	);
445
446	/// evaluate F successively n-2 at 0
447	///
448	/// @return returns a list of successive evaluations of F, ending with F
449	CFList evaluateAtZero (const CanonicalForm& F ///< [in] some poly
450	);
451
452	/// divides factors by their content wrt. Variable(1) and checks if these polys
453	/// divide F
454	///
455	/// @return returns factors of F
456	CFList recoverFactors (const CanonicalForm& F, ///< [in] some poly F
457	const CFList& factors ///< [in] some list of
458	///< factor candidates
459	);
460
461	/// divides factors shifted by evaluation by their content wrt. Variable(1) and
462	/// checks if these polys divide F
463	///
464	/// @return returns factors of F
465	CFList recoverFactors (const CanonicalForm& F, ///< [in] some poly F
466	const CFList& factors, ///< [in] some list of
467	///< factor candidates
468	const CFList& evaluation
469	);
470
471	/// refine a bivariate factorization of A with l factors to one with
472	/// minFactorsLength
473	void
474	refineBiFactors (const CanonicalForm& A, ///< [in] some poly
475	CFList& biFactors, ///< [in,out] list of bivariate to be
476	///< refined, returns refined factors
477	CFList* const& factors, ///< [in] list of bivariate
478	///< factorizations of A wrt different
479	///< second variables
480	const CFList& evaluation,///< [in] the evaluation point
481	int minFactorsLength ///< [in] the minimal number of factors
482	);
483
484	/// plug in evalPoint for y in a list of polys
485	///
486	/// @return returns a list of the evaluated polys, these evaluated polys are
487	/// made monic
488	CFList
489	buildUniFactors (const CFList& biFactors, ///< [in] a list of polys
490	const CanonicalForm& evalPoint,///< [in] some evaluation point
491	const Variable& y ///< [in] some variable
492	);
493
494	/// extract leading coefficients wrt Variable(1) from bivariate factors obtained
495	/// from factorizations of A wrt different second variables
496	void
497	getLeadingCoeffs (const CanonicalForm& A, ///< [in] some poly
498	CFList*& Aeval, ///< [in,out] array of bivariate
499	///< factors, returns the leading
500	///< coefficients of these factors
501	const CFList& uniFactors,///< [in] univariate factors of A
502	const CFList& evaluation ///< [in] evaluation point
503	);
504
505	/// normalize precomputed leading coefficients such that leading coefficients
506	/// evaluated at 0 in K^(n-2) equal the leading coeffs wrt Variable(1) of
507	/// bivariate factors
508	void
509	prepareLeadingCoeffs (CFList*& LCs, ///<[in,out]
510	int n, ///<[in] level of poly to be
511	///< factored
512	const CFList& leadingCoeffs,///<[in] precomputed leading
513	///< coeffs
514	const CFList& biFactors ///<[in] bivariate factors
515	);
516
517	/// obtain factors of F by reconstructing their leading coeffs
518	///
519	/// @return returns the reconstructed factors
520	/// @sa factorRecombination()
521	CFList
522	leadingCoeffReconstruction (const CanonicalForm& F,///<[in] poly to be factored
523	const CFList& factors, ///<[in] factors of f monic
524	///< wrt Variable (1)
525	const CFList& M ///<[in] a list of powers of
526	///< Variables
527	);
528
529	/// distribute content
530	///
531	/// @return returns a list result of polys such that prod (result)= prod (L)
532	/// but the first entry of L may be (partially) factorized and these factors
533	/// are distributed onto other entries in L
534	CFList
535	distributeContent (
536	const CFList& L, ///<[in] list of polys, first
537	///< entry the content to be
538	///< distributed
539	const CFList* differentSecondVarFactors,///<[in] factorization wrt
540	///< different second vars
541	int length ///<[in] length of
542	///<differentSecondVarFactors
543	);
544
545	/// gcd free basis of two lists of factors
546	void
547	gcdFreeBasis (CFFList& factors1, ///< [in,out] list of factors, returns gcd free
548	///< factors
549	CFFList& factors2 ///< [in,out] list of factors, returns gcd free
550	///< factors
551	);
552
553	/// heuristic algorithm for lifting sparse polynomials
554	///
555	/// @return a list of factors of A, possibly incomplete
556	CFList
557	sparseHeuristic (const CanonicalForm& A, ///<[in] polynomial to be factored
558	const CFList& biFactors, ///<[in] list of bivariate factors wrt
559	///< Variable 1 and 2
560	CFList*& moreBiFactors, ///<[in,out] more bivariate factors
561	///< wrt different second variables.
562	///< May be recombined s.t. there are
563	///< only minFactorsLength factors and
564	///< resorted s.t. the sequence of
565	///< univariate factors in biFactors
566	///< and moreBiFactors coincides
567	const CFList& evaluation,///<[in] evaluation point
568	int minFactorsLength ///<[in] minimal number of factors
569	);
570
571	#endif
572	/* FAC_FQ_FACTORIZE_H */
573

Note: See TracBrowser for help on using the repository browser.

Download in other formats: