source: git/libfac/charset/charset.cc @ 3e55bc

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