source: git/factory/fac_multivar.cc @ 281760

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