Context Navigation

source: git/factory/facFqFactorize.h @ 91788c0

spielwiese

Last change on this file since 91788c0 was 91788c0, checked in by Martin Lee <martinlee84@…>, 12 years ago
add: code for sparse heuristic lifting a la Lucks/Wang moved: code for other sparse heuristic to facSparseHensel rm: unused function leadingCoeffReconstruction from facFqFactorize.cc
Property mode set to `100644`
File size: 24.7 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	/// recombination of bivariate factors @a factors1 s. t. the result evaluated
267	/// at @a evalPoint coincides with @a factors2
268	CFList
269	recombination (const CFList& factors1, ///<[in] list of bivariate factors
270	const CFList& factors2, ///<[in] list univariate factors
271	int s, ///<[in] algorithm starts checking
272	///< subsets of size s
273	int thres, ///<[in] threshold for the size of
274	///< subsets which are checked
275	const CanonicalForm& evalPoint,///<[in] evaluation point
276	const Variable& x ///<[in] second variable of
277	///< bivariate factors
278	);
279
280	/// Lift bound adaption. Essentially an early factor detection but only the lift
281	/// bound is adapted.
282	///
283	/// @return @a liftBoundAdaption returns an adapted lift bound.
284	/// @sa earlyFactorDetect(), earlyFactorDetection()
285	int
286	liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly
287	const CFList& factors, ///< [in] list of list of lifted
288	///< factors that are monic wrt
289	///< Variable (1)
290	bool& success, ///< [in,out] indicates that no
291	///< further lifting is necessary
292	const int deg, ///< [in] stage of Hensel lifting
293	const CFList& MOD, ///< [in] a list of powers of
294	///< Variables
295	const int bound ///< [in] initial lift bound
296	);
297
298	/// Lift bound adaption over an extension of the initial field. Essentially an
299	///early factor detection but only the lift bound is adapted.
300	///
301	/// @return @a liftBoundAdaption returns an adapted lift bound.
302	/// @sa earlyFactorDetect(), earlyFactorDetection()
303	int
304	extLiftBoundAdaption (
305	const CanonicalForm& F, ///< [in] a poly
306	const CFList& factors, ///< [in] list of list of lifted
307	///< factors that are monic wrt
308	bool& success, ///< [in,out] indicates that no further
309	///< lifting is necessary
310	const ExtensionInfo& info, ///< [in] info about extension
311	const CFList& eval, ///< [in] evaluation point
312	const int deg, ///< [in] stage of Hensel lifting
313	const CFList& MOD, ///< [in] a list of powers of
314	///< Variables
315	const int bound ///< [in] initial lift bound
316	);
317
318	/// detects factors of @a F at stage @a deg of Hensel lifting.
319	/// No combinations of more than one factor are tested. Lift bound is adapted.
320	///
321	/// @return @a earlyFactorDetect returns a list of factors of F (possibly
322	/// incomplete), in case of success. Otherwise an empty list.
323	/// @sa factorRecombination(), extEarlyFactorDetect()
324	CFList
325	earlyFactorDetect (
326	CanonicalForm& F, ///< [in,out] poly to be factored,
327	///< returns poly divided by detected
328	///< factors in case of success
329	CFList& factors, ///< [in,out] list of factors lifted up
330	///< to @a deg, returns a list of factors
331	///< without detected factors
332	int& adaptedLiftBound, ///< [in,out] adapted lift bound
333	bool& success, ///< [in,out] indicating success
334	const int deg, ///< [in] stage of Hensel lifting
335	const CFList& MOD, ///< [in] a list of powers of
336	///< Variables
337	const int bound ///< [in] initial lift bound
338	);
339
340	/// detects factors of @a F at stage @a deg of Hensel lifting.
341	/// No combinations of more than one factor are tested. Lift bound is adapted.
342	///
343	/// @return @a extEarlyFactorDetect returns a list of factors of F (possibly
344	/// incomplete), whose shift to zero is reversed, in case of success.
345	/// Otherwise an empty list.
346	/// @sa factorRecombination(), earlyFactorDetection()
347	CFList
348	extEarlyFactorDetect (
349	CanonicalForm& F, ///< [in,out] poly to be factored,
350	///< returns poly divided by detected
351	///< factors in case of success
352	CFList& factors, ///< [in,out] list of factors lifted up
353	///< to @a deg, returns a list of factors
354	///< without detected factors
355	int& adaptedLiftBound, ///< [in,out] adapted lift bound
356	bool& success, ///< [in,out] indicating succes
357	const ExtensionInfo& info, ///< [in] info about extension
358	const CFList& eval, ///< [in] evaluation point
359	const int deg, ///< [in] stage of Hensel lifting
360	const CFList& MOD, ///< [in] a list of powers of Variables
361	const int bound ///< [in] initial lift bound
362	);
363
364	/// evaluation point search for multivariate factorization,
365	/// looks for a (F.level() - 1)-tuple such that the resulting univariate
366	/// polynomial has main variable Variable (1), is squarefree and its degree
367	/// coincides with degree(F) and the bivariate one is primitive wrt.
368	/// Variable(1), and successively evaluated polynomials have the same degree in
369	/// their main variable as F has, fails if there are no valid evaluation points,
370	/// eval contains the intermediate evaluated polynomials.
371	///
372	/// @return @a evalPoints returns an evaluation point, which is valid if and
373	/// only if fail == false.
374	CFList
375	evalPoints (const CanonicalForm& F, ///< [in] a compressed poly
376	CFList & eval, ///< [in,out] an empty list, returns @a F
377	///< successive evaluated
378	const Variable& alpha, ///< [in] algebraic variable
379	CFList& list, ///< [in,out] a list of points already
380	///< considered, a point is encoded as a
381	///< poly of degree F.level()-1 in
382	///< Variable(1)
383	const bool& GF, ///< [in] GF?
384	bool& fail ///< [in,out] indicates failure
385	);
386
387	/// hensel Lifting and early factor detection
388	///
389	/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
390	/// factors without factors which have been detected at an early stage
391	/// of Hensel lifting
392	/// @sa earlyFactorDetectn(), extEarlyFactorDetect()
393	CFList
394	henselLiftAndEarly (
395	CanonicalForm& A, ///< [in,out] poly to be factored,
396	///< returns poly divided by detected
397	///< factors, in case of success
398	CFList& MOD, ///< [in,out] a list of powers of
399	///< Variables
400	int*& liftBounds, ///< [in,out] initial lift bounds, returns
401	///< adapted lift bounds
402	bool& earlySuccess, ///< [in,out] indicating success
403	CFList& earlyFactors, ///< [in,out] early factors
404	const CFList& Aeval, ///< [in] @a A successively evaluated at
405	///< elements of @a evaluation
406	const CFList& biFactors, ///< [in] bivariate factors
407	const CFList& evaluation, ///< [in] evaluation point
408	const ExtensionInfo& info ///< [in] info about extension
409	);
410
411	/// Factorization over an extension of initial field
412	///
413	/// @return @a extFactorize returns factorization of F over initial field
414	/// @sa extBiFactorize(), multiFactorize()
415	CFList
416	extFactorize (const CanonicalForm& F, ///< [in] poly to be factored
417	const ExtensionInfo& info ///< [in] info about extension
418	);
419
420	/// compute the LCM of the contents of @a A wrt to each variable occuring in @a
421	/// A.
422	///
423	/// @return @a lcmContent returns the LCM of the contents of @a A wrt to each
424	/// variable occuring in @a A.
425	CanonicalForm
426	lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly
427	CFList& contentAi ///< [in,out] an empty list, returns a list
428	///< of the contents of @a A wrt to each
429	///< variable occuring in @a A starting from
430	///< @a A.mvar().
431	);
432
433	/// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and
434	/// no gaps between the variables occur
435	///
436	/// @return a compressed poly with the above properties
437	CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly
438	CFMap& N ///< [in,out] a map to
439	///< decompress
440	);
441
442	/// evaluate a poly A with main variable at level 1 at an evaluation point in
443	/// K^(n-1) wrt different second variables. If this evaluation is valid (see
444	/// evalPoints) then Aeval contains A successively evaluated at this point,
445	/// otherwise this entry is empty
446	void
447	evaluationWRTDifferentSecondVars (
448	CFList*& Aeval, ///<[in,out] an array of length n-2
449	///< if variable at level i > 2
450	///< admits a valid evaluation
451	///< this entry contains A
452	///< successively evaluated at this
453	///< point otherwise an empty list
454	const CFList& evaluation,///<[in] a valid evaluation point
455	///< for main variable at level 1
456	///< and second variable at level 2
457	const CanonicalForm& A ///<[in] some poly
458	);
459
460	/// evaluate F successively n-2 at 0
461	///
462	/// @return returns a list of successive evaluations of F, ending with F
463	CFList evaluateAtZero (const CanonicalForm& F ///< [in] some poly
464	);
465
466	/// divides factors by their content wrt. Variable(1) and checks if these polys
467	/// divide F
468	///
469	/// @return returns factors of F
470	CFList recoverFactors (const CanonicalForm& F, ///< [in] some poly F
471	const CFList& factors ///< [in] some list of
472	///< factor candidates
473	);
474
475	/// divides factors shifted by evaluation by their content wrt. Variable(1) and
476	/// checks if these polys divide F
477	///
478	/// @return returns factors of F
479	CFList recoverFactors (const CanonicalForm& F, ///< [in] some poly F
480	const CFList& factors, ///< [in] some list of
481	///< factor candidates
482	const CFList& evaluation
483	);
484
485	/// refine a bivariate factorization of A with l factors to one with
486	/// minFactorsLength
487	void
488	refineBiFactors (const CanonicalForm& A, ///< [in] some poly
489	CFList& biFactors, ///< [in,out] list of bivariate to be
490	///< refined, returns refined factors
491	CFList* const& factors, ///< [in] list of bivariate
492	///< factorizations of A wrt different
493	///< second variables
494	const CFList& evaluation,///< [in] the evaluation point
495	int minFactorsLength ///< [in] the minimal number of factors
496	);
497
498	/// plug in evalPoint for y in a list of polys
499	///
500	/// @return returns a list of the evaluated polys, these evaluated polys are
501	/// made monic
502	CFList
503	buildUniFactors (const CFList& biFactors, ///< [in] a list of polys
504	const CanonicalForm& evalPoint,///< [in] some evaluation point
505	const Variable& y ///< [in] some variable
506	);
507
508	/// extract leading coefficients wrt Variable(1) from bivariate factors obtained
509	/// from factorizations of A wrt different second variables
510	void
511	getLeadingCoeffs (const CanonicalForm& A, ///< [in] some poly
512	CFList*& Aeval, ///< [in,out] array of bivariate
513	///< factors, returns the leading
514	///< coefficients of these factors
515	const CFList& uniFactors,///< [in] univariate factors of A
516	const CFList& evaluation ///< [in] evaluation point
517	);
518
519	/// normalize precomputed leading coefficients such that leading coefficients
520	/// evaluated at 0 in K^(n-2) equal the leading coeffs wrt Variable(1) of
521	/// bivariate factors
522	void
523	prepareLeadingCoeffs (CFList*& LCs, ///<[in,out]
524	int n, ///<[in] level of poly to be
525	///< factored
526	const CFList& leadingCoeffs,///<[in] precomputed leading
527	///< coeffs
528	const CFList& biFactors ///<[in] bivariate factors
529	);
530
531	/// obtain factors of F by reconstructing their leading coeffs
532	///
533	/// @return returns the reconstructed factors
534	/// @sa factorRecombination()
535	CFList
536	leadingCoeffReconstruction (const CanonicalForm& F,///<[in] poly to be factored
537	const CFList& factors, ///<[in] factors of f monic
538	///< wrt Variable (1)
539	const CFList& M ///<[in] a list of powers of
540	///< Variables
541	);
542
543	/// distribute content
544	///
545	/// @return returns a list result of polys such that prod (result)= prod (L)
546	/// but the first entry of L may be (partially) factorized and these factors
547	/// are distributed onto other entries in L
548	CFList
549	distributeContent (
550	const CFList& L, ///<[in] list of polys, first
551	///< entry the content to be
552	///< distributed
553	const CFList* differentSecondVarFactors,///<[in] factorization wrt
554	///< different second vars
555	int length ///<[in] length of
556	///<differentSecondVarFactors
557	);
558
559	/// gcd free basis of two lists of factors
560	void
561	gcdFreeBasis (CFFList& factors1, ///< [in,out] list of factors, returns gcd free
562	///< factors
563	CFFList& factors2 ///< [in,out] list of factors, returns gcd free
564	///< factors
565	);
566
567	/// heuristic algorithm for lifting sparse polynomials
568	///
569	/// @return a list of factors of A, possibly incomplete
570	CFList
571	sparseHeuristic (const CanonicalForm& A, ///<[in] polynomial to be factored
572	const CFList& biFactors, ///<[in] list of bivariate factors wrt
573	///< Variable 1 and 2
574	CFList*& moreBiFactors, ///<[in,out] more bivariate factors
575	///< wrt different second variables.
576	///< May be recombined s.t. there are
577	///< only minFactorsLength factors and
578	///< resorted s.t. the sequence of
579	///< univariate factors in biFactors
580	///< and moreBiFactors coincides
581	const CFList& evaluation,///<[in] evaluation point
582	int minFactorsLength ///<[in] minimal number of factors
583	);
584
585	#endif
586	/* FAC_FQ_FACTORIZE_H */
587

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

Download in other formats: