Context Navigation

source: git/factory/facFactorize.cc @ ee668e

spielwiese

Last change on this file since ee668e was ec16f0, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: use sparse heuristic in precomputation of leading coefficients
Property mode set to `100644`
File size: 25.7 KB

Line
1	/*****************************************************************************\
2	* Computer Algebra System SINGULAR
3	\*****************************************************************************/
4	/** @file facFqFactorize.cc
5	*
6	* multivariate factorization over Q(a)
7	*
8	* @author Martin Lee
9	*
10	* @internal @version \$Id$
11	*
12	**/
13	/*****************************************************************************/
14
15	#include "config.h"
16
17	#include "assert.h"
18	#include "debug.h"
19	#include "timing.h"
20
21	#include "cf_algorithm.h"
22	#include "facFqFactorizeUtil.h"
23	#include "facFactorize.h"
24	#include "facFqFactorize.h"
25	#include "cf_random.h"
26	#include "facHensel.h"
27	#include "cf_gcd_smallp.h"
28	#include "cf_map_ext.h"
29	#include "algext.h"
30	#include "cf_reval.h"
31	#include "facSparseHensel.h"
32
33	#ifdef HAVE_NTL
34	CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E)
35	{
36	CFList result;
37	Variable x= Variable (1);
38
39	bool found= false;
40	CanonicalForm deriv_x, gcd_deriv;
41	CFListIterator iter;
42	do
43	{
44	eval.insert (F);
45	bool bad= false;
46	for (int i= E.max(); i >= E.min(); i--)
47	{
48	eval.insert (eval.getFirst()( E [i], i));
49	result.append (E[i]);
50	if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
51	{
52	result= CFList();
53	eval= CFList();
54	bad= true;
55	break;
56	}
57	}
58
59	if (bad)
60	{
61	E.nextpoint();
62	continue;
63	}
64
65	if (degree (eval.getFirst()) != degree (F, 1))
66	{
67	result= CFList();
68	eval= CFList();
69	E.nextpoint();
70	continue;
71	}
72
73	deriv_x= deriv (eval.getFirst(), x);
74	gcd_deriv= gcd (eval.getFirst(), deriv_x);
75	if (degree (gcd_deriv) > 0)
76	{
77	result= CFList();
78	eval= CFList();
79	E.nextpoint();
80	continue;
81	}
82	iter= eval;
83	iter++;
84	CanonicalForm contentx= content (iter.getItem(), x);
85	if (degree (contentx) > 0)
86	{
87	result= CFList();
88	eval= CFList();
89	E.nextpoint();
90	continue;
91	}
92	found= true;
93	}
94	while (!found);
95
96	if (!eval.isEmpty())
97	eval.removeFirst();
98	return result;
99	}
100
101	void
102	factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
103	int& minFactorsLength, bool& irred,
104	const Variable& w)
105	{
106	Variable x= Variable (1);
107	minFactorsLength= 0;
108	irred= false;
109	Variable v;
110	CFList factors;
111	for (int j= 0; j < A.level() - 2; j++)
112	{
113	if (!Aeval[j].isEmpty())
114	{
115	v= Variable (Aeval[j].getFirst().level());
116
117	factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
118
119	if (factors.getFirst().inCoeffDomain())
120	factors.removeFirst();
121
122	if (minFactorsLength == 0)
123	minFactorsLength= factors.length();
124	else
125	minFactorsLength= tmin (minFactorsLength, factors.length());
126
127	if (factors.length() == 1)
128	{
129	irred= true;
130	return;
131	}
132	sortList (factors, x);
133	Aeval [j]= factors;
134	}
135	}
136	}
137
138	int
139	testFactors (const CanonicalForm& G, const CFList& uniFactors,
140	CanonicalForm& sqrfPartF, CFList& factors,
141	CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
142	const CFArray& evalPoint)
143	{
144	CanonicalForm tmp;
145	CFListIterator j;
146	for (CFListIterator i= uniFactors; i.hasItem(); i++)
147	{
148	tmp= i.getItem();
149	if (i.hasItem())
150	i++;
151	else
152	break;
153	for (j= i; j.hasItem(); j++)
154	{
155	if (tmp == j.getItem())
156	return 0;
157	}
158	}
159
160	CanonicalForm F= G;
161	CFFList sqrfFactorization= sqrFree (F);
162
163	sqrfPartF= 1;
164	for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
165	sqrfPartF *= i.getItem().factor();
166
167	evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
168
169	CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
170
171	if (degree (test) != degree (sqrfPartF, 1))
172	return 0;
173
174	CFFList sqrfFactors;
175	CFList tmp2;
176	int k= 0;
177	factors= uniFactors;
178	CFFListIterator iter;
179	for (CFListIterator i= factors; i.hasItem(); i++, k++)
180	{
181	tmp= 1;
182	sqrfFactors= sqrFree (i.getItem());
183
184	for (iter= sqrfFactors; iter.hasItem(); iter++)
185	{
186	tmp2.append (iter.getItem().factor());
187	tmp *= iter.getItem().factor();
188	}
189	i.getItem()= tmp/Lc(tmp);
190	bufSqrfFactors [k]= sqrfFactors;
191	}
192
193	for (int i= 0; i < factors.length() - 1; i++)
194	{
195	for (int k= i + 1; k < factors.length(); k++)
196	{
197	gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
198	}
199	}
200
201	factors= CFList();
202	for (int i= 0; i < uniFactors.length(); i++)
203	{
204	if (i == 0)
205	{
206	for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
207	{
208	if (iter.getItem().factor().inCoeffDomain())
209	continue;
210	iter.getItem()= CFFactor (iter.getItem().factor()/
211	Lc (iter.getItem().factor()),
212	iter.getItem().exp());
213	factors.append (iter.getItem().factor());
214	}
215	}
216	else
217	{
218	for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
219	{
220	if (iter.getItem().factor().inCoeffDomain())
221	continue;
222	iter.getItem()= CFFactor (iter.getItem().factor()/
223	Lc (iter.getItem().factor()),
224	iter.getItem().exp());
225	if (!find (factors, iter.getItem().factor()))
226	factors.append (iter.getItem().factor());
227	}
228	}
229	}
230
231	test= prod (factors);
232	tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
233	if (test/Lc (test) != tmp/Lc (tmp))
234	return 0;
235	else
236	return 1;
237	}
238
239	CFList
240	precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
241	const CFList& evaluation,CFList*& differentSecondVarLCs,
242	int length, Variable& y
243	)
244	{
245	y= Variable (1);
246	if (LCF.inCoeffDomain())
247	{
248	CFList result;
249	for (int i= 1; i <= LCFFactors.length() + 1; i++)
250	result.append (1);
251	return result;
252	}
253
254	CFMap N;
255	CanonicalForm F= compress (LCF, N);
256	if (LCF.isUnivariate())
257	{
258	CFList result;
259	int LCFLevel= LCF.level();
260	bool found= false;
261	if (LCFLevel == 2)
262	{
263	//bivariate leading coefficients are already the true leading coefficients
264	result= LCFFactors;
265	found= true;
266	}
267	else
268	{
269	CFListIterator j;
270	for (int i= 0; i < length; i++)
271	{
272	for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
273	{
274	if (j.getItem().level() == LCFLevel)
275	{
276	found= true;
277	break;
278	}
279	}
280	if (found)
281	{
282	result= differentSecondVarLCs [i];
283	break;
284	}
285	}
286	if (!found)
287	result= LCFFactors;
288	}
289	if (found)
290	result.insert (Lc (LCF));
291	else
292	result.append (LCF);
293	return result;
294	}
295
296	CFList factors= LCFFactors;
297
298	CFMap dummy;
299	for (CFListIterator i= factors; i.hasItem(); i++)
300	i.getItem()= compress (i.getItem(), dummy);
301
302	CanonicalForm sqrfPartF;
303	CFFList * bufSqrfFactors= new CFFList [factors.length()];
304	CFList evalSqrfPartF, bufFactors;
305	CFArray evalPoint= CFArray (evaluation.length() - 1);
306	CFListIterator iter= evaluation;
307	for (int i= evaluation.length() - 2; i > -1; i--, iter++)
308	evalPoint[i]= iter.getItem();
309	//TODO sqrfPartF einmal berechnen nicht stÃ€ndig
310	int pass= testFactors (F, factors, sqrfPartF,
311	bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
312
313	bool foundDifferent= false;
314	Variable z;
315	Variable x= y;
316	int j= 0;
317	if (!pass)
318	{
319	int lev;
320	for (int i= 1; i <= LCF.level(); i++)
321	{
322	if(degree (LCF, i) > 0)
323	{
324	lev= i - 1;
325	break;
326	}
327	}
328	for (int i= 0; i < length; i++)
329	{
330	CanonicalForm bufF, swap;
331	CFList bufBufFactors;
332	CFArray buf;
333	if (!differentSecondVarLCs [i].isEmpty())
334	{
335	bool allConstant= true;
336	for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
337	{
338	if (!iter.getItem().inCoeffDomain())
339	{
340	allConstant= false;
341	y= Variable (iter.getItem().level());
342	}
343	}
344	if (allConstant)
345	continue;
346
347	bufFactors= differentSecondVarLCs [i];
348	for (iter= bufFactors; iter.hasItem(); iter++)
349	iter.getItem()= swapvar (iter.getItem(), x, y);
350	bufF= F;
351	z= Variable (y.level() - lev);
352	bufF= swapvar (bufF, x, z);
353	bufBufFactors= bufFactors;
354	evalPoint= CFArray (evaluation.length() - 1);
355	buf= CFArray (evaluation.length());
356	iter= evaluation;
357	int k= evaluation.length() - 1;
358	for (; iter.hasItem(); iter++, k--)
359	buf[k]= iter.getItem();
360	swap= buf[z.level() - 1];
361	buf[z.level() - 1]= buf[0];
362	buf[0]= 0;
363	int l= 0;
364	for (k= 0; k < evaluation.length(); k++)
365	{
366	if (buf[k].isZero())
367	continue;
368	evalPoint[l]= buf[k];
369	l++;
370	}
371	pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
372	bufSqrfFactors, evalSqrfPartF, evalPoint);
373	if (pass)
374	{
375	foundDifferent= true;
376	F= bufF;
377	CFList l= factors;
378	for (iter= l; iter.hasItem(); iter++)
379	iter.getItem()= swapvar (iter.getItem(), x, y);
380	differentSecondVarLCs [i]= l;
381	j= i;
382	break;
383	}
384	if (!pass && i == length - 1)
385	{
386	CFList result;
387	result.append (LCF);
388	for (int j= 1; j <= factors.length(); j++)
389	result.append (LCF);
390	y= Variable (1);
391	delete [] bufSqrfFactors;
392	return result;
393	}
394	}
395	}
396	}
397	if (!pass)
398	{
399	CFList result;
400	result.append (LCF);
401	for (int j= 1; j <= factors.length(); j++)
402	result.append (LCF);
403	y= Variable (1);
404	delete [] bufSqrfFactors;
405	return result;
406	}
407	else
408	factors= bufFactors;
409
410
411	bufFactors= factors;
412	CFList evaluation2;
413	if (y == x)
414	evaluation2= evaluation;
415	else
416	{
417	CanonicalForm tmp;
418	evaluation2= evaluation;
419	int i= evaluation.length() + 1;
420	for (CFListIterator iter= evaluation2; iter.hasItem(); iter++, i--)
421	{
422	if (i == y.level())
423	{
424	tmp= iter.getItem();
425	iter.getItem()= evaluation2.getLast();
426	evaluation2.removeLast();
427	evaluation2.append (tmp);
428	break;
429	}
430	}
431	}
432
433	CFList interMedResult;
434	CanonicalForm oldSqrfPartF= sqrfPartF;
435	sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
436	if (factors.length() > 1)
437	{
438	CanonicalForm LC1= LC (oldSqrfPartF, 1);
439	CFList leadingCoeffs;
440	for (int i= 0; i < factors.length(); i++)
441	leadingCoeffs.append (LC1);
442
443	CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
444	CFList oldFactors= factors;
445	for (CFListIterator i= oldFactors; i.hasItem(); i++)
446	i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
447
448	bool success= false;
449	if (LucksWangSparseHeuristic (oldSqrfPartF*power (LC1, factors.length()-1),
450	oldFactors, 1, leadingCoeffs, factors))
451	{
452	interMedResult= recoverFactors (oldSqrfPartF, factors);
453	if (oldFactors.length() == interMedResult.length())
454	success= true;
455	}
456	if (!success)
457	{
458	LC1= LC (evalSqrfPartF.getFirst(), 1);
459
460	CFArray leadingCoeffs= CFArray (factors.length());
461	for (int i= 0; i < factors.length(); i++)
462	leadingCoeffs[i]= LC1;
463
464	for (CFListIterator i= factors; i.hasItem(); i++)
465	{
466	i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
467	i.getItem() *= LC1 (0,2)/Lc (i.getItem());
468	}
469	factors.insert (1);
470
471	CanonicalForm
472	newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
473
474	int liftBound= degree (newSqrfPartF,2) + 1;
475
476	CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
477	CFArray Pi;
478	CFList diophant;
479	henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
480	leadingCoeffs, false);
481
482	if (sqrfPartF.level() > 2)
483	{
484	int* liftBounds= new int [sqrfPartF.level() - 1];
485	liftBounds [0]= liftBound;
486	bool noOneToOne= false;
487	CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
488	LC1= LC (evalSqrfPartF.getLast(), 1);
489	CFList LCs;
490	for (int i= 0; i < factors.length(); i++)
491	LCs.append (LC1);
492	leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
493	for (int i= sqrfPartF.level() - 1; i > 2; i--)
494	{
495	for (CFListIterator j= LCs; j.hasItem(); j++)
496	j.getItem()= j.getItem() (0, i + 1);
497	leadingCoeffs2 [i - 3]= LCs;
498	}
499	sqrfPartF *= power (LC1, factors.length()-1);
500
501	int liftBoundsLength= sqrfPartF.level() - 1;
502	for (int i= 1; i < liftBoundsLength; i++)
503	liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
504	evalSqrfPartF= evaluateAtZero (sqrfPartF);
505	evalSqrfPartF.removeFirst();
506	factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
507	diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
508	delete [] leadingCoeffs2;
509	delete [] liftBounds;
510	}
511	for (CFListIterator iter= factors; iter.hasItem(); iter++)
512	iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
513
514	interMedResult=
515	recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
516	factors);
517	}
518	}
519	else
520	{
521	factors= CFList (oldSqrfPartF);
522	interMedResult= recoverFactors (oldSqrfPartF, factors);
523	}
524
525	CFList result;
526	CFFListIterator k;
527	CanonicalForm tmp;
528	for (int i= 0; i < LCFFactors.length(); i++)
529	{
530	tmp= 1;
531	for (k= bufSqrfFactors[i]; k.hasItem(); k++)
532	{
533	int pos= findItem (bufFactors, k.getItem().factor());
534	if (pos)
535	tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
536	}
537	result.append (tmp);
538	}
539
540	for (CFListIterator i= result; i.hasItem(); i++)
541	{
542	F /= i.getItem();
543	if (foundDifferent)
544	i.getItem()= swapvar (i.getItem(), x, z);
545	i.getItem()= N (i.getItem());
546	}
547
548	if (foundDifferent)
549	{
550	CFList l= differentSecondVarLCs [j];
551	for (CFListIterator i= l; i.hasItem(); i++)
552	i.getItem()= swapvar (i.getItem(), y, z);
553	differentSecondVarLCs [j]= l;
554	F= swapvar (F, x, z);
555	}
556
557	result.insert (N (F));
558
559	result= distributeContent (result, differentSecondVarLCs, length);
560
561	if (!result.getFirst().inCoeffDomain())
562	{
563	CFListIterator i= result;
564	CanonicalForm tmp;
565	if (foundDifferent)
566	i.getItem()= swapvar (i.getItem(), Variable (2), y);
567
568	tmp= i.getItem();
569
570	i++;
571	for (; i.hasItem(); i++)
572	{
573	if (foundDifferent)
574	i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
575	else
576	i.getItem() *= tmp;
577	}
578	}
579	else
580	y= Variable (1);
581
582	delete [] bufSqrfFactors;
583
584	return result;
585	}
586
587
588	CFList
589	multiFactorize (const CanonicalForm& F, const Variable& v)
590	{
591	if (F.inCoeffDomain())
592	return CFList (F);
593
594	// compress and find main Variable
595	CFMap N;
596	CanonicalForm A= myCompress (F, N);
597
598	//univariate case
599	if (F.isUnivariate())
600	{
601	CFList result= conv (factorize (F, v));
602	if (result.getFirst().inCoeffDomain())
603	result.removeFirst();
604	return result;
605	}
606
607	//bivariate case
608	if (A.level() == 2)
609	{
610	CFList buf= biFactorize (F, v);
611	return buf;
612	}
613
614	Variable x= Variable (1);
615	Variable y= Variable (2);
616
617	// remove content
618	CFList contentAi;
619	CanonicalForm lcmCont= lcmContent (A, contentAi);
620	A /= lcmCont;
621
622	// trivial after content removal
623	CFList contentAFactors;
624	if (A.inCoeffDomain())
625	{
626	for (CFListIterator i= contentAi; i.hasItem(); i++)
627	{
628	if (i.getItem().inCoeffDomain())
629	continue;
630	else
631	{
632	lcmCont /= i.getItem();
633	contentAFactors=
634	Union (multiFactorize (lcmCont, v),
635	multiFactorize (i.getItem(), v));
636	break;
637	}
638	}
639	decompress (contentAFactors, N);
640	if (isOn (SW_RATIONAL))
641	normalize (contentAFactors);
642	return contentAFactors;
643	}
644
645	// factorize content
646	contentAFactors= multiFactorize (lcmCont, v);
647
648	// univariate after content removal
649	CFList factors;
650	if (A.isUnivariate ())
651	{
652	factors= conv (factorize (A, v));
653	append (factors, contentAFactors);
654	decompress (factors, N);
655	return factors;
656	}
657
658	// check main variable
659	CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
660	int factorNums= 3;
661	CanonicalForm bivarEval;
662	CFList biFactors, bufBiFactors;
663	CanonicalForm evalPoly;
664	int lift, bufLift;
665	CFList* bufAeval2= new CFList [A.level() - 2];
666	CFList* Aeval2= new CFList [A.level() - 2];
667	int counter;
668	int differentSecondVar= 0;
669	CanonicalForm bufA;
670	// several bivariate factorizations
671	REvaluation E (2, A.level(), IntRandom (25));
672	for (int i= 0; i < factorNums; i++)
673	{
674	counter= 0;
675	bufA= A;
676	bufAeval= CFList();
677	bufEvaluation= evalPoints (bufA, bufAeval, E);
678	E.nextpoint();
679	evalPoly= 0;
680
681	bivarEval= bufEvaluation.getLast();
682
683	evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
684
685	for (int j= 0; j < A.level() - 1; j++)
686	{
687	if (!bufAeval2[j].isEmpty())
688	counter++;
689	}
690
691	bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
692
693	TIMING_START (fac_bi_factorizer);
694	bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
695	TIMING_END_AND_PRINT (fac_bi_factorizer,
696	"time for bivariate factorization: ");
697	bufBiFactors.removeFirst();
698
699	if (bufBiFactors.length() == 1)
700	{
701	factors.append (A);
702	appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
703	if (isOn (SW_RATIONAL))
704	normalize (factors);
705	delete [] bufAeval2;
706	delete [] Aeval2;
707	return factors;
708	}
709
710	if (i == 0)
711	{
712	Aeval= bufAeval;
713	evaluation= bufEvaluation;
714	biFactors= bufBiFactors;
715	lift= bufLift;
716	for (int j= 0; j < A.level() - 2; j++)
717	Aeval2 [j]= bufAeval2 [j];
718	differentSecondVar= counter;
719	}
720	else
721	{
722	if (bufBiFactors.length() < biFactors.length() \|\|
723	((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) \|\|
724	counter > differentSecondVar)
725	{
726	Aeval= bufAeval;
727	evaluation= bufEvaluation;
728	biFactors= bufBiFactors;
729	lift= bufLift;
730	for (int j= 0; j < A.level() - 2; j++)
731	Aeval2 [j]= bufAeval2 [j];
732	differentSecondVar= counter;
733	}
734	}
735	int k= 0;
736	for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
737	evalPoly += j.getItem()*power (x, k);
738	list.append (evalPoly);
739	}
740
741	delete [] bufAeval2;
742
743	sortList (biFactors, x);
744
745	int minFactorsLength;
746	bool irred= false;
747	factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
748
749	if (irred)
750	{
751	factors.append (A);
752	appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
753	if (isOn (SW_RATIONAL))
754	normalize (factors);
755	delete [] Aeval2;
756	return factors;
757	}
758
759	if (minFactorsLength == 0)
760	minFactorsLength= biFactors.length();
761	else if (biFactors.length() > minFactorsLength)
762	refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
763
764	if (differentSecondVar == A.level() - 2)
765	{
766	bool zeroOccured= false;
767	for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
768	{
769	if (iter.getItem().isZero())
770	{
771	zeroOccured= true;
772	break;
773	}
774	}
775	if (!zeroOccured)
776	{
777	factors= sparseHeuristic (A, biFactors, Aeval2, evaluation, minFactorsLength);
778	if (factors.length() == biFactors.length())
779	{
780	appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
781	normalize (factors);
782	delete [] Aeval2;
783	return factors;
784	}
785	else
786	factors= CFList();
787	//TODO case where factors.length() > 0
788	}
789	}
790
791	CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
792
793	CFList * oldAeval= new CFList [A.level() - 2];
794	for (int i= 0; i < A.level() - 2; i++)
795	oldAeval[i]= Aeval2[i];
796
797	getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
798
799	CFList biFactorsLCs;
800	for (CFListIterator i= biFactors; i.hasItem(); i++)
801	biFactorsLCs.append (LC (i.getItem(), 1));
802
803	Variable w;
804	CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
805	evaluation, Aeval2, A.level() - 2, w);
806
807	if (w.level() != 1)
808	{
809	A= swapvar (A, y, w);
810	for (int i= 0; i < A.level() - 2; i++)
811	{
812	if (oldAeval[i].isEmpty())
813	continue;
814	if (oldAeval[i].getFirst().level() == w.level())
815	{
816	biFactors= CFList();
817	for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
818	biFactors.append (swapvar (iter.getItem(), w, y));
819	}
820	}
821	int i= A.level();
822	CanonicalForm evalPoint;
823	for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
824	{
825	if (i == w.level())
826	{
827	evalPoint= iter.getItem();
828	iter.getItem()= evaluation.getLast();
829	evaluation.removeLast();
830	evaluation.append (evalPoint);
831	break;
832	}
833	}
834	}
835
836	CFListIterator iter;
837	CanonicalForm oldA= A;
838	CFList oldBiFactors= biFactors;
839	if (!leadingCoeffs.getFirst().inCoeffDomain())
840	{
841	CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
842	A *= tmp;
843	Aeval= evaluateAtZero (A);
844	tmp= leadingCoeffs.getFirst();
845	iter= evaluation;
846	for (int i= A.level(); i > 2; i--, iter++)
847	tmp= tmp (iter.getItem(), i);
848	if (!tmp.inCoeffDomain())
849	{
850	for (CFListIterator i= biFactors; i.hasItem(); i++)
851	{
852	i.getItem() *= tmp/LC (i.getItem(), 1);
853	i.getItem() /= Lc (i.getItem());
854	}
855	}
856	}
857
858	leadingCoeffs.removeFirst();
859
860	//prepare leading coefficients
861	CFList* leadingCoeffs2= new CFList [A.level() - 2];
862	prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
863	evaluation);
864
865
866	Aeval= evaluateAtEval (A, evaluation, 2);
867
868	CanonicalForm hh= Lc (Aeval.getFirst());
869
870	for (CFListIterator i= Aeval; i.hasItem(); i++)
871	i.getItem() /= hh;
872
873	A /= hh;
874
875	if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2 [A.level() - 3],
876	factors))
877	{
878	int check= factors.length();
879	factors= recoverFactors (A, factors);
880
881	if (check == factors.length())
882	{
883	appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
884	normalize (factors);
885	delete [] Aeval2;
886	return factors;
887	}
888	else
889	factors= CFList();
890	}
891
892
893	//shifting to zero
894	A= shift2Zero (A, Aeval, evaluation);
895
896	for (iter= biFactors; iter.hasItem(); iter++)
897	iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
898
899	for (int i= 0; i < A.level() - 2; i++)
900	{
901	if (i != A.level() - 3)
902	leadingCoeffs2[i]= CFList();
903	}
904	for (iter= leadingCoeffs2[A.level() - 3]; iter.hasItem(); iter++)
905	{
906	iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
907	for (int i= A.level() - 4; i > -1; i--)
908	{
909	if (i + 1 == A.level() - 3)
910	leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
911	else
912	leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
913	}
914	}
915
916	CFArray Pi;
917	CFList diophant;
918	int* liftBounds= new int [A.level() - 1];
919	int liftBoundsLength= A.level() - 1;
920	for (int i= 0; i < liftBoundsLength; i++)
921	liftBounds [i]= degree (A, i + 2) + 1;
922
923	Aeval.removeFirst();
924	bool noOneToOne= false;
925
926	factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
927	Pi, liftBounds, liftBoundsLength, noOneToOne);
928
929	if (!noOneToOne)
930	{
931	int check= factors.length();
932	A= oldA;
933	factors= recoverFactors (A, factors, evaluation);
934	if (check != factors.length())
935	noOneToOne= true;
936	}
937	if (noOneToOne)
938	{
939	A= shift2Zero (oldA, Aeval, evaluation);
940	biFactors= oldBiFactors;
941	for (iter= biFactors; iter.hasItem(); iter++)
942	iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
943	CanonicalForm LCA= LC (Aeval.getFirst(), 1);
944	CanonicalForm yToLift= power (y, lift);
945	CFListIterator i= biFactors;
946	lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
947	i++;
948
949	for (; i.hasItem(); i++)
950	lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
951
952	lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
953
954	i= biFactors;
955	yToLift= power (y, lift);
956	CanonicalForm dummy;
957	for (; i.hasItem(); i++)
958	{
959	LCA= LC (i.getItem(), 1);
960	extgcd (LCA, yToLift, LCA, dummy);
961	i.getItem()= mod (i.getItem()*LCA, yToLift);
962	}
963
964	liftBoundsLength= F.level() - 1;
965	liftBounds= liftingBounds (A, lift);
966
967	CFList MOD;
968	bool earlySuccess;
969	CFList earlyFactors;
970	ExtensionInfo info= ExtensionInfo (false);
971	TIMING_START (fac_hensel_lift);
972	CFList liftedFactors= henselLiftAndEarly
973	(A, MOD, liftBounds, earlySuccess, earlyFactors,
974	Aeval, biFactors, evaluation, info);
975	TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
976
977	TIMING_START (fac_factor_recombination);
978	factors= factorRecombination (A, liftedFactors, MOD);
979	TIMING_END_AND_PRINT (fac_factor_recombination,
980	"time for factor recombination: ");
981
982	if (earlySuccess)
983	factors= Union (factors, earlyFactors);
984
985	for (CFListIterator i= factors; i.hasItem(); i++)
986	{
987	int kk= Aeval.getLast().level();
988	for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
989	{
990	if (i.getItem().level() < kk)
991	continue;
992	i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
993	}
994	}
995	}
996
997	if (w.level() != 1)
998	{
999	for (CFListIterator iter= factors; iter.hasItem(); iter++)
1000	iter.getItem()= swapvar (iter.getItem(), w, y);
1001	}
1002
1003	swap (factors, 0, 0, x);
1004	append (factors, contentAFactors);
1005	decompress (factors, N);
1006	if (isOn (SW_RATIONAL))
1007	normalize (factors);
1008
1009	delete [] leadingCoeffs2;
1010	delete [] oldAeval;
1011	delete [] Aeval2;
1012	delete[] liftBounds;
1013
1014	return factors;
1015	}
1016
1017	#endif

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

Download in other formats: