source: git/factory/fac_multivar.cc @ ac7e53

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