source: git/factory/fac_distrib.cc @ a81073

spielwiese
Last change on this file since a81073 was a81073, checked in by Hans Schönemann <hannes@…>, 16 years ago
*hannes: format git-svn-id: file:///usr/local/Singular/svn/trunk@10516 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 5.5 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: fac_distrib.cc,v 1.9 2008-01-22 09:28:39 Singular Exp $ */
3
4#include <config.h>
5
6#include "assert.h"
7#include "debug.h"
8
9#include "cf_defs.h"
10#include "canonicalform.h"
11#include "cf_algorithm.h"
12#include "cf_iter.h"
13#include "fac_util.h"
14
15bool
16nonDivisors ( CanonicalForm omega, CanonicalForm delta, const CFArray & F, CFArray & d )
17{
18    DEBINCLEVEL( cerr, "nonDivisors" );
19    CanonicalForm q, r;
20    int k = F.size();
21    d = CFArray( 0, k );
22    d[0] = delta * omega;
23    for ( int i = 1; i <= k; i++ ) {
24        q = abs(F[i]);
25        for ( int j = i-1; j >= 0; j-- ) {
26            r = d[j];
27            do {
28                r = gcd( r, q );
29                q = q / r;
30            } while ( r != 1 );
31            if ( q == 1 ) {
32                DEBDECLEVEL( cerr, "nonDivisors" );
33                return false;
34            }
35        }
36        d[i] = q;
37    }
38    DEBDECLEVEL( cerr, "nonDivisors" );
39    return true;
40}
41
42bool
43checkEvaluation ( const CanonicalForm & U, const CanonicalForm & lcU, const CanonicalForm & omega, const CFFList & F, const Evaluation & A, CanonicalForm & delta )
44{
45    CanonicalForm Vn, U0 = A( U );
46    CFFListIterator I;
47    int j;
48    CFArray FF = CFArray( 1, F.length() );
49    CFArray D;
50    Vn = A( lcU );
51    if ( Vn.isZero() )
52        return false;
53    delta = content( U0 );
54    for ( I = F, j = 1; I.hasItem(); I++, j++ )
55        FF[j] = A( I.getItem().factor() );
56    return nonDivisors( omega, delta, FF, D );
57}
58
59bool
60distributeLeadingCoeffs ( CanonicalForm & U, CFArray & G, CFArray & lcG, const CFFList & F, const CFArray & D, CanonicalForm & delta, CanonicalForm & omega, const Evaluation & A, int r )
61{
62    DEBINCLEVEL( cerr, "distributeLeadingCoeffs" );
63    CanonicalForm ut, gt, d, ft;
64    CanonicalForm dd;
65    CFFListIterator I;
66    int m, j, i;
67    lcG = CFArray( 1, r );
68    for ( j = 1; j <= r; j ++ )
69        lcG[j] = 1;
70
71    for ( I = F, i = 1; I.hasItem(); I++, i++ )
72    {
73        ft = I.getItem().factor();
74        m = I.getItem().exp();
75        DEBOUTLN( cerr, "trying to distribute " << ft );
76        DEBOUTLN( cerr, "which is tested with " << D[i] );
77        DEBOUTLN( cerr, "and contained to the power of " << m );
78        j = 1;
79        while ( m > 0 && j <= r )
80        {
81            ut = lc( G[j] );
82            DEBOUTLN( cerr, "checking with " << ut );
83            while ( m > 0 && fdivides( D[i], ut ) )
84            {
85                DEBOUTLN( cerr, "match found" );
86                m--; ut /= D[i];
87                lcG[j] *= ft;
88            }
89            j++;
90        }
91        if (m != 0)
92        {
93            DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
94            return false;
95        }
96    }
97    DEBOUTLN( cerr, "the leading coeffs before omega and delta correction: " << lcG );
98    if ( omega != 1 )
99    {
100        for ( j = 1; j <= r; j++ )
101        {
102//            G[j] *= omega;
103            lcG[j] *= omega;
104            G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
105        }
106        U *= power( omega, r-1 );
107    }
108    if ( delta != 1 )
109    {
110        for ( j = 1; j <= r; j++ )
111        {
112            lcG[j] *= delta;
113            G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
114        }
115        U *= power( delta, r );
116    }
117    DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
118    return true;
119}
120
121
122static void
123gfbAdjoin ( const CanonicalForm & F, CFList & L )
124{
125    if ( F.isOne() )
126        return;
127    if ( L.isEmpty() ) {
128        L.append( F );
129        return;
130    }
131    CanonicalForm h, f = F;
132    CFListIterator i, j;
133    for ( i = L; i.hasItem() && ! f.isOne(); ) {
134        h = gcd( f, i.getItem() );
135        if ( h.isOne() ) {
136            i++;
137            continue;
138        }
139        while ( fdivides( h, f ) )
140            f /= h;
141        CFList D( h );
142        gfbAdjoin( i.getItem() / h, D );
143        for ( j = D; j.hasItem(); j++ )
144            i.append( j.getItem() );
145        i.remove( true );
146    }
147    if ( ! f.isOne() )
148        L.append( f );
149}
150
151
152CFList
153gcdFreeBasis ( const CFList L )
154{
155    CFListIterator i;
156    CFList R;
157    for ( i = L; i.hasItem(); i++ )
158        gfbAdjoin( i.getItem(), R );
159    return R;
160}
161
162bool
163Univar2Bivar(const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
164{
165    CanonicalForm l = LC( U, Variable(1) );
166    int n = G.size();
167    CFArray lcG(1,n);
168    for ( int i = 1; i <= n; i++ ) {
169        G[i] *= A(l)/lc(G[i]);
170        lcG[i] = l;
171    }
172    return Hensel( U * power( l, n-1 ), G, lcG, A, bound, x );
173}
174
175bool
176Hensel2 ( const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
177{
178    int i,n = G.size(); // n is number of factors of U
179    CFArray TrueLcs(1, n);
180    for (i=1; i <= n; i++)
181        TrueLcs[i] = 1;
182    Variable y;
183    CanonicalForm lcU = LC ( U, Variable(1) );
184    while (! lcU.inCoeffDomain())
185    {
186        y = lcU.mvar(); // should make a more intelligent choice
187        CanonicalForm BivariateU = A ( U, 2, y.level() - 1 );
188        CFArray BivariateFactors = G;
189        CFArray lcFactors(1,n);
190        Univar2Bivar(BivariateU, BivariateFactors, A, bound, y);
191        for (i = 1; i <= n; i++)
192        {
193            BivariateFactors[i] /= content(BivariateFactors[i]);
194            lcFactors[i] = LC(BivariateFactors[i],Variable(1));
195        }
196//        GFB = GcdFreeBasis(lcFactors); // this is not right... should probably make everything squarefree
197//        Hensel2(lcU, GFB, A, bound, y);
198    }
199    for (i = 1; i <= n; i++)
200        G[i] *= A(TrueLcs[i])/lc(G[i]);
201    return Hensel(U, G, TrueLcs, A, bound, x);
202}
Note: See TracBrowser for help on using the repository browser.