source: git/factory/fac_multivar.cc @ 043814

spielwiese
Last change on this file since 043814 was 043814, checked in by Jens Schmidt <schmidt@…>, 27 years ago
debug output rewritten some spurious preprocessor directives removed git-svn-id: file:///usr/local/Singular/svn/trunk@97 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 8.2 KB
Line 
1// emacs edit mode for this file is -*- C++ -*-
2// $Id: fac_multivar.cc,v 1.3 1997-03-27 09:47:17 schmidt Exp $
3
4/*
5$Log: not supported by cvs2svn $
6Revision 1.2  1996/12/05 18:24:54  schmidt
7``Unconditional'' check-in.
8Now it is my turn to develop factory.
9
10Revision 1.1  1996/07/23 09:18:35  stobbe
11Version in work.
12
13Revision 1.0  1996/05/17 10:59:45  stobbe
14Initial revision
15
16*/
17
18#include "assert.h"
19#include "debug.h"
20#include "timing.h"
21
22#include "cf_defs.h"
23
24#include "fac_multivar.h"
25#include "fac_univar.h"
26#include "cf_reval.h"
27#include "cf_map.h"
28#include "fac_util.h"
29#include "cf_binom.h"
30#include "cf_iter.h"
31#include "fac_distrib.h"
32
33
34TIMING_DEFINE_PRINT(fac_content);
35TIMING_DEFINE_PRINT(fac_findeval);
36TIMING_DEFINE_PRINT(fac_distrib);
37TIMING_DEFINE_PRINT(fac_hensel);
38
39static CFArray
40conv_to_factor_array( const CFFList & L )
41{
42    int n;
43    CFFListIterator I = L;
44    bool negate = false;
45
46    if ( ! I.hasItem() )
47        n = 0;
48    else  if ( I.getItem().factor().inBaseDomain() ) {
49        negate = I.getItem().factor().sign() < 0;
50        I++;
51        n = L.length();
52    }
53    else
54        n = L.length() + 1;
55    CFFListIterator J = I;
56    while ( J.hasItem() ) {
57        n += J.getItem().exp() - 1;
58        J++;
59    }
60    CFArray result( 1, n-1 );
61    int i, j, k;
62    i = 1;
63    while ( I.hasItem() ) {
64        k = I.getItem().exp();
65        for ( j = 1; j <= k; j++ ) {
66            result[i] = I.getItem().factor();
67            i++;
68        }
69        I++;
70    }
71    if ( negate )
72        result[1] = -result[1];
73    return result;
74}
75
76static modpk
77coeffBound ( const CanonicalForm & f, int p )
78{
79    int * degs = degrees( f );
80    int M = 0, i, k = f.level();
81    for ( i = 1; i <= k; i++ )
82        M += degs[i];
83    CanonicalForm b = 2 * maxCoeff( f ) * power( CanonicalForm( 3 ), M );
84    CanonicalForm B = p;
85    k = 1;
86    while ( B < b ) {
87        B *= p;
88        k++;
89    }
90    return modpk( p, k );
91}
92
93// static bool
94// nonDivisors ( CanonicalForm omega, CanonicalForm delta, const CFArray & F, CFArray & d )
95// {
96//     DEBOUTLN( cerr, "nondivisors omega = ", omega );
97//     DEBOUTLN( cerr, "nondivisors delta = ", delta );
98//     DEBOUTLN( cerr, "nondivisors F = ", F );
99//     CanonicalForm q, r;
100//     int k = F.size();
101//     d = CFArray( 0, k );
102//     d[0] = delta * omega;
103//     for ( int i = 1; i <= k; i++ ) {
104//      q = abs(F[i]);
105//      for ( int j = i-1; j >= 0; j-- ) {
106//          r = d[j];
107//          do {
108//              r = gcd( r, q );
109//              q = q / r;
110//          } while ( r != 1 );
111//          if ( q == 1 )
112//              return false;
113//      }
114//      d[i] = q;
115//     }
116//     return true;
117// }
118
119static void
120findEvaluation ( const CanonicalForm & U, const CanonicalForm & V, const CanonicalForm & omega, const CFFList & F, Evaluation & A, CanonicalForm & U0, CanonicalForm & delta, CFArray & D, int r )
121{
122    DEBINCLEVEL( cerr, "findEvaluation" );
123    CanonicalForm Vn;
124    CFFListIterator I;
125    int j;
126    bool found = false;
127    CFArray FF = CFArray( 1, F.length() );
128    if ( r > 0 )
129        A.nextpoint();
130    while ( ! found ) {
131        Vn = A( V );
132        if ( Vn != 0 ) {
133            U0 = A( U );
134            DEBOUTLN( cerr, "U0 = ", U0 );
135            if ( isSqrFree( U0 ) ) {
136                delta = content( U0 );
137                DEBOUTLN( cerr, "content( U0 ) = ", delta );
138                for ( I = F, j = 1; I.hasItem(); I++, j++ )
139                    FF[j] = A( I.getItem().factor() );
140                found = nonDivisors( omega, delta, FF, D );
141            }
142            else {
143                DEBOUTLN( cerr, "not sqrfree :", sqrFree( U0 ) );
144            }
145        }
146        if ( ! found )
147            A.nextpoint();
148    }
149    DEBDECLEVEL( cerr, "findEvaluation" );
150}
151
152static CFArray
153ZFactorizeMulti ( const CanonicalForm & arg )
154{
155    DEBINCLEVEL( cerr, "ZFactorizeMulti" );
156    CFMap M;
157    CanonicalForm UU, U = compress( arg, M );
158    CanonicalForm delta, omega, V = LC( U, 1 );
159    int t = U.level();
160    CFFList F = factorize( V );
161    CFFListIterator I, J;
162    CFArray G, lcG, D;
163    int i, j, k, m, r, maxdeg, h;
164    REvaluation A( 2, t, IntRandom( 100 ) );
165    CanonicalForm U0;
166    CanonicalForm ft, ut, gt, d;
167    modpk b;
168    bool negate = false;
169
170    DEBOUTLN( cerr, "-----------------------------------------------------", ' ' );
171    DEBOUTLN( cerr, "trying to factorize U = ", U );
172    DEBOUTLN( cerr, "U is a polynomial of level = ", arg.level() );
173    DEBOUTLN( cerr, "U will be factorized with respect to variable ", Variable(1) );
174    DEBOUTLN( cerr, "the leading coefficient of U with respect to that variable is ", V );
175    DEBOUTLN( cerr, "which is factorized as ", F );
176
177    maxdeg = 0;
178    for ( i = 2; i <= t; i++ ) {
179        j = U.degree( Variable( i ) );
180        if ( j > maxdeg ) maxdeg = j;
181    }
182
183    if ( F.getFirst().factor().inCoeffDomain() ) {
184        omega = F.getFirst().factor();
185        F.removeFirst();
186        if ( omega < 0 ) {
187            negate = true;
188            omega = -omega;
189            U = -U;
190        }
191    }
192    else
193        omega = 1;
194
195    bool goodeval = false;
196    r = 0;
197
198//    for ( i = 0; i < 10*t; i++ )
199//      A.nextpoint();
200
201    while ( ! goodeval ) {
202        TIMING_START(fac_findeval);
203        findEvaluation( U, V, omega, F, A, U0, delta, D, r );
204        TIMING_END(fac_findeval);
205        DEBOUTLN( cerr, "the evaluation point to reduce to an univariate problem is ", A );
206        DEBOUTLN( cerr, "corresponding delta = ", delta );
207        DEBOUTLN( cerr, "              omega = ", omega );
208        DEBOUTLN( cerr, "              D     = ", D );
209        DEBOUTLN( cerr, "now factorize the univariate polynomial ", U0 );
210        G = conv_to_factor_array( factorize( U0, false ) );
211        DEBOUTLN( cerr, "which factorizes into ", G );
212        b = coeffBound( U, getZFacModulus().getp() );
213        if ( getZFacModulus().getpk() > b.getpk() )
214            b = getZFacModulus();
215        DEBOUTLN( cerr, "the coefficient bound of the factors of U is ", b.getpk() );
216
217        r = G.size();
218        lcG = CFArray( 1, r );
219        UU = U;
220        DEBOUTLN( cerr, "now trying to distribute the leading coefficients ...", ' ' );
221        TIMING_START(fac_distrib);
222        goodeval = distributeLeadingCoeffs( UU, G, lcG, F, D, delta, omega, A, r );
223        TIMING_END(fac_distrib);
224#ifdef DEBUGOUTPUT
225        if ( goodeval ) {
226            DEBOUTLN( cerr, "the univariate factors after distribution are ", G );
227            DEBOUTLN( cerr, "the distributed leading coeffs are ", lcG );
228            DEBOUTLN( cerr, "U may have changed and is now ", UU );
229            DEBOUTLN( cerr, "which has leading coefficient ", LC( UU, Variable(1) ) );
230
231            if ( LC( UU, Variable(1) ) != prod( lcG ) || A(UU) != prod( G ) ) {
232                DEBOUTLN( cerr, "!!! distribution was not correct !!!", ' ' );
233                DEBOUTLN( cerr, "product of leading coeffs is ", prod( lcG ) );
234                DEBOUTLN( cerr, "product of univariate factors is ", prod( G ) );
235                DEBOUTLN( cerr, "the new U is evaluated as ", A(UU) );
236            }
237            else
238                DEBOUTLN( cerr, "leading coeffs correct", ' ' );
239        }
240        else {
241            DEBOUTLN( cerr, "we have found a bad evaluation point", ' ' );
242        }
243#endif
244        if ( goodeval ) {
245            TIMING_START(fac_hensel);
246            goodeval = Hensel( UU, G, lcG, A, b, Variable(1) );
247            TIMING_END(fac_hensel);
248        }
249    }
250    for ( i = 1; i <= r; i++ ) {
251        G[i] /= icontent( G[i] );
252        G[i] = M(G[i]);
253    }
254    // negate noch beachten !
255    if ( negate )
256        G[1] = -G[1];
257    DEBDECLEVEL( cerr, "ZFactorMulti" );
258    return G;
259}
260
261CFFList
262ZFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree )
263{
264    CFFList G, F, R;
265    CFArray GG;
266    CFFListIterator i, j;
267    CFMap M;
268    CanonicalForm g, cont;
269    Variable v1, vm;
270    int k, m, n;
271
272    v1 = Variable(1);
273    if ( issqrfree )
274        F = CFFactor( f, 1 );
275    else
276        F = sqrFree( f );
277
278    for ( i = F; i.hasItem(); i++ ) {
279        if ( i.getItem().factor().inCoeffDomain() ) {
280            if ( ! i.getItem().factor().isOne() )
281                R.append( CFFactor( i.getItem().factor(), i.getItem().exp() ) );
282        }
283        else {
284            TIMING_START(fac_content);
285            g = compress( i.getItem().factor(), M );
286            // now after compress g contains Variable(1)
287            vm = g.mvar();
288            g = swapvar( g, v1, vm );
289            cont = content( g );
290            g = swapvar( g / cont, v1, vm );
291            cont = swapvar( cont, v1, vm );
292            n = i.getItem().exp();
293            TIMING_END(fac_content);
294            DEBOUTLN( cerr, "now after content ...", ' ' );
295            if ( g.isUnivariate() ) {
296                G = factorize( g, true );
297                for ( j = G; j.hasItem(); j++ )
298                    if ( ! j.getItem().factor().isOne() )
299                        R.append( CFFactor( M( j.getItem().factor() ), n ) );
300            }
301            else {
302                GG = ZFactorizeMulti( g );
303                m = GG.max();
304                for ( k = GG.min(); k <= m; k++ )
305                    if ( ! GG[k].isOne() )
306                        R.append( CFFactor( M( GG[k] ), n ) );
307            }
308            G = factorize( cont, true );
309            for ( j = G; j.hasItem(); j++ )
310                if ( ! j.getItem().factor().isOne() )
311                    R.append( CFFactor( M( j.getItem().factor() ), n ) );
312        }
313    }
314    return R;
315}
Note: See TracBrowser for help on using the repository browser.