Changeset b30017 in git for factory/facFqFactorize.cc


Ignore:
Timestamp:
Aug 22, 2012, 11:16:18 AM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
903f87563d5c7fb02893c3f85c6e728757b7106b
Parents:
c89740c263a7f55af9bd2cdbff4e77573d7eb82e
git-author:
Martin Lee <martinlee84@web.de>2012-08-22 11:16:18+02:00
git-committer:
Martin Lee <martinlee84@web.de>2012-09-04 18:01:19+02:00
Message:
chg: added heuristics to distribute leading coeff to finite field case
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/facFqFactorize.cc

    rc89740 rb30017  
    25932593  CFList bufFactors= CFList();
    25942594  bool LCheuristic= false;
    2595   if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2 [lengthAeval2-1],
     2595  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
    25962596                                 factors))
    25972597  {
    … …  
    26042604    {
    26052605      if (extension)
    2606         factors= extNonMonicFactorRecombination (factors, bufA, info);       //TODO brauche hier ein bufA statt A
     2606        factors= extNonMonicFactorRecombination (factors, bufA, info);
    26072607
    26082608      if (v.level() != 1)
    … …  
    26462646      factors= CFList();
    26472647    }
     2648    else if (!LCmultiplierIsConst && factors.length() == 0)
     2649    {
     2650      LCheuristic= true;
     2651      factors= oldFactors;
     2652      CanonicalForm cont;
     2653      CFList contents, LCs;
     2654      int index=1;
     2655      bool foundTrueMultiplier= false;
     2656      for (iter= factors; iter.hasItem(); iter++, index++)
     2657      {
     2658        cont= content (iter.getItem(), 1);
     2659        cont= gcd (cont , LCmultiplier);
     2660        contents.append (cont);
     2661        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
     2662        {
     2663          foundTrueMultiplier= true;
     2664          int index2= 1;
     2665          for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
     2666                                                                    index2++)
     2667          {
     2668            if (index2 == index)
     2669              continue;
     2670            iter2.getItem() /= LCmultiplier;
     2671          }
     2672          A= oldA;
     2673          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
     2674          for (int i= lengthAeval2-1; i > -1; i--)
     2675            leadingCoeffs2[i]= CFList();
     2676          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
     2677                                biFactors, evaluation );
     2678          Aeval= evaluateAtEval (A, evaluation, 2);
     2679
     2680          hh= Lc (Aeval.getFirst());
     2681
     2682          for (iter2= Aeval; iter2.hasItem(); iter2++)
     2683            iter2.getItem() /= hh;
     2684
     2685          A /= hh;
     2686          break;
     2687        }
     2688        else
     2689          LCs.append (LC (iter.getItem()/cont, 1));
     2690      }
     2691      if (!foundTrueMultiplier)
     2692      {
     2693        index= 1;
     2694        iter2= factors;
     2695        bool foundMultiplier= false;
     2696        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
     2697        {
     2698          if (fdivides (iter.getItem(), LCmultiplier))
     2699          {
     2700            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
     2701                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
     2702            {
     2703              int index2= 1;
     2704              for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
     2705                   iter3.hasItem(); iter3++, index2++)
     2706              {
     2707                if (index2 == index)
     2708                {
     2709                  iter3.getItem() /= LCmultiplier;
     2710                  break;
     2711                }
     2712              }
     2713              A /= LCmultiplier;
     2714              foundMultiplier= true;
     2715              iter.getItem()= 1;
     2716            }
     2717          }
     2718        }
     2719        // coming from above: divide out more LCmultiplier if possible
     2720        if (foundMultiplier)
     2721        {
     2722          foundMultiplier= false;
     2723          index=1;
     2724          iter2= factors;
     2725          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
     2726          {
     2727            if (!iter.getItem().isOne() &&
     2728                fdivides (iter.getItem(), LCmultiplier))
     2729            {
     2730              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
     2731              {
     2732                int index2= 1;
     2733                for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
     2734                     iter2++, index2++)
     2735                {
     2736                  if (index2 == index)
     2737                  {
     2738                    iter2.getItem() /= iter.getItem();
     2739                    foundMultiplier= true;
     2740                    break;
     2741                  }
     2742                }
     2743                A /= iter.getItem();
     2744                LCmultiplier /= iter.getItem();
     2745                iter.getItem()= 1;
     2746              }
     2747              else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
     2748              {
     2749                //TODO maybe use a sqrffree decomposition of LCmultiplier as below
     2750                Variable xx= Variable (2);
     2751                CanonicalForm vars;
     2752                vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
     2753                                          xx));
     2754                for (int i= 0; i < lengthAeval2; i++)
     2755                {
     2756                  if (oldAeval[i].isEmpty())
     2757                    continue;
     2758                  xx= oldAeval[i].getFirst().mvar();
     2759                  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
     2760                                             xx));
     2761                }
     2762                if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
     2763                    /myGetVars (LCmultiplier) == vars)
     2764                {
     2765                  int index2= 1;
     2766                  for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
     2767                       iter2++, index2++)
     2768                  {
     2769                    if (index2 == index)
     2770                    {
     2771                      iter2.getItem() /= LCmultiplier;
     2772                      foundMultiplier= true;
     2773                      break;
     2774                    }
     2775                  }
     2776                  A /= LCmultiplier;
     2777                  iter.getItem()= 1;
     2778                }
     2779              }
     2780            }
     2781          }
     2782        }
     2783        else
     2784        {
     2785          CanonicalForm pLCs= prod (LCs);
     2786          if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
     2787          {
     2788            A= oldA;
     2789            iter2= leadingCoeffs2[lengthAeval2-1];
     2790            for (iter= contents; iter.hasItem(); iter++, iter2++)
     2791              iter2.getItem() /= iter.getItem();
     2792            foundMultiplier= true;
     2793          }
     2794          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
     2795          {
     2796            Variable xx;
     2797            CFList vars1;
     2798            CFFList sqrfMultiplier= sqrFree (LCmultiplier);
     2799            if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
     2800              sqrfMultiplier.removeFirst();
     2801            sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
     2802            xx= Variable (2);
     2803            for (iter= oldBiFactors; iter.hasItem(); iter++)
     2804              vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
     2805            for (int i= 0; i < lengthAeval2; i++)
     2806            {
     2807              if (oldAeval[i].isEmpty())
     2808                continue;
     2809              xx= oldAeval[i].getFirst().mvar();
     2810              iter2= vars1;
     2811              for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
     2812                iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
     2813            }
     2814            CanonicalForm tmp;
     2815            iter2= vars1;
     2816            for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
     2817                                                                    iter2++)
     2818            {
     2819              tmp= iter.getItem()/LCmultiplier;
     2820              for (int i=1; i <= tmp.level(); i++)
     2821              {
     2822                if (degree (tmp, i) > 0)
     2823                  iter2.getItem() /= power (Variable (i), degree (tmp,i));
     2824              }
     2825            }
     2826            int multi;
     2827            for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
     2828            {
     2829              multi= 0;
     2830              for (iter= vars1; iter.hasItem(); iter++)
     2831              {
     2832                tmp= iter.getItem();
     2833                while (fdivides (myGetVars (ii.getItem().factor()), tmp))
     2834                {
     2835                  multi++;
     2836                  tmp /= myGetVars (ii.getItem().factor());
     2837                }
     2838              }
     2839              if (multi == ii.getItem().exp())
     2840              {
     2841                index= 1;
     2842                for (iter= vars1; iter.hasItem(); iter++, index++)
     2843                {
     2844                  while (fdivides (myGetVars(ii.getItem().factor()),
     2845                                   iter.getItem()
     2846                                  )
     2847                        )
     2848                  {
     2849                    int index2= 1;
     2850                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
     2851                         iter2++, index2++)
     2852                    {
     2853                      if (index2 == index)
     2854                        continue;
     2855                      else
     2856                      {
     2857                        tmp= ii.getItem().factor();
     2858                        iter2.getItem() /= tmp;
     2859                        CFListIterator iter3= evaluation;
     2860                        for (int jj= A.level(); jj > 2; jj--, iter3++)
     2861                          tmp= tmp (iter3.getItem(), jj);
     2862                        if (!tmp.inCoeffDomain())
     2863                        {
     2864                          int index3= 1;
     2865                          for (iter3= biFactors; iter3.hasItem(); iter3++,
     2866                                                                  index3++)
     2867                          {
     2868                            if (index3 == index2)
     2869                            {
     2870                              iter3.getItem() /= tmp;
     2871                              iter3.getItem() /= Lc (iter3.getItem());
     2872                              break;
     2873                            }
     2874                          }
     2875                        }
     2876                        A /= ii.getItem().factor();
     2877                      }
     2878                    }
     2879                    iter.getItem() /= getVars (ii.getItem().factor());
     2880                  }
     2881                }
     2882              }
     2883              else
     2884              {
     2885                index= 1;
     2886                for (iter= vars1; iter.hasItem(); iter++, index++)
     2887                {
     2888                  if (!fdivides (myGetVars (ii.getItem().factor()),
     2889                                 iter.getItem()
     2890                                )
     2891                     )
     2892                  {
     2893                    int index2= 1;
     2894                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
     2895                         iter2++, index2++)
     2896                    {
     2897                      if (index2 == index)
     2898                      {
     2899                        tmp= power (ii.getItem().factor(), ii.getItem().exp());
     2900                        iter2.getItem() /= tmp;
     2901                        A /= tmp;
     2902                        CFListIterator iter3= evaluation;
     2903                        for (int jj= A.level(); jj > 2; jj--, iter3++)
     2904                          tmp= tmp (iter3.getItem(), jj);
     2905                        if (!tmp.inCoeffDomain())
     2906                        {
     2907                          int index3= 1;
     2908                          for (iter3= biFactors; iter3.hasItem(); iter3++,
     2909                                                                  index3++)
     2910                          {
     2911                            if (index3 == index2)
     2912                            {
     2913                              iter3.getItem() /= tmp;
     2914                              iter3.getItem() /= Lc (iter3.getItem());
     2915                              break;
     2916                            }
     2917                          }
     2918                        }
     2919                      }
     2920                    }
     2921                  }
     2922                }
     2923              }
     2924            }
     2925          }
     2926        }
     2927
     2928        // patch everything together again
     2929        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
     2930        for (int i= lengthAeval2-1; i > -1; i--)
     2931          leadingCoeffs2[i]= CFList();
     2932        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
     2933                              evaluation);
     2934        Aeval= evaluateAtEval (A, evaluation, 2);
     2935
     2936        hh= Lc (Aeval.getFirst());
     2937
     2938        for (CFListIterator i= Aeval; i.hasItem(); i++)
     2939          i.getItem() /= hh;
     2940
     2941        A /= hh;
     2942      }
     2943      factors= CFList();
     2944      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
     2945      {
     2946        LCheuristic= false;
     2947        A= bufA;
     2948        biFactors= bufBiFactors;
     2949        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
     2950        LCmultiplier= bufLCmultiplier;
     2951      }
     2952    }
    26482953    else
    26492954      factors= CFList();
    … …  
    26512956  }
    26522957
     2958  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
     2959      && fdivides (getVars (LCmultiplier), testVars))
     2960  {
     2961    int index;
     2962    Variable xx;
     2963    CFList vars1;
     2964    CFFList sqrfMultiplier= sqrFree (LCmultiplier);
     2965    if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
     2966      sqrfMultiplier.removeFirst();
     2967    sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
     2968    xx= Variable (2);
     2969    for (iter= oldBiFactors; iter.hasItem(); iter++)
     2970      vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
     2971    for (int i= 0; i < lengthAeval2; i++)
     2972    {
     2973      if (oldAeval[i].isEmpty())
     2974        continue;
     2975      xx= oldAeval[i].getFirst().mvar();
     2976      iter2= vars1;
     2977      for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
     2978        iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
     2979    }
     2980    CanonicalForm tmp;
     2981    iter2= vars1;
     2982    for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
     2983    {
     2984      tmp= iter.getItem()/LCmultiplier;
     2985      for (int i=1; i <= tmp.level(); i++)
     2986      {
     2987        if (degree (tmp, i) > 0)
     2988          iter2.getItem() /= power (Variable (i), degree (tmp,i));
     2989      }
     2990    }
     2991    int multi;
     2992    for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
     2993    {
     2994      multi= 0;
     2995      for (iter= vars1; iter.hasItem(); iter++)
     2996      {
     2997        tmp= iter.getItem();
     2998        while (fdivides (myGetVars (ii.getItem().factor()), tmp))
     2999        {
     3000          multi++;
     3001          tmp /= myGetVars (ii.getItem().factor());
     3002        }
     3003      }
     3004      if (multi == ii.getItem().exp())
     3005      {
     3006        index= 1;
     3007        for (iter= vars1; iter.hasItem(); iter++, index++)
     3008        {
     3009          while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
     3010          {
     3011            int index2= 1;
     3012            for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();iter2++,
     3013                                                                      index2++)
     3014            {
     3015              if (index2 == index)
     3016                continue;
     3017              else
     3018              {
     3019                tmp= ii.getItem().factor();
     3020                iter2.getItem() /= tmp;
     3021                CFListIterator iter3= evaluation;
     3022                for (int jj= A.level(); jj > 2; jj--, iter3++)
     3023                  tmp= tmp (iter3.getItem(), jj);
     3024                if (!tmp.inCoeffDomain())
     3025                {
     3026                  int index3= 1;
     3027                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
     3028                  {
     3029                    if (index3 == index2)
     3030                    {
     3031                      iter3.getItem() /= tmp;
     3032                      iter3.getItem() /= Lc (iter3.getItem());
     3033                      break;
     3034                    }
     3035                  }
     3036                }
     3037                A /= ii.getItem().factor();
     3038              }
     3039            }
     3040            iter.getItem() /= getVars (ii.getItem().factor());
     3041          }
     3042        }
     3043      }
     3044      else
     3045      {
     3046        index= 1;
     3047        for (iter= vars1; iter.hasItem(); iter++, index++)
     3048        {
     3049          if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
     3050          {
     3051            int index2= 1;
     3052            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
     3053                                                                      index2++)
     3054            {
     3055              if (index2 == index)
     3056              {
     3057                tmp= power (ii.getItem().factor(), ii.getItem().exp());
     3058                iter2.getItem() /= tmp;
     3059                A /= tmp;
     3060                CFListIterator iter3= evaluation;
     3061                for (int jj= A.level(); jj > 2; jj--, iter3++)
     3062                  tmp= tmp (iter3.getItem(), jj);
     3063                if (!tmp.inCoeffDomain())
     3064                {
     3065                  int index3= 1;
     3066                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
     3067                  {
     3068                    if (index3 == index2)
     3069                    {
     3070                      iter3.getItem() /= tmp;
     3071                      iter3.getItem() /= Lc (iter3.getItem());
     3072                      break;
     3073                    }
     3074                  }
     3075                }
     3076              }
     3077            }
     3078          }
     3079        }
     3080      }
     3081    }
     3082
     3083    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
     3084    for (int i= lengthAeval2-1; i > -1; i--)
     3085      leadingCoeffs2[i]= CFList();
     3086    prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
     3087                          evaluation);
     3088    Aeval= evaluateAtEval (A, evaluation, 2);
     3089
     3090    hh= Lc (Aeval.getFirst());
     3091
     3092    for (CFListIterator i= Aeval; i.hasItem(); i++)
     3093      i.getItem() /= hh;
     3094
     3095    A /= hh;
     3096  }
     3097
     3098tryAgainWithoutHeu:
    26533099  A= shift2Zero (A, Aeval, evaluation);
    26543100
    … …  
    26973143  if (noOneToOne)
    26983144  {
     3145
     3146    if (!LCmultiplierIsConst && LCheuristic)
     3147    {
     3148      A= bufA;
     3149      biFactors= bufBiFactors;
     3150      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
     3151      delete [] liftBounds;
     3152      LCheuristic= false;
     3153      goto tryAgainWithoutHeu;
     3154      //something probably went wrong in the heuristic
     3155    }
     3156
    26993157    A= shift2Zero (oldA, Aeval, evaluation);
    27003158    biFactors= oldBiFactors;
Note: See TracChangeset for help on using the changeset viewer.