affinealgebras.H

#ifndef _AFFINEALGEBRAS_H_
#define _AFFINEALGEBRAS_H_

#include <fstream>
#include <iostream>
#include "algebras.H"
#include <string>
#include "alphabet.H"
using namespace std;




template <class K>
class AffineAlgebra : public SimpleAlphabet {
public:

  // data ///////////////////////////////////////

  bool verbose;
  bool very_verbose;

  Ideal<K> relations;


  AffineAlgebra<K>(){
    verbose= false;
    very_verbose= false;
  }

  // little things /////////////////////////////////////////////////


  Polynomial<K> new_variable(const string& name){
    Polynomial<K> ans;

    SimpleAlphabet::new_variable(name);
    ans= Polynomial<K>( PowProd( var_in_use )  );
    ans.alphabet= this;

    return ans;
  }
  Polynomial<K> one() const {
    Polynomial<K> ans;

    ans= Polynomial<K>( PowProd(0) );
    ans.alphabet= (Alphabet *) this;

    return ans;

  }
 
  Tuple< Polynomial<K> > get_variables() const 
  {
    Tuple< Polynomial<K> > ans;
    
    ans.resize(this->var_in_use + 1);
    for(long i=0; i<= this->var_in_use; i++){
      ans[i]= Polynomial<K>( PowProd(i) );
      ans[i].alphabet= (Alphabet *) this;
    }
    return ans;
  }

  void add_relation(const Polynomial<K>& rel){
    if( !rel.is_zero() )
      relations.generators.push_back( rel );
  }
  long count_relations() const {
    long ans=0;
    typename list< Polynomial<K> >::const_iterator it;

    for(it= relations.generators.begin();
        it!= relations.generators.end();
        it++)
      ans++;

    return ans;
  }

  virtual void fix_alphabets(){
    typename list< Polynomial<K> >::iterator it;

    for(it= relations.generators.begin();
        it != relations.generators.end();
        it++)
      it->alphabet= this;
  }

  // things to do with grobner basis ////////////////////////////////


  void find_grobner_basis(){
    relations.grobnerize();
    // relations.minimalize();
  }
  void reduce_grobner_basis(){
    relations.reduce();
  }
  Polynomial<K> reduced_form(const Polynomial<K>& f) const {
    return division_remainder(f, relations.generators);
  }

  // return some info on the algebra //////////////////////////////


  bool is_finite_dimensional() const {
    typename list< Polynomial<K> >::const_iterator it;
    PowProd pow;
    long i, j;

    for(i=1; i<= var_in_use; i++){
      
      // is there a relation whose lp() is a power of variable i ?
      for(it= relations.generators.begin();
          it!= relations.generators.end();
          it++){
        
        
        pow= it->lp();
        
        if( pow.nvars() == i ){
          for(j=1; j < i; j++)
            if( pow.power_of(j) != 0 )
              break; // out of for j loop
          if (j == i ) // all went okay ?
            break; // out of for it loop
        }
      }
      if( it == relations.generators.end() ) // could not find one ?
        return false;
    }
    
    return true;
  }
  bool is_polynomial_variable(const Polynomial<K>& P) const {
    Polynomial<K> Q;
    long var;

    var= P.lp().nvars();
    Q= Polynomial<K>( PowProd(var) );
    Q+= P*(-1);

    if(!Q.is_zero())
      return false;

    if( relations.variable_shows_up( var ) )
      return false;

    return true;
  }


  // simple modifications to the algebra ////////////////////////////


  virtual void swap_variables_order(long i, long j, list< Polynomial<K> >& polys){
    typename list< Polynomial<K> >::iterator it;
    string dummy;

    for(it= relations.generators.begin(); 
        it!= relations.generators.end(); 
        it++)
      it->swap_variables(i,j);
  
    for(it= polys.begin(); 
        it!= polys.end(); 
        it++)
      it->swap_variables(i,j);


    dummy= names[i];
    names[i]= names[j];
    names[j]= dummy;


  }

virtual  void swap_variables_order(long i, long j){
    list< Polynomial<K> > empty_list;

    this->swap_variables_order(i,j,empty_list);
  }


  void tensor_with(const AffineAlgebra<K>& that)
  {
    long i, n;
    typename list< Polynomial<K> >::const_iterator it;
    Polynomial<K> P;
    
    
    n= this->var_in_use;
    
    for(i=1; i<= that.variables_in_use(); i++)
      new_variable( that.nameof(i) );
    
    for(it= that.relations.generators.begin();
        it!= that.relations.generators.end();
        it++){
      P= *it;
      P.shift_variables(n);
      add_relation(P);
    }
    
    fix_alphabets();
  }
  




  // methods to look for redundancies and find a simpler presentation



  bool top_variable_redundant(Polynomial<K>& result){
    typename list< Polynomial<K> >::iterator it;
    PowProd top_var;
    K c;
    // does the varianle show up at all?
    if( !relations.variable_shows_up(var_in_use) )
      return false;

    // otherwise, we need LEX
    if(PowProd::current_order() != LEX){
      cerr << "Error: killing variables requires LEX order" << endl;
      return false;
    }

    find_grobner_basis();

    top_var= PowProd( var_in_use );
    

    for(it= relations.generators.begin(); 
        it!= relations.generators.end() && !(it->lp()==top_var); 
        it++);

    if( it== relations.generators.end() )
      return false;
    //else...
    c= it->lc();
    result= *it;
    result.add_term(top_var, -c);
    c= -1/c;
    result*= c;
    return true;

  }


  bool variable_redundant(long var, Polynomial<K>& result) const {
    int old_order;
    long old_priority;    
    PowProd pow;
    typename list< Polynomial<K> >::iterator it;
    Ideal<K> test;
    bool ans;
    K c;

    test= relations;

    old_order= Polynomial<K>::get_order_override();
    old_priority= Polynomial<K>::get_variable_priority();
    Polynomial<K>::set_order_override(DEGLEXSV);
    Polynomial<K>::set_variable_priority(var);

    //    find_grobner_basis();
    test.grobnerize();

    pow= PowProd( var );
    for(it= test.generators.begin(); 
        it!= test.generators.end() && !(it->lp()==pow); 
        it++);

    if( it== test.generators.end() )
      ans= false;
    else{
      c= it->coeff_of(pow);
      result= *it;
      result.add_term(pow, -c);
      c= -1/c;
      result*= c;
      ans= true;
    }

    Polynomial<K>::set_order_override(old_order);
    Polynomial<K>::set_variable_priority(old_priority);
    return ans;
  }


  virtual void kill_top_variable(const Polynomial<K>& replacement, list< Polynomial<K> >& polys){
    typename list< Polynomial<K> >::iterator it;

    it= relations.generators.begin();
    while(it!= relations.generators.end()){
      it->substitute_variable(var_in_use,replacement);
      if( !it->is_zero() )
        it++;
      else
        it= relations.generators.erase(it);
    }

    for(it= polys.begin(); it!= polys.end(); it++)
      it->substitute_variable(var_in_use,replacement);

    names.erase(var_in_use);
    var_in_use--;

  }

  void kill_top_variable(const Polynomial<K> replacement){
    list< Polynomial<K> > empty_list;

    this->kill_top_variable(replacement, empty_list);
  }

  void kill_variable(long var, const Polynomial<K>& replacement,list< Polynomial<K> >& polys){

    polys.push_front(replacement);
    this->swap_variables_order(var, var_in_use, polys);
    this->kill_top_variable( *polys.begin(), polys);
    polys.erase( polys.begin() );
  }

  void kill_variable(long var, const Polynomial<K>& replacement){
    list< Polynomial<K> > empty_list;

    kill_variable(var, replacement, empty_list);
  }


  void cut_down_variables(list< Polynomial<K> >& polys){
    long leftvar;
    Polynomial<K> relation;
    typename list< Polynomial<K> >::iterator it;


    for(leftvar= 1; 
        leftvar <= var_in_use && !relations.variable_shows_up(leftvar);
        leftvar++);

    while( leftvar <= var_in_use ){
      if(very_verbose)
        cout << "trying to kill variable " << names[leftvar] << "..." << endl;

      if( variable_redundant(leftvar, relation) ){
        if(verbose){
          cout << "Redundancy found! variable  "
               << names[leftvar] << " = " 
               << relation << endl;
        }
        this->kill_variable(leftvar, relation, polys);
      }
      else{

        for(leftvar++; 
        leftvar <= var_in_use && !relations.variable_shows_up(leftvar);
        leftvar++);
      }

    }// end of WHILE
  }
  
  void cut_down_variables(){
    list< Polynomial<K> > empty_list;

    cut_down_variables(empty_list);
  }


  AbstractHomomorphism<K> find_redundancies(){
    bool grobner_done;
    long nb_relations, current_relation, var;
    list< Polynomial<K> > structure_constants;
    Polynomial<K> rel;
    typename list< Polynomial<K> >::iterator it;
    AbstractHomomorphism<K> ans, temphom;
    

    if(verbose)
      cout << "{\\bf Now reducing variables and relations}"
           << endl << endl;

    grobner_done= false;
    ans.make_identity(this->var_in_use);
    
    
    nb_relations= 0;
    current_relation= 1;
    structure_constants= relations.generators;
    relations.generators.clear();
    
    for(it= structure_constants.begin(); 
        it!= structure_constants.end();){
      
      if( (var= it->has_lonely_variable(rel)) > 0 ){
        if(very_verbose)
          cout << "relation " << current_relation
               << " yields a variable redundancy: $"
               << this->nameof(var) << " = " << rel 
               << "$" << endl << endl;
        it= structure_constants.erase(it);
        kill_variable(var, rel, structure_constants);
        grobner_done= false;
        // now write the corresponding homomorphism
        rel.swap_variables(var, this->var_in_use + 1); // rel itself must be updated !!
        temphom.make_identity(this->var_in_use + 1);
        temphom.set_image(this->var_in_use + 1, Polynomial<K>( PowProd(var) ) );
        temphom.set_image(var, rel);
        ans= temphom * ans;
      }
      else{
        
        if( !grobner_done ){
          find_grobner_basis();
          reduce_grobner_basis();
          grobner_done= true;
        }
        rel= reduced_form( *it );
        if( !rel.is_zero() ){
          nb_relations++;
          if(very_verbose)
            cout << "adding relation " << current_relation
                 << " (total " << nb_relations << " relations added): "
                 << "$" << rel << "$" << endl << endl;
          add_relation(rel);
          grobner_done= false;
          it++;
        }
        else{
          if(very_verbose)
            cout << "relation " << current_relation << " redundant"
                 << endl << endl;
          it= structure_constants.erase(it);
        }
      }
      current_relation++;
    }
    //cut_down_variables();
    if(verbose)
      cout << "{\\bf Final presentation: } " 
           << var_in_use << " variables kept, " 
           << nb_relations << " relations kept" 
           << endl << endl;
    
    relations.generators= structure_constants;
    return ans;
  }
  

  AbstractHomomorphism<K> find_unitary_redundancies(){
    bool grobner_done;
    long nb_relations, current_relation, var;
    list< Polynomial<K> > structure_constants;
    Polynomial<K> rel;
    typename list< Polynomial<K> >::iterator it;
    AbstractHomomorphism<K> ans, temphom;
    
    grobner_done= false;
    
    
    nb_relations= 0;
    current_relation= 1;
    structure_constants= relations.generators;
    relations.generators.clear();
    
    for(it= structure_constants.begin(); 
        it!= structure_constants.end();){
      
      if( (var= it->has_unitary_variable(rel)) > 0 ){
        if(verbose)
          cout << "relation " << current_relation
               << " yields a variable redundancy: $"
               << this->nameof(var) << " = " << rel 
               << "$" << endl << endl;
        it= structure_constants.erase(it);
        kill_variable(var, rel, structure_constants);
        grobner_done= false;
        // now write the corresponding homomorphism
        rel.swap_variables(var, this->var_in_use + 1); // rel itself must be updated !!
        temphom.make_identity(this->var_in_use + 1);
        temphom.set_image(this->var_in_use + 1, Polynomial<K>( PowProd(var) ) );
        temphom.set_image(var, rel);
        ans= temphom * ans;
      }
      else{
        
        if( !grobner_done ){
          find_grobner_basis();
          reduce_grobner_basis();
          grobner_done= true;
        }
        rel= reduced_form( *it );
        if( !rel.is_zero() ){
          nb_relations++;
          if(very_verbose)
            cout << "adding relation " << current_relation
                 << " (total " << nb_relations << " relations added): "
                 << "$" << rel << "$" << endl << endl;
          add_relation(rel);
          grobner_done= false;
          it++;
        }
        else{
          if(very_verbose)
            cout << "relation " << current_relation << " redundant"
                 << endl << endl;
          it= structure_constants.erase(it);
        }
      }
      current_relation++;
    }
    //cut_down_variables();
    if(verbose)
      cout << "{\\bf Final presentation: } " 
           << var_in_use << " variables kept, " 
           << nb_relations << " relations kept" 
           << endl << endl;
    
    relations.generators= structure_constants;
    return;
  }
  



  // friend printing ////////////////////////////////////////////

  friend ostream& operator<<(ostream& os, const AffineAlgebra<K>& R){
    typename map<long, string>::const_iterator it_gen;
    typename list< Polynomial<K> >::const_iterator it_rel;

    os << "generators:" << endl;
    for(it_gen= R.names.begin(); it_gen!= R.names.end(); it_gen++)
      os << it_gen->second << " ";

    os << endl << "relations:" << endl;
    for(it_rel=R.relations.generators.begin(); 
        it_rel!= R.relations.generators.end(); it_rel++)
      os << *it_rel << endl;

    return os;
  }

friend ofstream& operator<<(ofstream& file, AffineAlgebra<K>& x){
  long n;
  n= x.count_relations();
  file << n << " ";


 typename list< Polynomial<K> >::iterator it;
 for(it= x.relations.generators.begin();
     it!= x.relations.generators.end();
     it++)
   file << *it;



 file << x.var_in_use << " ";
 for(long i=1; i <= x.var_in_use; i++)
   file << x.nameof(i) << " ";

 return file;
}

friend void operator>>(ifstream& file, AffineAlgebra<K>& x){
  long n, nv;
  Polynomial<K> P;

  // first delete everything !
  x.relations.generators.clear();
  nv= x.var_in_use;
  Polynomial<K> zero;
  zero.sets_to_zero();
  for(long i=1; i <= nv; i++)
    x.kill_top_variable(zero);

  // read the relations
  file >> n;
  P.alphabet= &x;
  while(n > 0){
    file >> P;
    x.add_relation(P);
    n--;
  }
  //read the variables
  file >> nv;
  string name;
  while(nv > 0){
    file >> name;
    x.new_variable(name);
    nv--;
  }



}



};






#endif

---