Changeset c6d3744 in git for factory/fac_multivar.cc


Ignore:
Timestamp:
Jan 22, 2008, 10:29:56 AM (16 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
ef9d6b431bfae763ec3be1cc7fa8a7ff3a44d0d3
Parents:
a8107357ac68111e1051981bf688474782ef2671
Message:
*hannes: work in progress


git-svn-id: file:///usr/local/Singular/svn/trunk@10517 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/fac_multivar.cc

    ra81073 rc6d3744  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: fac_multivar.cc,v 1.12 2005-08-22 17:24:02 Singular Exp $ */
     2/* $Id: fac_multivar.cc,v 1.13 2008-01-22 09:29:56 Singular Exp $ */
    33
    44#include <config.h>
    … …  
    2121
    2222void out_cf(char *s1,const CanonicalForm &f,char *s2);
     23void out_cff(CFFList &L);
    2324
    2425TIMING_DEFINE_PRINT(fac_content);
    … …  
    118119    if ( r > 0 )
    119120        A.nextpoint();
    120     while ( ! found ) {
     121    while ( ! found )
     122    {
    121123        Vn = A( V );
    122         if ( Vn != 0 ) {
     124        if ( Vn != 0 )
     125        {
    123126            U0 = A( U );
    124127            DEBOUTLN( cerr, "U0 = " << U0 );
    125             if ( isSqrFree( U0 ) ) {
     128            if ( isSqrFree( U0 ) )
     129            {
    126130                delta = content( U0 );
    127131                DEBOUTLN( cerr, "content( U0 ) = " << delta );
    … …  
    130134                found = nonDivisors( omega, delta, FF, D );
    131135            }
    132             else {
     136            else
     137            {
    133138                DEBOUTLN( cerr, "not sqrfree : " << sqrFree( U0 ) );
    134139            }
    … …  
    191196#endif
    192197
    193 static CFArray
    194 ZFactorizeMulti ( const CanonicalForm & arg )
     198static CFArray ZFactorizeMulti ( const CanonicalForm & arg )
    195199{
    196200    DEBINCLEVEL( cerr, "ZFactorizeMulti" );
    … …  
    217221
    218222    maxdeg = 0;
    219     for ( i = 2; i <= t; i++ ) {
     223    for ( i = 2; i <= t; i++ )
     224    {
    220225        j = U.degree( Variable( i ) );
    221226        if ( j > maxdeg ) maxdeg = j;
    222227    }
    223228
    224     if ( F.getFirst().factor().inCoeffDomain() ) {
     229    if ( F.getFirst().factor().inCoeffDomain() )
     230    {
    225231        omega = F.getFirst().factor();
    226232        F.removeFirst();
    227         if ( omega < 0 ) {
     233        if ( omega < 0 )
     234        {
    228235            negate = true;
    229236            omega = -omega;
    … …  
    240247//        A.nextpoint();
    241248
    242     while ( ! goodeval ) {
     249    while ( ! goodeval )
     250    {
    243251        TIMING_START(fac_findeval);
    244252        findEvaluation( U, V, omega, F, A, U0, delta, D, r );
    … …  
    254262        {
    255263          int i=prime_number;
    256           find_good_prime(arg,i);
    257           find_good_prime(U0,i);
    258           find_good_prime(U,i);
    259           int p=cf_getSmallPrime(i);
    260           //printf("found:p=%d (%d)\n",p,i);
    261           if ((i==0)||(i!=prime_number))
    262           { 
     264          find_good_prime(arg,i);
     265          find_good_prime(U0,i);
     266          find_good_prime(U,i);
     267          int p=cf_getSmallPrime(i);
     268          //printf("found:p=%d (%d)\n",p,i);
     269          if ((i==0)||(i!=prime_number))
     270          {
    263271            b = coeffBound( U, p );
    264             prime_number=i;
    265           } 
    266           modpk bb=coeffBound(U0,p);
    267           if (bb.getk() > b.getk() ) b=bb;
    268           bb=coeffBound(arg,p);
    269           if (bb.getk() > b.getk() ) b=bb;
     272            prime_number=i;
     273          }
     274          modpk bb=coeffBound(U0,p);
     275          if (bb.getk() > b.getk() ) b=bb;
     276          bb=coeffBound(arg,p);
     277          if (bb.getk() > b.getk() ) b=bb;
    270278        }
    271279        #else
    … …  
    274282            b = getZFacModulus();
    275283        #endif
    276         //printf("p=%d, k=%d\n",b.getp(),b.getk());
     284        //printf("p=%d, k=%d\n",b.getp(),b.getk());
    277285        DEBOUTLN( cerr, "the coefficient bound of the factors of U is " << b.getpk() );
    278286
    … …  
    285293        TIMING_END(fac_distrib);
    286294#ifdef DEBUGOUTPUT
    287         if ( goodeval ) {
     295        if ( goodeval )
     296        {
    288297            DEBOUTLN( cerr, "the univariate factors after distribution are " << G );
    289298            DEBOUTLN( cerr, "the distributed leading coeffs are " << lcG );
    … …  
    291300            DEBOUTLN( cerr, "which has leading coefficient " << LC( UU, Variable(1) ) );
    292301
    293             if ( LC( UU, Variable(1) ) != prod( lcG ) || A(UU) != prod( G ) ) {
     302            if ( LC( UU, Variable(1) ) != prod( lcG ) || A(UU) != prod( G ) )
     303            {
    294304                DEBOUTLN( cerr, "!!! distribution was not correct !!!" );
    295305                DEBOUTLN( cerr, "product of leading coeffs is " << prod( lcG ) );
    … …  
    300310                DEBOUTLN( cerr, "leading coeffs correct" );
    301311        }
    302         else {
     312        else
     313        {
    303314            DEBOUTLN( cerr, "we have found a bad evaluation point" );
    304315        }
    305316#endif
    306         if ( goodeval ) {
     317        if ( goodeval )
     318        {
    307319            TIMING_START(fac_hensel);
    308320            goodeval = Hensel( UU, G, lcG, A, b, Variable(1) );
    … …  
    310322        }
    311323    }
    312     for ( i = 1; i <= r; i++ ) {
     324    for ( i = 1; i <= r; i++ )
     325    {
    313326        G[i] /= icontent( G[i] );
    314327        G[i] = M(G[i]);
    … …  
    321334}
    322335
    323 CFFList
    324 ZFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree )
     336CFFList ZFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree )
    325337{
    326338    CFFList G, F, R;
    … …  
    336348        F = CFFactor( f, 1 );
    337349    else
    338         F = sqrFree( f );
    339 
    340     for ( i = F; i.hasItem(); i++ ) {
    341         if ( i.getItem().factor().inCoeffDomain() ) {
     350        F = sqrFree( f, 0, false );
     351
     352    for ( i = F; i.hasItem(); i++ )
     353    {
     354        if ( i.getItem().factor().inCoeffDomain() )
     355        {
    342356            if ( ! i.getItem().factor().isOne() )
    343357                R.append( CFFactor( i.getItem().factor(), i.getItem().exp() ) );
    344358        }
    345         else {
     359        else
     360        {
    346361            TIMING_START(fac_content);
    347362            g = compress( i.getItem().factor(), M );
    … …  
    355370            TIMING_END(fac_content);
    356371            DEBOUTLN( cerr, "now after content ..." );
    357             if ( g.isUnivariate() ) {
     372            if ( g.isUnivariate() )
     373            {
    358374                G = factorize( g, true );
    359375                for ( j = G; j.hasItem(); j++ )
    … …  
    361377                        R.append( CFFactor( M( j.getItem().factor() ), n ) );
    362378            }
    363             else {
     379            else
     380            {
    364381                GG = ZFactorizeMulti( g );
    365382                m = GG.max();
    … …  
    376393    return R;
    377394}
     395
     396static CFArray FpFactorizeMulti ( const CanonicalForm & arg )
     397{
     398    out_cf("FpFactorizeMulti:",arg,"\n");
     399    DEBINCLEVEL( cerr, "FpFactorizeMulti" );
     400    CFMap M;
     401    CanonicalForm UU, U = compress( arg, M );
     402    CanonicalForm delta, omega, V = LC( U, 1 );
     403    int t = U.level();
     404    CFFList F = factorize( V );
     405    CFFListIterator I, J;
     406    CFArray G, lcG, D;
     407    int i, j, k, m, r, maxdeg, h;
     408    REvaluation A( 2, t, FFRandom() );
     409    CanonicalForm U0;
     410    CanonicalForm ft, ut, gt, d;
     411    modpk b;
     412    bool negate = false;
     413
     414    DEBOUTLN( cerr, "-----------------------------------------------------" );
     415    DEBOUTLN( cerr, "trying to factorize U = " << U );
     416    DEBOUTLN( cerr, "U is a polynomial of level = " << arg.level() );
     417    DEBOUTLN( cerr, "U will be factorized with respect to variable " << Variable(1) );
     418    DEBOUTLN( cerr, "the leading coefficient of U with respect to that variable is " << V );
     419    DEBOUTLN( cerr, "which is factorized as " << F );
     420
     421    maxdeg = 0;
     422    out_cf("try:",U,"\n");
     423    for ( i = 2; i <= t; i++ )
     424    {
     425        j = U.degree( Variable( i ) );
     426        if ( j > maxdeg ) maxdeg = j;
     427    }
     428
     429    if ( F.getFirst().factor().inCoeffDomain() )
     430    {
     431        omega = F.getFirst().factor();
     432        F.removeFirst();
     433        if ( omega < 0 )
     434        {
     435            negate = true;
     436            omega = -omega;
     437            U = -U;
     438        }
     439    }
     440    else
     441        omega = 1;
     442
     443    bool goodeval = false;
     444    r = 0;
     445
     446//    for ( i = 0; i < 10*t; i++ )
     447//        A.nextpoint();
     448
     449    while ( ! goodeval )
     450    {
     451        TIMING_START(fac_findeval);
     452        findEvaluation( U, V, omega, F, A, U0, delta, D, r );
     453        out_cf("univ.U0:",U0,"\n");
     454        TIMING_END(fac_findeval);
     455        DEBOUTLN( cerr, "the evaluation point to reduce to an univariate problem is " << A );
     456        DEBOUTLN( cerr, "corresponding delta = " << delta );
     457        DEBOUTLN( cerr, "              omega = " << omega );
     458        DEBOUTLN( cerr, "              D     = " << D );
     459        DEBOUTLN( cerr, "now factorize the univariate polynomial " << U0 );
     460        G = conv_to_factor_array( factorize( U0, false ) );
     461        printf("conv_to_factor_array\n");
     462        DEBOUTLN( cerr, "which factorizes into " << G );
     463
     464        r = G.size();
     465        lcG = CFArray( 1, r );
     466        UU = U;
     467        //if ( goodeval )
     468        {
     469            printf("start hensel\n");
     470            TIMING_START(fac_hensel);
     471            goodeval = Hensel( UU, G, lcG, A, b, Variable(1) );
     472            TIMING_END(fac_hensel);
     473        }
     474    }
     475    for ( i = 1; i <= r; i++ )
     476    {
     477        G[i] /= icontent( G[i] );
     478        G[i] = M(G[i]);
     479    }
     480    // negate noch beachten !
     481    if ( negate )
     482        G[1] = -G[1];
     483    DEBDECLEVEL( cerr, "ZFactorMulti" );
     484    return G;
     485}
     486CFFList FpFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree )
     487{
     488    CFFList G, F, R;
     489    CFArray GG;
     490    CFFListIterator i, j;
     491    CFMap M;
     492    CanonicalForm g, cont;
     493    Variable v1, vm;
     494    int k, m, n;
     495
     496    v1 = Variable(1);
     497    if ( issqrfree )
     498        F = CFFactor( f, 1 );
     499    else
     500        F = sqrFree( f, 0, false );
     501
     502    printf("nach sqrFree:\n");
     503    out_cff(F);
     504    for ( i = F; i.hasItem(); i++ )
     505    {
     506        out_cf("consider:",i.getItem().factor(),"\n");
     507        if ( i.getItem().factor().inCoeffDomain() )
     508        {
     509            if ( ! i.getItem().factor().isOne() )
     510                R.append( CFFactor( i.getItem().factor(), i.getItem().exp() ) );
     511        }
     512        else
     513        {
     514            TIMING_START(fac_content);
     515            g = compress( i.getItem().factor(), M );
     516            // now after compress g contains Variable(1)
     517            vm = g.mvar();
     518            g = swapvar( g, v1, vm );
     519            cont = content( g );
     520            g = swapvar( g / cont, v1, vm );
     521            cont = swapvar( cont, v1, vm );
     522            n = i.getItem().exp();
     523            TIMING_END(fac_content);
     524            DEBOUTLN( cerr, "now after content ..." );
     525            if ( g.isUnivariate() )
     526            {
     527                G = factorize( g, true );
     528                for ( j = G; j.hasItem(); j++ )
     529                    if ( ! j.getItem().factor().isOne() )
     530                        R.append( CFFactor( M( j.getItem().factor() ), n ) );
     531            }
     532            else
     533            {
     534                GG = FpFactorizeMulti( g );
     535                m = GG.max();
     536                for ( k = GG.min(); k <= m; k++ )
     537                    if ( ! GG[k].isOne() )
     538                        R.append( CFFactor( M( GG[k] ), n ) );
     539            }
     540            out_cf("try cont:",cont,"\n");
     541            G = factorize( cont, true );
     542            out_cff(G);
     543            for ( j = G; j.hasItem(); j++ )
     544                if ( ! j.getItem().factor().isOne() )
     545                    R.append( CFFactor( M( j.getItem().factor() ), n ) );
     546        }
     547    }
     548    return R;
     549}
Note: See TracChangeset for help on using the changeset viewer.