Changeset 0851b0 in git

Timestamp:

Oct 12, 2012, 5:31:21 PM (10 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')

Children:

cb4f0c3c5277d6de4d18c968650b4169ff1d1b46

Parents:

2a95b234ef67ebbc98057baefb8dd2ed43af3762

git-author:

Martin Lee <martinlee84@web.de>2012-10-12 17:31:21+02:00

git-committer:

Martin Lee <martinlee84@web.de>2012-10-24 12:26:22+02:00

Message:

chg: added more timing infos to main factorization functions

Location:

factory

Files:

• facAlgExt.cc (modified) (9 diffs)
• facBivar.cc (modified) (5 diffs)
• facBivar.h (modified) (3 diffs)
• facFactorize.cc (modified) (18 diffs)
• facFactorize.h (modified) (2 diffs)
• facFqBivar.cc (modified) (13 diffs)
• facFqBivar.h (modified) (8 diffs)
• facFqFactorize.cc (modified) (19 diffs)
• facFqFactorize.h (modified) (6 diffs)

factory/facAlgExt.cc

@@ -29 +29 @@
 #include "fac_sqrfree.h"
 
+TIMING_DEFINE_PRINT(fac_alg_resultant)
+TIMING_DEFINE_PRINT(fac_alg_norm)
+TIMING_DEFINE_PRINT(fac_alg_factor_norm)
+TIMING_DEFINE_PRINT(fac_alg_gcd)
+TIMING_DEFINE_PRINT(fac_alg_sqrf)
+TIMING_DEFINE_PRINT(fac_alg_factor_sqrf)
+
 // squarefree part of F
 CanonicalForm
@@ -53 +60 @@
   int degmipo= degree (mipo);
   CanonicalForm norm;
+  TIMING_START (fac_alg_resultant);
   if (degg >= 8 || degmipo >= 8)
     norm= resultantZ (g, mipo, x);
   else
     norm= resultant (g, mipo, x);
+  TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ");
 
   i= 0;
@@ -72 +81 @@
         g= F (y - i*alpha, y);
         g *= bCommonDen (g);
+        TIMING_START (fac_alg_resultant);
         if (degg >= 8 || degmipo >= 8)
           norm= resultantZ (g (x, alpha), mipo, x);
         else
           norm= resultant (g (x, alpha), mipo, x);
+        TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant1: ");
       }
       else
@@ -81 +92 @@
         g= F (y + i*alpha, y);
         g *= bCommonDen (g);
+        TIMING_START (fac_alg_resultant);
         if (degg >= 8 || degmipo >= 8)
           norm= resultantZ (g (x, alpha), mipo, x);
         else
           norm= resultant (g (x, alpha), mipo, x);
+        TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant2: ");
       }
       if (degree (gcd (deriv (norm, y), norm)) <= 0)
@@ -108 +121 @@
   CanonicalForm f= F*bCommonDen (F);
   int shift;
+  TIMING_START (fac_alg_norm);
   CanonicalForm norm= sqrfNorm (f, alpha, shift);
+  TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
   ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
+  TIMING_START (fac_alg_factor_norm);
   CFFList normFactors= factorize (norm);
+  TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
   CFList factors;
   if (normFactors.length() <= 2)
@@ -125 +142 @@
   {
     ASSERT (i.getItem().exp() == 1, "norm not squarefree");
+    TIMING_START (fac_alg_gcd);
     if (shift == 0)
       factor= gcd (buf, i.getItem().factor());
@@ -130 +148 @@
       factor= gcd (buf, i.getItem().factor() (f.mvar() + shift*alpha, f.mvar()));
     buf /= factor;
+    TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
     factors.append (factor);
   }
@@ -149 +168 @@
   bool save_rat=!isOn (SW_RATIONAL);
   On (SW_RATIONAL);
+  TIMING_START (fac_alg_sqrf);
   CFFList sqrf= sqrFreeZ (F);
+  TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
   CFList factorsSqrf;
   CFFList factors;
@@ -158 +179 @@
   {
     if (i.getItem().factor().inCoeffDomain()) continue;
+    TIMING_START (fac_alg_factor_sqrf);
     factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
+    TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
+                          "time to factor sqrf factors in Q(a)[x]: ");
     for (j= factorsSqrf; j.hasItem(); j++)
     {

factory/facBivar.cc

@@ -13 +13 @@
 #include "config.h"
 
-#include "assert.h"
+#include "cf_assert.h"
 #include "debug.h"
 #include "timing.h"
@@ -28 +28 @@
 TIMING_DEFINE_PRINT(fac_bi_hensel_lift)
 TIMING_DEFINE_PRINT(fac_bi_factor_recombination)
+TIMING_DEFINE_PRINT(fac_bi_evaluation)
+TIMING_DEFINE_PRINT(fac_bi_shift_to_zero)
 
 // bound on coeffs of f (cf. Musser: Multivariate Polynomial Factorization,
@@ -334 +336 @@
   {
     bufAeval= A;
+    TIMING_START (fac_bi_evaluation);
     bufAeval= evalPoint (A, bufEvaluation);
+    TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
 
     bufAeval2= buf;
+    TIMING_START (fac_bi_evaluation);
     bufAeval2= evalPoint (buf, bufEvaluation2);
+    TIMING_END_AND_PRINT (fac_bi_evaluation,
+                          "time for eval point over Q in y: ");
 
     // univariate factorization
-    TIMING_START (uni_factorize);
-
+    TIMING_START (fac_uni_factorizer);
     if (extension)
       bufUniFactors= conv (factorize (bufAeval, v));
     else
       bufUniFactors= conv (factorize (bufAeval, true));
-    TIMING_END_AND_PRINT (uni_factorize,
-                          "time for univariate factorization: ");
+    TIMING_END_AND_PRINT (fac_uni_factorizer,
+                          "time for univariate factorization over Q: ");
     DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
               (prod (bufUniFactors) == bufAeval));
 
-    TIMING_START (uni_factorize);
+    TIMING_START (fac_uni_factorizer);
     if (extension)
       bufUniFactors2= conv (factorize (bufAeval2, v));
     else
       bufUniFactors2= conv (factorize (bufAeval2, true));
-    TIMING_END_AND_PRINT (uni_factorize,
-                          "time for univariate factorization in y: ");
+    TIMING_END_AND_PRINT (fac_uni_factorizer,
+                          "time for univariate factorization in y over Q: ");
     DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
               (prod (bufUniFactors2) == bufAeval2));
@@ -544 +550 @@
               (A, earlySuccess, earlyFactors, degs, liftBound,
                uniFactors, dummy, evaluation, b);
-  TIMING_END_AND_PRINT (fac_bi_hensel_lift, "time for hensel lifting: ");
+  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
+                        "time for bivariate hensel lifting over Q: ");
   DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
@@ -563 +570 @@
   Off (SW_RATIONAL);
 
+  TIMING_START (fac_bi_factor_recombination);
   factors= factorRecombination (uniFactors, A, MODl, degs, 1,
                                 uniFactors.length()/2, b);
+  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
+                        "time for bivariate factor recombination over Q: ");
 
   On (SW_RATIONAL);

factory/facBivar.h

@@ -14 +14 @@
 #define FAC_BIVAR_H
 
-#include <config.h>
-
-#include "assert.h"
+#include "config.h"
+
+#include "cf_assert.h"
+#include "timing.h"
 
 #include "facFqBivarUtil.h"
@@ -26 +27 @@
 #include "algext.h"
 #include "fac_util.h"
+
+TIMING_DEFINE_PRINT(fac_bi_sqrf)
+TIMING_DEFINE_PRINT(fac_bi_factor_sqrf)
 
 /// @return @a biFactorize returns a list of factors of F. If F is not monic
@@ -196 +200 @@
   vec_ZZ S;
   F= compress (F, M, S);
+  TIMING_START (fac_bi_sqrf);
   CFFList sqrfFactors= sqrFree (F);
+  TIMING_END_AND_PRINT (fac_bi_sqrf,
+                       "time for bivariate sqrf factors over Q: ");
   for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
   {
+    TIMING_START (fac_bi_factor_sqrf);
     CFList tmp= ratBiSqrfFactorize (i.getItem().factor(), v);
+    TIMING_END_AND_PRINT (fac_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over Q: ");
     for (CFListIterator j= tmp; j.hasItem(); j++)
     {

factory/facFactorize.cc

@@ -29 +29 @@
 #include "facSparseHensel.h"
 
-TIMING_DEFINE_PRINT(fac_bi_factorize)
+TIMING_DEFINE_PRINT(fac_bi_factorizer)
 TIMING_DEFINE_PRINT(fac_hensel_lift)
 TIMING_DEFINE_PRINT(fac_factor_recombination)
+TIMING_DEFINE_PRINT(fac_shift_to_zero)
+TIMING_DEFINE_PRINT(fac_precompute_leadcoeff)
+TIMING_DEFINE_PRINT(fac_evaluation)
+TIMING_DEFINE_PRINT(fac_recover_factors)
+TIMING_DEFINE_PRINT(fac_preprocess_and_content)
+TIMING_DEFINE_PRINT(fac_bifactor_total)
+TIMING_DEFINE_PRINT(fac_luckswang)
+TIMING_DEFINE_PRINT(fac_lcheuristic)
+TIMING_DEFINE_PRINT(fac_cleardenom)
+TIMING_DEFINE_PRINT(fac_content)
+TIMING_DEFINE_PRINT(fac_compress)
 
 #ifdef HAVE_NTL
@@ -158 +169 @@
     return CFList (F);
 
+  TIMING_START (fac_preprocess_and_content);
   // compress and find main Variable
   CFMap N;
+  TIMING_START (fac_compress)
   CanonicalForm A= myCompress (F, N);
+  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
 
   //univariate case
@@ -186 +200 @@
 
   // remove content
+  TIMING_START (fac_content);
   CFList contentAi;
   CanonicalForm lcmCont= lcmContent (A, contentAi);
   A /= lcmCont;
+  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
 
   // trivial after content removal
@@ -214 +230 @@
 
   // factorize content
+  TIMING_START (fac_content);
   contentAFactors= multiFactorize (lcmCont, v);
+  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
 
   // univariate after content removal
@@ -230 +248 @@
 
   A *= bCommonDen (A);
-  // check main variable
   CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
   int factorNums= 1;
@@ -241 +258 @@
   int differentSecondVar= 0;
   CanonicalForm bufA;
+  TIMING_END_AND_PRINT (fac_preprocess_and_content,
+                       "time to preprocess poly and extract content over Q: ");
+
   // several bivariate factorizations
+  TIMING_START (fac_bifactor_total);
   REvaluation E (2, A.level(), IntRandom (25));
   for (int i= 0; i < factorNums; i++)
@@ -248 +269 @@
     bufA= A;
     bufAeval= CFList();
+    TIMING_START (fac_evaluation);
     bufEvaluation= evalPoints (bufA, bufAeval, E);
+    TIMING_END_AND_PRINT (fac_evaluation,
+                          "time to find evaluation point over Q: ");
     E.nextpoint();
     evalPoly= 0;
 
+    TIMING_START (fac_evaluation);
     evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
+    TIMING_END_AND_PRINT (fac_evaluation,
+                          "time to eval wrt diff second vars over Q: ");
 
     for (int j= 0; j < lengthAeval2; j++)
@@ -262 +289 @@
     bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
 
-    TIMING_START (fac_bi_factorize);
+    TIMING_START (fac_bi_factorizer);
     bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
-    TIMING_END_AND_PRINT (fac_bi_factorize,
+    TIMING_END_AND_PRINT (fac_bi_factorizer,
                           "time for bivariate factorization: ");
     bufBiFactors.removeFirst();
@@ -316 +343 @@
   int minFactorsLength;
   bool irred= false;
+  TIMING_START (fac_bi_factorizer);
   factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
-
+  TIMING_END_AND_PRINT (fac_bi_factorizer,
+             "time for bivariate factorization wrt diff second vars over Q: ");
+
+  TIMING_END_AND_PRINT (fac_bifactor_total,
+                        "total time for eval and bivar factors over Q: ");
   if (irred)
   {
@@ -376 +408 @@
 
   Variable w;
+  TIMING_START (fac_precompute_leadcoeff);
   CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
                                           evaluation, Aeval2, lengthAeval2, w);
@@ -477 +510 @@
     }
   }
+  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
+                       "time to precompute LC over Q: ");
+
+  TIMING_START (fac_luckswang);
   CFList bufFactors= CFList();
   bool LCheuristic= false;
@@ -499 +536 @@
       delete [] index;
       delete [] Aeval2;
+      TIMING_END_AND_PRINT (fac_luckswang,
+                            "time for successful LucksWang over Q: ");
       return factors;
     }
@@ -837 +876 @@
     delete [] index;
   }
+  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
+
+  TIMING_START (fac_lcheuristic);
   if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
       && fdivides (getVars (LCmultiplier), testVars))
@@ -986 +1028 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
 
 tryAgainWithoutHeu:
   //shifting to zero
+  TIMING_START (fac_shift_to_zero);
   A= shift2Zero (A, Aeval, evaluation);
 
@@ -1007 +1051 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_shift_to_zero,
+                        "time to shift evaluation point to zero: ");
 
   CFArray Pi;
@@ -1018 +1064 @@
   bool noOneToOne= false;
 
+  TIMING_START (fac_cleardenom);
   CFList commonDenominators;
   for (iter=biFactors; iter.hasItem(); iter++)
@@ -1056 +1103 @@
       iter.getItem() *= iter2.getItem()*multiplier;
   }
-
-
+  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
+
+  TIMING_START (fac_hensel_lift);
   factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
                                Pi, liftBounds, liftBoundsLength, noOneToOne);
+  TIMING_END_AND_PRINT (fac_hensel_lift,
+                        "time for non monic hensel lifting over Q: ");
 
   if (!noOneToOne)
@@ -1065 +1115 @@
     int check= factors.length();
     A= oldA;
+    TIMING_START (fac_recover_factors);
     factors= recoverFactors (A, factors, evaluation);
+    TIMING_END_AND_PRINT (fac_recover_factors,
+                          "time to recover factors over Q: ");
     if (check != factors.length())
       noOneToOne= true;

factory/facFactorize.h

@@ -14 +14 @@
 #define FAC_FACTORIZE_H
 
-// #include "config.h"
+#include "config.h"
+#include "timing.h"
 
 #include "facBivar.h"
 #include "facFqBivarUtil.h"
+
+TIMING_DEFINE_PRINT (fac_squarefree)
+TIMING_DEFINE_PRINT (fac_factor_squarefree)
 
 /// Factorization over Q (a)
@@ -120 +124 @@
 
   CFFList result;
+  TIMING_START (fac_squarefree);
   CFFList sqrfFactors= sqrFree (F);
+  TIMING_END_AND_PRINT (fac_squarefree,
+                        "time for squarefree factorization over Q: ");
+
+  CFList tmp;
   for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
   {
-    CFList tmp= ratSqrfFactorize (i.getItem().factor(), v);
+    TIMING_START (fac_factor_squarefree);
+    tmp= ratSqrfFactorize (i.getItem().factor(), v);
+    TIMING_END_AND_PRINT (fac_factor_squarefree,
+                          "time to factorize sqrfree factor over Q: ");
     for (CFListIterator j= tmp; j.hasItem(); j++)
     {

factory/facFqBivar.cc

@@ -46 +46 @@
 TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift)
 TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination)
+TIMING_DEFINE_PRINT(fac_fq_bi_evaluation)
+TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero)
 
 CanonicalForm prodMod0 (const CFList& L, const CanonicalForm& M, const modpk& b)
@@ -6082 +6084 @@
   {
     bufAeval= A;
+    TIMING_START (fac_fq_bi_evaluation);
     bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
+    TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
     if (!derivXZero && !fail2 && !symmetric)
     {
@@ -6091 +6095 @@
       }
       bufAeval2= buf;
+      TIMING_START (fac_fq_bi_evaluation);
       bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
+      TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
+                            "time to find eval point wrt y: ");
     }
     // first try to change main variable if there is no valid evaluation point
@@ -6132 +6139 @@
     bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
     TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
-                          "time for univariate factorization: ");
+                          "time for univariate factorization over Fq: ");
     DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
               (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
@@ -6141 +6148 @@
       bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
       TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
-                            "time for univariate factorization in y: ");
+                            "time for univariate factorization in y over Fq: ");
       DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
                 (prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
@@ -6291 +6298 @@
   }
 
+  TIMING_START (fac_fq_bi_shift_to_zero);
   A= A (y + evaluation, y);
+  TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
+                        "time to shift eval to zero: ");
 
   int degMipo= 1;
@@ -6307 +6317 @@
                (A, earlySuccess, earlyFactors, degs, liftBound,
                 uniFactors, info, evaluation);
-    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                          "time for bivariate hensel lifting over Fq: ");
     DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
     CanonicalForm MODl= power (y, liftBound);
 
+    TIMING_START (fac_fq_bi_factor_recombination);
     if (extension)
       factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
@@ -6318 +6330 @@
       factors= factorRecombination (uniFactors, A, MODl, degs, 1,
                                     uniFactors.length()/2);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
+                          "time for naive bivariate factor recombi over Fq: ");
 
     if (earlySuccess)
@@ -6346 +6360 @@
       factors= Union (lll, factors);
     }
-    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                          "time to bivar lift and LLL recombi over Fq: ");
     DEBOUTLN (cerr, "lifted factors= " << uniFactors);
   }
@@ -6357 +6372 @@
                (A, earlySuccess, earlyFactors, degs, liftBound,
                 uniFactors, info, evaluation);
-    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                          "time for bivar hensel lifting over Fq: ");
     DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
@@ -6363 +6379 @@
     if (!extension)
     {
+      TIMING_START (fac_fq_bi_factor_recombination);
       factors= factorRecombination (uniFactors, A, MODl, degs, 1, 3);
+      TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
+                            "time for small subset naive recombi over Fq: ");
 
       int oldUniFactorsLength= uniFactors.length();
@@ -6369 +6388 @@
       {
         CFList tmp;
+        TIMING_START (fac_fq_bi_hensel_lift);
         if (alpha.level() == 1)
           tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
@@ -6384 +6404 @@
                                    );
         }
+        TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
+                              "time to increase precision: ");
         factors= Union (factors, tmp);
         if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0

factory/facFqBivar.h

@@ -15 +15 @@
 #define FAC_FQ_BIVAR_H
 
-// #include "config.h"
-
+ #include "config.h"
+
+#include "timing.h"
 #include "cf_assert.h"
 
@@ -26 +27 @@
 #include "cf_map.h"
 #include "cfNewtonPolygon.h"
+
+TIMING_DEFINE_PRINT(fac_fq_bi_sqrf)
+TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf)
 
 static const double log2exp= 1.442695041;
@@ -273 +277 @@
   F= compress (F, M, S);
 
+  TIMING_START (fac_fq_bi_sqrf);
   CFFList sqrf= FpSqrf (F, false);
+  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
+                       "time for bivariate sqrf factors over Fp: ");
   CFList bufResult;
   sqrf.removeFirst();
@@ -279 +286 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_bi_factor_sqrf);
     bufResult= biFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over Fp: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (N (decompress (i.getItem(), M, S)),
@@ -374 +384 @@
   F= compress (F, M, S);
 
+  TIMING_START (fac_fq_bi_sqrf);
   CFFList sqrf= FqSqrf (F, alpha, false);
+  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
+                       "time for bivariate sqrf factors over Fq: ");
   CFList bufResult;
   sqrf.removeFirst();
@@ -380 +393 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_bi_factor_sqrf);
     bufResult= biFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over Fq: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (N (decompress (i.getItem(), M, S)),
@@ -476 +492 @@
   F= compress (F, M, S);
 
+  TIMING_START (fac_fq_bi_sqrf);
   CFFList sqrf= GFSqrf (F, false);
+  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
+                       "time for bivariate sqrf factors over GF: ");
   CFList bufResult;
   sqrf.removeFirst();
@@ -482 +501 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_bi_factor_sqrf);
     bufResult= biFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
+                          "time to factor bivariate sqrf factors over GF: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (N (decompress (i.getItem(), M, S)),

factory/facFqFactorize.cc

@@ -38 +38 @@
 TIMING_DEFINE_PRINT(fac_fq_hensel_lift)
 TIMING_DEFINE_PRINT(fac_fq_factor_recombination)
+TIMING_DEFINE_PRINT(fac_fq_shift_to_zero)
+TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff)
+TIMING_DEFINE_PRINT(fac_fq_evaluation)
+TIMING_DEFINE_PRINT(fac_fq_recover_factors)
+TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content)
+TIMING_DEFINE_PRINT(fac_fq_bifactor_total)
+TIMING_DEFINE_PRINT(fac_fq_luckswang)
+TIMING_DEFINE_PRINT(fac_fq_lcheuristic)
+TIMING_DEFINE_PRINT(fac_fq_content)
+TIMING_DEFINE_PRINT(fac_fq_check_mainvar)
+TIMING_DEFINE_PRINT(fac_fq_compress)
 
 static inline
@@ -2196 +2207 @@
     return CFList (F);
 
+  TIMING_START (fac_fq_preprocess_and_content);
   // compress and find main Variable
   CFMap N;
+  TIMING_START (fac_fq_compress)
   CanonicalForm A= myCompress (F, N);
+  TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
 
   A /= Lc (A); // make monic
@@ -2232 +2246 @@
 
   // remove content
+  TIMING_START (fac_fq_content);
   CFList contentAi;
   CanonicalForm lcmCont= lcmContent (A, contentAi);
   A /= lcmCont;
+  TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
 
   // trivial after content removal
@@ -2260 +2276 @@
 
   // factorize content
+  TIMING_START (fac_fq_content);
   contentAFactors= multiFactorize (lcmCont, info);
+  TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
 
   // univariate after content removal
@@ -2273 +2291 @@
 
   // check main variable
+  TIMING_START (fac_fq_check_mainvar);
   int swapLevel= 0;
   CanonicalForm derivZ;
@@ -2315 +2334 @@
     }
   }
-
+  TIMING_END_AND_PRINT (fac_fq_check_mainvar,
+                        "time to check main var over Fq: ");
+  TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
+                       "time to preprocess poly and extract content over Fq: ");
 
   CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
@@ -2335 +2357 @@
   int differentSecondVar= 0;
   // several bivariate factorizations
+  TIMING_START (fac_fq_bifactor_total);
   for (int i= 0; i < factorNums; i++)
   {
@@ -2340 +2363 @@
     bufA= A;
     bufAeval= CFList();
+    TIMING_START (fac_fq_evaluation);
     bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
+    TIMING_END_AND_PRINT (fac_fq_evaluation,
+                          "time to find evaluation point over Fq: ");
     evalPoly= 0;
 
@@ -2385 +2411 @@
       break;
 
+    TIMING_START (fac_fq_evaluation);
     evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
+    TIMING_END_AND_PRINT (fac_fq_evaluation,
+                          "time for evaluation wrt diff second vars over Fq: ");
 
     for (int j= 0; j < lengthAeval2; j++)
@@ -2460 +2489 @@
   int minFactorsLength;
   bool irred= false;
+  TIMING_START (fac_fq_bi_factorizer);
   factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
-
+  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
+             "time for bivariate factorization wrt diff second vars over Fq: ");
+
+  TIMING_END_AND_PRINT (fac_fq_bifactor_total,
+                        "total time for eval and bivar factors over Fq: ");
   if (irred)
   {
@@ -2532 +2566 @@
 
   Variable v;
+  TIMING_START (fac_fq_precompute_leadcoeff);
   CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
                                           evaluation, Aeval2, lengthAeval2, v);
@@ -2631 +2666 @@
     }
   }
+  TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
+                       "time to precompute LC over Fq: ");
+
+  TIMING_START (fac_fq_luckswang);
   CFList bufFactors= CFList();
   bool LCheuristic= false;
@@ -2658 +2697 @@
       delete [] index;
       delete [] Aeval2;
+      TIMING_END_AND_PRINT (fac_fq_luckswang,
+                            "time for successful LucksWang over Fq: ");
       return factors;
     }
@@ -2997 +3038 @@
     delete [] index;
   }
-
+  TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
+
+  TIMING_START (fac_fq_lcheuristic);
   if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
       && fdivides (getVars (LCmultiplier), testVars))
@@ -3147 +3190 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
 
 tryAgainWithoutHeu:
+  TIMING_START (fac_fq_shift_to_zero);
   A= shift2Zero (A, Aeval, evaluation);
 
@@ -3167 +3212 @@
     }
   }
+  TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
+                        "time to shift evaluation point to zero: ");
 
   CFArray Pi;
@@ -3177 +3224 @@
   Aeval.removeFirst();
   bool noOneToOne= false;
+  TIMING_START (fac_fq_hensel_lift);
   factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
                                Pi, liftBounds, liftBoundsLength, noOneToOne);
+  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
+                        "time for non monic hensel lifting over Fq: ");
 
   if (!noOneToOne)
@@ -3184 +3234 @@
     int check= factors.length();
     A= oldA;
+    TIMING_START (fac_fq_recover_factors);
     factors= recoverFactors (A, factors, evaluation);
+    TIMING_END_AND_PRINT (fac_fq_recover_factors,
+                          "time to recover factors over Fq: ");
     if (check != factors.length())
       noOneToOne= true;
@@ -3243 +3296 @@
                    (A, MOD, liftBounds, earlySuccess, earlyFactors,
                     Aeval, biFactors, evaluation, info);
-    TIMING_END_AND_PRINT (fac_fq_hensel_lift, "time for hensel lifting: ");
+    TIMING_END_AND_PRINT (fac_fq_hensel_lift,
+                          "time for hensel lifting over Fq: ");
 
     if (!extension)

factory/facFqFactorize.h

@@ -15 +15 @@
 #define FAC_FQ_FACTORIZE_H
 
-// #include "config.h"
+#include "config.h"
+#include "timing.h"
 
 #include "facFqBivar.h"
@@ -23 +24 @@
 #include "facFqSquarefree.h"
 #include "facFqBivarUtil.h"
+
+
+TIMING_DEFINE_PRINT (fac_fq_squarefree)
+TIMING_DEFINE_PRINT (fac_fq_factor_squarefree)
 
 /// Factorization over a finite field
@@ -150 +155 @@
   Variable a= Variable (1);
   CanonicalForm LcF= Lc (F);
+  TIMING_START (fac_fq_squarefree);
   CFFList sqrf= FpSqrf (F, false);
+  TIMING_END_AND_PRINT (fac_fq_squarefree,
+                        "time for squarefree factorization over Fq: ");
   CFFList result;
   CFList bufResult;
@@ -157 +165 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_factor_squarefree);
     bufResult= multiFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
+                          "time to factorize sqrfree factor over Fq: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (i.getItem(), iter.getItem().exp()));
@@ -227 +238 @@
   ExtensionInfo info= ExtensionInfo (alpha, false);
   CanonicalForm LcF= Lc (F);
+  TIMING_START (fac_fq_squarefree);
   CFFList sqrf= FqSqrf (F, alpha, false);
+  TIMING_END_AND_PRINT (fac_fq_squarefree,
+                        "time for squarefree factorization over Fq: ");
   CFFList result;
   CFList bufResult;
@@ -234 +248 @@
   for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
   {
+    TIMING_START (fac_fq_factor_squarefree);
     bufResult= multiFactorize (iter.getItem().factor(), info);
+    TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
+                          "time to factorize sqrfree factor over Fq: ");
     for (i= bufResult; i.hasItem(); i++)
       result.append (CFFactor (i.getItem(), iter.getItem().exp()));