source: git/libfac/charset/charset.cc @ 4a81ec

spielwiese
Last change on this file since 4a81ec was 4a81ec, checked in by Hans Schönemann <hannes@…>, 27 years ago
* hannes/michael: libfac-0.3.0 git-svn-id: file:///usr/local/Singular/svn/trunk@708 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 16.2 KB
Line 
1/* Copyright 1996 Michael Messollen. All rights reserved. */
2////////////////////////////////////////////////////////////
3// emacs edit mode for this file is -*- C++ -*-
4static char * rcsid = "$Id: charset.cc,v 1.3 1997-09-12 07:19:40 Singular Exp $";
5/////////////////////////////////////////////////////////////
6// FACTORY - Includes
7#include <factory.h>
8// Factor - Includes
9#include <SqrFree.h>
10#include <Factor.h>
11#include <interrupt.h>
12// Charset - Includes
13#include "csutil.h"
14#include "algfactor.h"
15#include "alg_factor.h"
16// Some CC's need this:
17#include "charset.h"
18
19#ifdef BASICSETDEBUG
20#  define DEBUGOUTPUT
21#else
22#  undef DEBUGOUTPUT
23#endif
24
25#include "debug.h"
26#include "timing.h"
27TIMING_DEFINE_PRINT(subfactorize_time);
28
29
30// forward declarations:
31static CFList     irras(CFList & AS, int &ja, CanonicalForm & reducible);
32
33#ifdef BASICSETDEBUG
34#  define DEBUGOUTPUT
35#else
36#  undef DEBUGOUTPUT
37#endif
38#include "debug.h"
39
40// the next computes a characteristic set (a basic set in Wang's sense)
41CFList
42BasicSet( const CFList &PS )
43{
44    CFList QS = PS, BS, RS;
45    CanonicalForm b;
46    int cb;
47
48    DEBOUTLN(cout, "BasicSet: called with ps= ", PS);
49    if ( PS.length() < 2 ) return PS;
50    while ( ! QS.isEmpty() ) {
51        b = lowestRank( QS );
52        cb = rank( b );
53        DEBOUTLN(cout, "BasicSet: choose b  = ", b);
54        DEBOUTLN(cout, "BasicSet: it's rank = ", cb);
55        BS=Union(CFList(b),BS);//BS.append( b );
56        if ( rank( b ) == 0 )
57            return Union(PS, CFList(b)) ; // b should be the first elem!
58        else {
59            RS = CFList();
60            // QS:= {q \in QS -{B} | q is reduced wrt b}
61            // We can process whole QS, because b is not reduced wrt. b
62            for ( CFListIterator i = QS; i.hasItem(); ++i )
63                if ( degree( i.getItem(), cb ) < degree( b ) )
64                    //RS.append( i.getItem() );
65                    RS = Union(CFList(i.getItem()),RS);
66            QS = RS;
67        }
68    }
69    DEBOUTLN(cout, "BasicSet: returning bs= ", BS);
70    return BS;
71}
72
73int
74checkok( const CFList & PS, CFList & FS2){
75  CanonicalForm elem;
76
77  for ( CFListIterator i=PS; i.hasItem(); i++){
78    elem= i.getItem();
79    for (CFListIterator j=FS2; j.hasItem(); j++){
80      if (elem == j.getItem()){
81        //      FS2= Difference(FS2,CFList(elem));
82        return 0;
83      }
84    }
85  }
86  return 1;
87}
88
89#ifdef MCHARSETNDEBUG
90#  define DEBUGOUTPUT
91#else
92#  undef DEBUGOUTPUT
93#endif
94#include "debug.h"
95
96// The modified CharSet (an extended characteristic set with certain factors
97// canceled; this is a characteristic set in Wang's sense)
98CFList
99MCharSetN( const CFList &PS, PremForm & Remembern ){
100  CFList QS = PS, RS = PS, CS, OLDCS;
101
102  DEBOUTLN(cout, "MCharSetN: called with ps= ", PS);
103  while ( ! RS.isEmpty() ) {
104    CS = BasicSet( QS );
105    OLDCS=CS;
106    DEBOUTLN(cout, "MCharSetN: CS= ", CS);
107//     if ( getNumVars(CS.getFirst()) > 1 ){
108//       //CS = removecontent(CS, Remembern);
109// #ifdef MCHARSETNDEBUG
110//       cout << "MCharSetN: CS= " << CS << endl;
111// #endif
112//     }
113    Remembern.FS1 = Union(Remembern.FS1, initalset1(CS));
114    DEBOUTLN(cout, "MCharSetN: Remembern.FS1= ", Remembern.FS1);
115    DEBOUTLN(cout, "MCharSetN: Remembern.FS2= ", Remembern.FS2);
116    RS = CFList();
117    if ( rank( CS.getFirst() ) != 0 ) {
118      CFList D = Difference( QS, CS );
119      DEBOUT(cout, "MCharSetN: Difference( ", QS);
120      DEBOUT(cout, " , ", CS);
121      DEBOUTLN(cout, " ) = ", D);
122//cout << "MCharSetN: Difference( " << QS << " , " << CS << " ) = " << D << endl;
123      //PremForm Oldremember=Remembern;
124      //PremForm Newremember=Remembern;
125      for ( CFListIterator i = D; i.hasItem(); ++i ) {
126        CanonicalForm r = Prem( i.getItem(), CS );
127        DEBOUT(cout,"MCharSetN: Prem(", i.getItem()  );
128        DEBOUT(cout, ",", CS);
129        DEBOUTLN(cout,") = ", r); 
130//cout << "MCharSetN: Prem("<< i.getItem() << "," << CS << ") = " << r << endl;
131        if ( r != 0 ){
132          //removefactor( r, Newremember );
133          removefactor( r, Remembern );
134          //Remembern.FS2 = Union(Remembern.FS2, Newremember.FS2);
135          //Newremember = Oldremember;
136          //if ( cls(r) > 0 )
137            //RS=Union(CFList(r),RS);//RS.append( r );
138            RS=Union(RS,CFList(r));
139        }
140      }
141      if ( ! checkok(RS,Remembern.FS2)) return CFList(CanonicalForm(1));
142      DEBOUTLN(cout, "MCharSetN: RS= ", RS);
143      //QS = Union( QS, RS );
144      QS = Union(OLDCS,RS);
145      DEBOUTLN(cout, "MCharSetN: QS= Union(QS,RS)= ", QS);
146    }
147    else{ return CFList(CanonicalForm(1)); }
148  }
149  DEBOUTLN(cout, "MCharSetN: Removed factors: ", Remembern.FS2);
150  DEBOUTLN(cout, "MCharSetN: Remembern.FS1: ", Remembern.FS1);
151
152  return CS;
153}
154
155
156CFList
157mcharset( const CFList &PS, PremForm & Remembern ){
158  CFList cs= MCharSetN(PS, Remembern );
159  CFList rs= remsetb(Difference(PS,cs),cs);
160
161  DEBOUTLN(cout, "mcharset: cs= ", cs);
162  DEBOUTLN(cout, "mcharset: rs= ", rs);
163  if ( rs.length() > 0 )
164    cs= mcharset(Union(PS,Union(cs,rs)), Remembern);
165  return cs;
166}
167
168// the "original" extended characteristic set
169CFList
170CharSet( const CFList &PS ){
171  CFList QS = PS, RS = PS, CS;
172
173  while ( ! RS.isEmpty() ) {
174    CS = BasicSet( QS );
175    RS = CFList();
176    if ( rank( CS.getFirst() ) != 0 ) {
177      CFList D = Difference( QS, CS );
178      for ( CFListIterator i = D; i.hasItem(); ++i ) {
179        CanonicalForm r = Prem( i.getItem(), CS );
180        if ( r != 0 )  RS=Union(CFList(r),RS);//RS.append( r );
181      }
182      QS = Union( QS, RS );
183    }
184  }
185  return CS;
186}
187
188static CFList
189charseta( const CFList & PS ){
190  CFList QS = PS, RS = PS, CS;
191
192  while ( ! RS.isEmpty() ) {
193    CS = CharSet( QS );
194    RS = CFList();
195    if ( rank( CS.getFirst() ) != 0 ) {
196      CFList D = Difference( QS, CS );
197      for ( CFListIterator i = D; i.hasItem(); ++i ) {
198        CanonicalForm r = Prem( i.getItem(), CS );
199        if ( r != 0 )  RS=Union(CFList(r),RS);//RS.append( r );
200      }
201      QS = Union(CS,Union( QS, RS ));
202    }
203    else return CFList(CanonicalForm(1));
204  }
205  return CS;
206}
207
208static bool
209contractsub( const CFList & cs1, const CFList & cs2 ){
210  CFListIterator i;
211
212  for ( i=cs1; i.hasItem(); i++ )
213    if ( Prem(i.getItem(),cs2 ) != 0 ) return false;
214  CFList is=initalset1(cs1);
215  for ( i=is; i.hasItem(); i++ )
216    if ( Prem(i.getItem(),cs2 ) == 0 ) return false;
217  return true;
218}
219
220static ListCFList
221contract( const ListCFList & cs){
222  ListCFList mem,ts;
223  CFList iitem,jitem;
224
225  if ( cs.length() < 2 ) return cs;
226
227  for ( ListCFListIterator i=cs; i.hasItem(); i++ ){
228    iitem=i.getItem();
229    if ( ! member(iitem, mem))
230      for ( ListCFListIterator j=i; j.hasItem(); j++){
231        jitem=j.getItem(); 
232        if ( ! same( iitem, jitem ) )
233          if ( ! member(jitem, mem))
234            if ( contractsub(iitem, jitem) ){ 
235              ts.append(jitem); mem.append(jitem);
236            }
237            else
238              if ( contractsub(jitem, iitem) ){
239                ts.append(iitem);
240              }
241      }
242  }
243  return Minus(cs,ts);
244}
245
246static ListCFList
247adjoin(const CFList & is, const CFList & qs, const ListCFList & qh ){
248  ListCFList iss,qhi;
249  ListCFListIterator j;
250  CFList iscopy,itt;
251  CFListIterator i;
252  CanonicalForm elem;
253  int ind, length;
254
255  for ( i=is ; i.hasItem(); i++ ){
256    elem=i.getItem();
257    if ( cls(elem) > 0 ) iscopy=Union(CFList(elem),iscopy); 
258  }
259  if ( iscopy.isEmpty() ) return iss;
260  qhi = MyDifference(qh,qs);
261  length = qhi.length();
262  for ( i =iscopy; i.hasItem(); i++){
263    itt = Union(qs,CFList(i.getItem()));
264    ind = 0;
265    if ( length > 0 )
266      for ( j=qhi; j.hasItem(); j++ )
267        if ( subset(j.getItem(),itt )) ind=1; 
268    if ( ind == 0 ) iss.append(itt);
269  }
270  return iss;
271}
272
273static ListCFList
274adjoinb(const CFList & is, const CFList & qs, const ListCFList & qh ,const CFList & cs){
275  ListCFList iss,qhi;
276  ListCFListIterator j;
277  CFList iscopy,itt;
278  CFListIterator i;
279  CanonicalForm elem;
280  int ind, length;
281
282  for ( i=is ; i.hasItem(); i++ ){
283    elem=i.getItem();
284    if ( cls(elem) > 0 ) iscopy=Union(CFList(elem),iscopy); 
285  }
286  if ( iscopy.isEmpty() ) return iss;
287  qhi = MyDifference(qh,qs);
288  length = qhi.length();
289  for ( i =iscopy; i.hasItem(); i++){
290    itt = Union(Union(qs,CFList(i.getItem())),cs);
291    ind = 0;
292    if ( length > 0 )
293      for ( j=qhi; j.hasItem(); j++ )
294        if ( subset(j.getItem(),itt )) ind=1; 
295    if ( ind == 0 ) {iss.append(itt);}
296  }
297  return iss;
298}
299
300static ListCFList
301sort( const ListCFList & list_to_sort ){
302  ListCFList output,copy=list_to_sort;
303  CFList l,qs1,elem;
304
305  l = copy.getLast(); copy.removeLast();
306  if ( copy.length() == 0 ){ return ListCFList(l); }
307  for ( ListCFListIterator i=copy ; i.hasItem(); i++ ){
308    elem = i.getItem();
309    if ( elem.length() > l.length() ) { 
310      output = MyUnion( ListCFList(l), output);
311      l= elem;
312    }
313    else{ output = MyUnion(output, ListCFList(elem) ); }
314  }
315  //output = MyUnion(ListCFList(l),sort(output));
316  output = MyUnion(ListCFList(l),output);
317  return output;
318}
319
320#ifdef EXPERIMENTAL
321static CFList
322getItemNr( int nr, const ListCFList & copy){
323  int i =1;
324  CFList elem;
325
326  for ( ListCFListIterator j=copy; j.hasItem(); j++ )
327    if ( i == nr ) { elem=j.getItem(); break; }
328    else { i+= 1; }
329  return elem;
330}
331
332static int
333choosefrom(){
334int choice;
335    cout << "choose from qhi! ->";
336    cin >> choice;
337return choice;
338}
339
340static ListCFList
341msort( const ListCFList & list_to_sort ){
342  int nr, number = list_to_sort.length();
343  ListCFList output;
344
345  cout << "Sort: list to sort is: " <<  list_to_sort << endl; 
346  for (int i=1; i<= number; i++){
347    cout << " Next elem = "; cin >> nr;
348    output.append(getItemNr(nr,list_to_sort));
349  }
350  return output;
351}
352#endif
353
354#ifdef IRRCHARSERIESDEBUG
355#  define DEBUGOUTPUT
356#else
357#  undef DEBUGOUTPUT
358#endif
359#include "debug.h"
360
361ListCFList
362IrrCharSeries( const CFList &PS, int opt ){
363  CanonicalForm reducible,reducible2;
364  CFList qs,cs,factorset,is,ts;
365  ListCFList pi,ppi,qqi,qsi,iss,qhi= ListCFList(PS);
366  int nr_of_iteration=0,ts2,highestlevel=0; 
367#ifdef EXPERIMENTAL
368  int choice=1;;
369#endif
370
371  DEBOUTMSG(cout, rcsid);
372//  cout << getCharacteristic() << endl;
373  for ( CFListIterator Ps=PS; Ps.hasItem(); Ps++ )
374    if ( level(Ps.getItem() ) > highestlevel ) highestlevel = level(Ps.getItem()) ;
375//  for ( int xx=1; xx <= highestlevel; xx++)
376//   cout << Variable(xx) ;
377//  cout << endl;
378//  for ( CFListIterator Ps=PS; Ps.hasItem(); Ps++ )
379//    cout << Ps.getItem() << ", " ;//<< endl;
380//  cout <<  endl;
381  while ( ! qhi.isEmpty() ) {
382    qhi=sort(qhi);
383    DEBOUTLN(cout, "qhi is: ", qhi);
384#ifdef EXPERIMENTAL
385    choice=choosefrom();
386    cout <<"/n Choose " << choice << endl;
387    qs= getItemNr(choice, qhi);
388#else
389    qs=qhi.getFirst();
390#endif
391    DEBOUTLN(cout, "qs  is: ", qs);
392    DEBOUTLN(cout, "ppi is: ", ppi);
393    ListCFList ppi1,ppi2;
394    select(ppi,qs.length(),ppi1,ppi2);
395    DEBOUTLN(cout, "ppi1 is: ", ppi1);
396    DEBOUTLN(cout, "ppi2 is: ", ppi2);
397    qqi = MyUnion(ppi2,qqi);
398    DEBOUTLN(cout, "qqi is: ", qqi);
399    if ( nr_of_iteration == 0 ){ nr_of_iteration += 1; ppi = ListCFList(); }
400    else{ nr_of_iteration += 1; ppi = MyUnion(ListCFList(qs),ppi1); }
401    DEBOUTLN(cout,"ppi is: ", ppi);
402    PremForm Remembern;
403    cs = MCharSetN(qs,Remembern);
404    DEBOUTLN(cout, "cs is: ", cs);
405    DEBOUTLN(cout, "factorset is: ", Remembern.FS2);
406    cs = removecontent(cs,Remembern);
407    factorset=Remembern.FS2;
408    DEBOUTLN(cout, "cs (after removecontent) is: ", cs);
409    DEBOUTLN(cout, "factorset is: ", factorset);
410    // Hier: removecontent einfuegen!!!!
411    if ( cls(cs.getFirst()) > 0 ){
412      ts = irras(cs,ts2, reducible);
413
414      // INTERRUPTHANDLER
415      if ( interrupt_handle() ) return ListCFList() ;
416      // INTERRUPTHANDLER
417
418      DEBOUTLN(cout, "ts is: ", ts);
419      DEBOUTLN(cout, "ts2 is: ", ts2);
420      // next is preliminary: should be ==0
421      if ( ts2 <= 0 ){ //irreducible
422        if ( ! subset(cs,qs) ){ 
423          DEBOUTMSG(cout, "cs is not a subset of qs");
424          cs = charseta(Union(qs,cs));
425          DEBOUTLN(cout, "new cs is: ", cs);
426        }
427        if ( ! member(cs,pi) ){ 
428          pi = MyUnion(pi, ListCFList(cs));
429          DEBOUTMSG(cout, "cs is not a member of pi");
430          DEBOUTLN(cout, "pi is: ", pi);
431          if ( cls(cs.getFirst()) > 0 ){
432            ts = irras(cs,ts2,reducible);
433
434            // INTERRUPTHANDLER
435            if ( interrupt_handle() ) return ListCFList() ;
436            // INTERRUPTHANDLER
437
438            DEBOUTLN(cout, "ts is: ", ts);
439            DEBOUTLN(cout, "ts2 is: ", ts2);
440            // next is preliminary: should be ==0
441            if ( ts2 <= 0 ){ //irreducible
442              qsi = MyUnion(qsi,ListCFList(cs));
443              DEBOUTLN(cout, "qsi is: ", qsi);
444              if ( cs.length() == highestlevel ){
445                DEBOUTLN(cout, "cs.length() == nops(ord) :", cs.length());
446                is = factorps(factorset);
447              }
448              else{
449                DEBOUT(cout,"cs.length() != nops(ord) :", cs.length());
450                DEBOUTLN(cout, "  nops(ord)= ", highestlevel);
451                is = Union(initalset1(cs),factorps(factorset));
452              }
453              DEBOUTLN(cout, "is is: ", is);
454              iss = adjoin(is,qs,qqi);
455              DEBOUTLN(cout, "iss is: ", iss);
456            }
457          }
458          else{ iss = adjoin(factorps(factorset),qs,qqi); }
459        }
460        else{ 
461          DEBOUTMSG(cout, "cs is a member of pi");
462          iss = adjoin(factorps(factorset),qs,qqi); }
463        DEBOUTLN(cout, "iss is: ", iss);
464        DEBOUTLN(cout, "   factorps(factorset)= ", factorps(factorset));
465        DEBOUTLN(cout, "   qs= ", qs);
466        DEBOUTLN(cout, "   qqi= ", qqi);
467      }
468      // next is preliminary: should be !=0
469      if ( ts2 > 0 ){
470        is = factorps(factorset);
471        DEBOUTLN(cout, "is is: ", is);
472        if ( ts2 > 1 ){ 
473          // setup cst: need it later for adjoinb
474          CFList cst;
475          for ( CFListIterator i=cs ; i.hasItem(); i++){
476            if ( i.getItem() == reducible ) { break; }
477            else { cst.append(i.getItem()); }
478          }
479          is = Union(initalset1(cst), is);
480          iss = MyUnion(adjoin(is,qs,qqi), adjoinb(ts,qs,qqi,cst));
481        }
482        else{ iss = adjoin(Union(is,ts),qs,qqi); }
483        DEBOUTLN(cout, "iss is: ", iss);
484      }
485    }
486    else{ 
487      iss = adjoin(factorps(factorset),qs,qqi); 
488      DEBOUTMSG(cout, "case: cs is a constant.");
489      DEBOUTLN(cout, "  qs = ", qs);
490      DEBOUTLN(cout, "  qqi = ", qqi);
491      DEBOUTLN(cout, "  iss = adjoin(factorps(factorset),qs,qqi) = ",iss);
492    }
493    if ( qhi.length() > 1 ){ qhi.removeFirst(); qhi = MyUnion(qhi,iss); }
494    else{ qhi = iss; }
495    DEBOUTLN(cout, "iss is: ", iss);
496  }
497  if ( ! qsi.isEmpty() ){ 
498    DEBOUTLN(cout, "qsi before contract= ", qsi);
499    if ( opt == 0 ){
500       return contract( qsi ); 
501    }
502    else { return qsi; }
503  }
504  else{ return ListCFList() ; }
505} 
506
507// tests for characteristic sets
508//////////////////////////////////
509#ifdef IRRASDEBUG
510#  define DEBUGOUTPUT
511#else
512#  undef DEBUGOUTPUT
513#endif
514
515#include "debug.h"
516
517static CFList
518irras( CFList & AS, int & ja, CanonicalForm & reducible){
519  CFFList qs;
520  CFList ts,as;
521  CanonicalForm elem;
522  int ind=1,nr=0, success=-1;
523  CFListIterator i;
524
525  ja = 0;
526  DEBOUTLN(cout, "irras: called with: AS= ", AS);
527  for ( i=AS; i.hasItem(); i++ ){
528    elem = i.getItem();
529    nr += 1;
530    DEBOUT(cout, "irras: factoring: ", elem);
531    if ( degree(elem) > 1 ) // linear poly's are irreduzible
532      qs = Factorize(elem);
533    else{
534      qs=(CFFactor(elem,1));
535      qs.insert(CFFactor(CanonicalForm(1),1));
536    }
537    DEBOUTLN(cout, "  = ", qs);
538    // INTERRUPTHANDLER
539    if ( interrupt_handle() ) return CFList() ;
540    // INTERRUPTHANDLER
541    qs.removeFirst();
542    if ( (qs.length() >= 2 ) || (qs.getFirst().exp() > 1)){
543      DEBOUTLN(cout, "irras: Setting ind=0, ja= ", nr);
544      ja=nr; ind=0; reducible= elem; 
545      break;
546    }
547    //    else{ as.append(elem) ; }
548  }
549  //  cout << "ind= " << ind << endl;
550  if ( (ind == 1) ){ //&& ( as.length() > 1) ){
551    if ( irreducible(AS) ){ // as quasilinear? => irreducible!
552      ja = 0; 
553      DEBOUTLN(cout, "as is irreducible. as= ", AS);
554    }
555    else {
556//#ifdef HAVE_SINGULAR
557//      extern void WerrorS(char *);
558//      WerrorS("libfac: Factoring over algebraic function field!");
559//#else
560//      cerr << "libfac: Factoring over algebraic function field!" << endl;
561//#endif
562      i=AS;
563      for ( nr=1; nr< AS.length(); nr++){
564        as.append(i.getItem());
565        i++;
566        if ( degree(i.getItem()) > 1 ){// search for a non linear elem
567          elem=i.getItem();
568//        cout << "f=  " << elem << endl;
569//        cout << "as= " << as << endl;
570          qs= newfactoras(elem,as,success);
571//        cout << "irras:newfactoras    qs= " << qs << endl;
572//        qs= factoras(elem,as,success);
573//        cout << "irras:factoras qs= " << qs << endl;
574          if ( qs.length() > 1 || qs.getFirst().exp() > 1 ){ //found elem is reducible
575            reducible=elem;
576            ja=nr+1;
577            break;
578          }
579        }
580      }
581    }
582  }
583  for ( CFFListIterator k=qs; k.hasItem();k++)
584    ts.append(k.getItem().factor());
585  return ts;
586}
587///////////////////////////////////////////////////////////////////////////////
588/*
589$Log: not supported by cvs2svn $
590Revision 1.2  1997/04/25 22:52:28  michael
591changed cerr and cout messages for use with Singular
592Version for libfac-0.2.1
593
594*/
Note: See TracBrowser for help on using the repository browser.