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

/magnus/back_end/Group/include/SmithNormalForm.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: SmithNormalForm.h,v 1.2 1996/04/30 21:11:47 bormotov 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 SmithNormalForm utility class.
00009 //           This encapsulates the computation which puts
00010 //           an Integer matrix into diagonal form.
00011 //
00012 // Principal Authors: Sergei Lyutikov, Roger Needham
00013 //
00014 // Status: provisional
00015 //
00016 // Special Remarks:
00017 //
00018 // * The libg++ Integer class uses the basic wrapped pointer scheme,
00019 //   "However, constructors and assignments operate by copying entire
00020 //    representations, not just pointers."
00021 //   This does not impose an unacceptable cost here, since the Integers
00022 //   will not typically be enormous, and objects in this class will not
00023 //   be instantiated very frequently.
00024 //   If these assumptions change, we can replace type Integer with
00025 //   type Integer* in the computations.
00026 //
00027 // Revision History:
00028 //
00029 // * 6/95 Roger adapted this from class Abelianization.
00030 //
00031 
00032 #ifndef _SMITH_NORMAL_FORM_H_
00033 #define _SMITH_NORMAL_FORM_H_
00034 
00035 
00036 #include "ExtendedIPC.h"
00037 
00038 #include "Vector.h"
00039 
00040 
00041 class SmithNormalForm {
00042 public:
00043 
00044   //////////////////////////////////////////////////////////////
00045   //                                                          //
00046   // Constructors:                                            //
00047   //                                                          //
00048   //////////////////////////////////////////////////////////////
00049 
00050   SmithNormalForm(Integer** theMatrix, int rows, int cols);
00051   // This reduces theMatrix in place, and deletes it when done.
00052 
00053   /////////////////////////////////////////////////////////////////////////
00054   //                                                                     //
00055   // Activation members:                                                 //
00056   //                                                                     //
00057   /////////////////////////////////////////////////////////////////////////
00058 
00059   bool continueComputation( );
00060   // Return true iff the computation is complete.
00061 
00062   /////////////////////////////////////////////////////////////////////////
00063   //                                                                     //
00064   // Accessors:                                                          //
00065   //                                                                     //
00066   /////////////////////////////////////////////////////////////////////////
00067 
00068   int getTorsionFreeRank( ) const;
00069   // It is an error to call this unless continueComputation() has returned
00070   // true.
00071 
00072   VectorOf<Integer> getTorsionInvariants( ) const;
00073   // It is an error to call this unless continueComputation() has returned
00074   // true.
00075 
00076 
00077 private:
00078 
00079   /////////////////////////////////////////////////////////////////////////
00080   //                                                                     //
00081   // Data Members:                                                       //
00082   //                                                                     //
00083   /////////////////////////////////////////////////////////////////////////
00084 
00085   Integer** matrix;
00086   // The matrix we are reducing in place
00087 
00088   int height, width;
00089 
00090   // The answer:
00091 
00092   VectorOf<Integer> theInvariants;
00093   int               rankOfFreePart;
00094 
00095   // Control variables for continueComputation():
00096   
00097   int i, j;
00098 
00099   VectorOf<Integer> resultTemp;
00100 
00101   bool done;
00102   
00103   /////////////////////////////////////////////////////////////////////////
00104   //                                                                     //
00105   // Private methods:                                                    //
00106   //                                                                     //
00107   /////////////////////////////////////////////////////////////////////////
00108 
00109   Integer abs( const Integer& a ) const { return ( a > 0 ) ? a : -a; }
00110 
00111   Integer sign( const Integer& a ) const {
00112          if ( a == 0 ) return 0;
00113          return ( a > 0 ) ? 1 : -1;
00114   }
00115 
00116   Integer GCD( Integer a, Integer b ) const;
00117 
00118 };
00119 
00120 #endif

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