Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/Group/include/AbelianGroupRep.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: AbelianGroupRep.h,v 1.7 2000/02/09 06:10:13 alex Exp $
00003  */
00004 
00005 // Copyright (C) 1994 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Definition of the AbelianGroupRep class
00009 //
00010 // Principal Author: Dmitry Bormotov, Alexei Myasnikov
00011 //
00012 // Status: in progress
00013 //
00014 // Usage:
00015 //
00016 // Special Notes:
00017 //
00018 // Revision History:
00019 //
00020 
00021 
00022 #ifndef _ABELIAN_GROUP_REP_H_
00023 #define _ABELIAN_GROUP_REP_H_
00024 
00025 
00026 #include "AbelianWord.h"
00027 #include "FPGroup.h"
00028 #include "Matrix.h"
00029 #include "PrimeNumbers.h"
00030 #include "File.h"
00031 
00032 // ---------------------------- AbelianGroupRep ---------------------------- //
00033 
00034 
00035 class AbelianSGPresentationRep;
00036 
00037 class AbelianGroupRep : public PureRep
00038 {
00039 
00040 public:
00041 
00042   /////////////////////////////////////////////////////////////////////////
00043   //                                                                     //
00044   //  Constructors:                                                      //
00045   //                                                                     //
00046   /////////////////////////////////////////////////////////////////////////
00047 
00048   AbelianGroupRep( const FPGroup& G, bool makeFile = false );
00049   // Constructs an abelian group with presentation G.
00050   // If bMakeFile is true, expression of new generators in terms
00051   // of old ones will be written in a file after the computation
00052   // is finished.
00053   
00054   // No default constructor, but it can be easily arranged by
00055   // combining default FPGroup constructor and previsious one.
00056 
00057   // Copy constructor and operator = provided by compiler
00058 
00059 
00060   /////////////////////////////////////////////////////////////////////////
00061   //                                                                     //
00062   // Accessors:                                                          //
00063   //                                                                     //
00064   /////////////////////////////////////////////////////////////////////////
00065 
00066   void computeCyclicDecomposition( );
00067   // *** Time consuming algorithm ! ***
00068   // Computes cyclic decomposition of the abelian group.
00069 
00070   void findPrimaryBasis();
00071   // *** Time consuming algorithm ! ***
00072   // Computes primary decomposition of the abelian group.
00073 
00074   bool haveCyclicDecomposition( ) const { return bHaveCyclicDecomposition; }
00075   // True if the cyclic decomposition has been computed.
00076 
00077   bool havePrimaryDecomposition( ) const { return primeBasisFound; }
00078   // True if the primary decomposition has been computed.
00079 
00080   Chars AbelianGroupRep::getFileName( ) const;
00081   // Returns name of the file containing new generators.
00082   // Calls error() if no file has been created.
00083   
00084   Chars getFileNameOfPDGens( ) const;
00085   // Returns name of the file containing generators for prime decomposition.
00086   // Calls error() if no file has been created.
00087 
00088   const FPGroup getFPGroup( ) const { return theGroup; }
00089   // Returns the original group presentation.
00090 
00091 
00092   SetOf<Word> getAllRelators( ) const;  
00093   // Returns all relators of the original group plus all commutators.
00094 
00095 
00096   AbelianWord oldInAbelianForm( const Word& w ) const {
00097     return AbelianWord( theGroup.numberOfGenerators(), w );
00098   }
00099   // Computes the abelian form of a word written in terms of 
00100   // the old generators.
00101 
00102   /////////////////////////////////////////////////////////////////////////
00103   //  
00104   //  The rest of the public functions in the class can be used only if
00105   //  the cyclic decomposition is computed.
00106   //
00107   //
00108 
00109   int rankOfFreeAbelianFactor( ) const;
00110   // Returns rank of the free part.
00111 
00112   VectorOf<Integer> invariants( ) const;
00113   // Return the invariants m_i such that m_i | m_{i+1}. All m_i > 1.
00114 
00115   VectorOf<AbelianWord> oldToNewGens() const;
00116   // Returns images of the old generators in terms of the
00117   // new set of generators.
00118     
00119   VectorOf<AbelianWord> newToOldGens() const;
00120   // Returns images of the new generators in terms of the
00121   // new set of generators.
00122 
00123   AbelianGroupRep getCanonicalSmithPresentation( ) const;
00124   // Returns the cyclic decomposition as an object of the class 
00125   // AbelianGroupRep. In that object the new generators and the old 
00126   // generators are the same; the cyclic decomposition, invariants, 
00127   // the rank of free part and transformation vectors are already computed.
00128     
00129   
00130   /////////////////////////////////////////////////////////////////////////
00131   //                                                                     //
00132   //  Methods and operators which deal with the group:                   //
00133   //                                                                     //
00134   /////////////////////////////////////////////////////////////////////////
00135 
00136   Integer order() const;
00137   // Returns order of the group, 0 means infinity.
00138 
00139   bool isTrivial() const;
00140   // Returns true if the group is trivial.
00141 
00142   bool isFree() const;
00143   // Returns true if the group is free.
00144  
00145   bool isomorphicTo( const AbelianGroupRep& G) const;
00146   // Returns true if the group is isomorphic to G.
00147 
00148   AbelianGroupRep computeIntegralHomology( int n ) const;
00149   // Returns the H_n group of this one.
00150   
00151   /////////////////////////////////////////////////////////////////////////
00152   //                                                                     //
00153   //  Methods and operators which deal with subgroups:                   //
00154   //                                                                     //
00155   /////////////////////////////////////////////////////////////////////////
00156 
00157   Integer orderOfTheTorsionSubgroup() const;
00158   // Returns order of the torsion subgroup.
00159   
00160   AbelianSGPresentationRep makeSubgroupPresentation(const VectorOf<Word>& vG) const;
00161   // *** Time consuming algorithm ! ***
00162  // Makes presentation of subgroup as a group 
00163 
00164   VectorOf<Word> findSubgroupIsolator(const VectorOf<Word>& vG) const;
00165   // *** Time consuming algorithm ! ***
00166   // Returns the generators of Isolator of given subgroup
00167 
00168   VectorOf<Word> findVirtFreeComplementOfSG(const VectorOf<Word>& vG) const;
00169   // *** Time consuming algorithm ! ***
00170   // returns generators of virtual free complement, of a given subgroup
00171 
00172   VectorOf<Word> joinSubgroups(const VectorOf<Word>& vG1,const VectorOf<Word>& vG2) const;
00173   // Returns the generators of join subgroup of given groups
00174   
00175   VectorOf<Word> findSubgIntersection( const VectorOf<Word>& vG1 ,
00176                                        const VectorOf<Word>& vG2 , 
00177                                        File& file ) const;
00178   // Returns the generators for intersection of given subgroups   
00179   
00180   bool isPureCyclSubgroup(const Word& w) const;
00181   // True if given cyclic subgroup is pure
00182   /////////////////////////////////////////////////////////////////////////
00183   //                                                                     //
00184   //  Methods which deal with group elements:                            //
00185   //                                                                     //
00186   /////////////////////////////////////////////////////////////////////////
00187 
00188   bool areEqual( const Word&, const Word& ) const;
00189   // Returns true if u and v are equal.
00190 
00191   bool isTrivial( const Word& ) const;
00192   // Word problem.
00193 
00194   Integer orderOfElt( const Word& ) const;
00195   // Returns the order of an element, 0 means infinity.
00196 
00197   AbelianWord newToOldGens( const AbelianWord& ) const;
00198   // Converts an element from the new generators to the old ones.
00199 
00200   AbelianWord oldToNewGens( const AbelianWord& ) const;
00201   // Converts an element from the old generators to the new ones.
00202 
00203   AbelianWord findEltPrimeForm(const Word& w) const;
00204   // Converts an element from the old generators to the prime form ones.
00205   
00206   AbelianWord pBlockOfElt( const AbelianWord& w,Integer p )const;
00207   // Returns a p-block of an element. 
00208 
00209   Integer pHeightOfElt(const Word& w, const Integer& p, Integer orderofElt) const;
00210   // Returns a p-height of a given alement. The orderofElt - is an order of
00211   // an element. If it -1, it will computed in the procedure.
00212 
00213   Integer powerOfEltInSubgroup(const Word& w,const VectorOf<Word>& sGroup) const;
00214   // Returns the power of element in subgroup
00215 
00216   bool isEltProperPower(const Word& w) const;
00217   // *** Time consuming algorithm ! ***
00218   // True if element is proper power
00219 
00220   void abelianMaximalRoot(const Word& w, Word& maxRoot, Integer& maxExp) const;
00221   // *** Time consuming algorithm ! ***
00222   // Compute the maximal root of an element. Put maximal root in  maxRoot and
00223   // maximal exponent in maxExp. If maxExp is 0, than there is no maximal root fpr
00224   // this element
00225 
00226   AbelianWord primeFormInOldGens(const AbelianWord& w) const;
00227   // Converts an element in prime form  to the old generators.
00228 
00229   int isPowerOfSecond(const Word& word1, const Word& word2) const;
00230   // *** Time consuming algorithm ! ***
00231   // If word1 is a power of word2, returns the power, if not returns 0
00232 
00233   /////////////////////////////////////////////////////////////////////////
00234   //                                                                     //
00235   //  Methods which deal with morpgisms:                                 //
00236   //                                                                     //
00237   /////////////////////////////////////////////////////////////////////////
00238 
00239   Bool isEpimorphism(const VectorOf<Word>& V) const;
00240   // *** Time consuming algorithm ! ***
00241   // Returns TRUE iff generating vector `V' defines an 
00242   // epimorphism of this group. The length of `V' should be
00243   // equal to the number of generators of this group. 
00244 
00245   int orderOfAuto(const VectorOf<Word>& V) const;
00246   // *** Time consuming algorithm ! ***
00247   // Returns the order of Automorphism defined by V. 
00248   // If check == true, checks is it automorphism.
00249 
00250   VectorOf<Word> inverseAuto(const VectorOf<Word>& V) const;
00251 
00252   // *** Time consuming algorithm ! ***
00253   // Returns the inverse  of automorphism, defined by V. 
00254   // Does not make check is it automorphism or not!!!
00255 
00256   VectorOf<Word> fixedPointsOfAuto( const VectorOf<Word>& v ) const;
00257   // Returns the generating set for the subgroup of fixed points of the 
00258   // automorphism defined by v.
00259   // Does not make check is it automorphism or not!!!
00260 
00261   /////////////////////////////////////////////////////////////////////////
00262   //                                                                     //
00263   // I/O:                                                                //
00264   //                                                                     //
00265   /////////////////////////////////////////////////////////////////////////
00266   
00267   void printOn( ostream& ) const;
00268   // Print the cyclic decomposition in the form, like Z^5 x Z_2 x Z_4^2 ...
00269   
00270   void printWordInNewGens( ostream&, const AbelianWord& ) const;
00271   // Print a word in the new generators in additive notation.
00272 
00273   void printInPrimaryForm(ostream& ostr, const AbelianWord& aw) const;
00274   // Print a word in primary form: f1 + 2 p2 ... (aw must be in prime form)
00275 
00276   void printPrimaryDec( ostream& ostr) const;
00277   // Print the prymary decomposition in the form, like Z^5 x Z_2 x Z_4 x Z_3 ...
00278 
00279  
00280   /////////////////////////////////////////////////////////////////////////
00281   //                                                                     //
00282   // IPC tools:                                                          //
00283   //                                                                     //
00284   /////////////////////////////////////////////////////////////////////////
00285 
00286   virtual void write( ostream& ostr ) const;
00287 
00288   virtual void read( istream& istr );
00289 
00290   /////////////////////////////////////////////////////////////////////////
00291   //                                                                     //
00292   //  Representation methods:                                            //
00293   //                                                                     //
00294   /////////////////////////////////////////////////////////////////////////
00295   
00296   AbelianGroupRep* clone( ) const { return new AbelianGroupRep(*this); }
00297   // overrides PureRep::clone()
00298 
00299 protected:
00300   Chars theFileName;       
00301   // Name of that file.
00302 
00303   Chars theFileNameOfPD;
00304   // Name of file, with generators for Primary decomposition.
00305 
00306   int numOfGensInTorsionPartOfPD() const{
00307      return primeBasicMatrix.height();
00308   }
00309   // Returns the number of generators in torsion part of primary decomposition
00310 private:
00311 
00312   /////////////////////////////////////////////////////////////////////////
00313   //                                                                     //
00314   // Data Members:                                                       //
00315   //                                                                     //
00316   /////////////////////////////////////////////////////////////////////////
00317 
00318   const FPGroup theGroup;  
00319   // The original group.
00320 
00321   bool bMakeFile;          
00322   // If true the file with the new generators will be created.  
00323   
00324   bool bHaveCyclicDecomposition; 
00325   // True if the cyclic decomposition has been computed.
00326 
00327   int numOfNewGens;              
00328   // Number of the new generators, i.e rank of free part plus
00329   // number of invariants in the group.
00330   
00331   int rankOfFreePart;
00332   // The number of free generators in the cyclic decompostion.
00333 
00334   VectorOf<Integer> theInvariants;
00335   // Contains invariants m_i such that m_i | m_{i+1}. All m_i > 1.
00336   
00337   VectorOf<AbelianWord> theNewToOldGens;
00338   // Images of the new generators in terms of the new set of generators.
00339 
00340   VectorOf<AbelianWord> theOldToNewGens;
00341   // Images of the old generators in terms of the new set of generators.
00342 
00343   bool primeBasisFound;
00344   // True if the primary decomposition has been computed.
00345 
00346   int invariantToNewGens( int inv, Integer orderOfCyclic,
00347                            int stPos,Integer power = 1);
00348   // Computes the image of generators of canonical decomposition
00349   // in generators of primary decomposition.
00350   // Warning! Don't call this procedure unless you know what are you
00351   // doing.
00352 
00353   DArray<Integer> primeBasicMatrix;
00354   // Matrix with prime decompozition information. It consists of
00355   // primes, their powers (which are the orders of cyclic subgroups),
00356   // index of invariants, from wich primes were found, and images
00357   // of the primary generators in terms of the set of generators of
00358   // canonical decomposition and vise versa.
00359 
00360   // The following data members are suppose to be local variables 
00361   // in the function computeCyclicDecomposition(), but they are here
00362   // to avoid sending them all the time to that function`s auxiliary 
00363   // methods. 
00364 
00365   Integer** matrix; // the main matrix containing all the original relators
00366   int height;       // height of the main matrix
00367   int width;        // width of the main matrix
00368   Integer** newToOldGensMatrix; // transformation matrix
00369   Integer** oldToNewGensMatrix; // transformation matrix
00370 
00371 
00372   /////////////////////////////////////////////////////////////////////////
00373   //                                                                     //
00374   // Private methods:                                                    //
00375   //                                                                     //
00376   /////////////////////////////////////////////////////////////////////////
00377 
00378 
00379   /////////////////////////////////////////////////////////////////////////
00380   //
00381   // The following list of functions are for computeCyclicDecomposition()
00382   // only.
00383   //
00384   //
00385 
00386   void fillTransformationVectors( );
00387   // Commit the necessary information from the transformation matrices
00388   // to the transformation vectors. 
00389 
00390   void addColumn( int i, int j, Integer k );
00391   // Add k j-th columns to the i-th column in matrix, 
00392   // the transformation matrices changes accordingly.
00393   
00394   void swapColumns( int i, int j );
00395   // Swaps the i-th and j-th columns in matrix,
00396   // the transformation matrices changes accordingly.
00397 
00398   void swapGenColumns( int i, int j );
00399   // To be used in swapColumns(),
00400   // the transformation matrices changes accordingly.
00401  
00402   void canoniseInvariants( int i, int j );
00403   // Writes invariants in the proper order
00404 
00405   void swapInvariants( int i, int j );
00406   // To be used in canoniseInvariants()
00407   
00408   void makeTransformationMatrices( );
00409   // Initilaizes the transformation matrices.
00410   
00411   void makeMainMatrix( );
00412   // Initilaizes the main matrix.
00413 
00414   void destroyMatrices( );
00415   // Destroys all three matrices.
00416 
00417   virtual void makeFile( );
00418   // Creates the file containing the expression of the new generators
00419   // in terms of the old ones.
00420 
00421   virtual void makeFileOfPDGens( );
00422   // Creates the file containing the expression of the primary generators
00423   // in terms of the old ones.
00424 
00425  AbelianSGPresentationRep buildTorsionFreePresentation
00426             ( Matrix<Integer>& gensTransformation, const VectorOf<Word>& vG)const;
00427   //Build ubgroup presentation witout torsion part. New generators, presented
00428   // by rows of gensTransformation matrix.
00429 
00430   void sortVector(DArray<Integer>& vc,int colSort,int start, int finish);
00431   void sortPrimeDecom(DArray<Integer>& m);
00432   // This procedures makes sort of primeBasicMatrix.  
00433   
00434   void minimizeWordInNewGens( AbelianWord& w ) const;
00435   // Garanties that all powers of generators of the torsion part will
00436   // be less than corresponding orders of the generators.
00437 
00438   bool isAllZero(int from, int to,MatrixRow<Integer>& vc) const;
00439   // Checks the subvector elements to be zero, returns true if all zeros
00440 
00441   Bool matrixMult(const Matrix<Integer>& m,bool haveTorsion) const;
00442 
00443   /////////////////////////////////////////////////////////////////////////
00444   //                                                                     //
00445   // Debugging stuff:                                                    //
00446   //                                                                     //
00447   /////////////////////////////////////////////////////////////////////////
00448 
00449   
00450 #ifdef debug_AbelianGroup
00451   void printMatrix(char *name, Integer **A, int height, int width);
00452   friend int main( );
00453 #endif
00454 
00455 };
00456 
00457 #endif
00458 
00459 
00460 

Generated at Tue Jun 19 09:49:36 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001