1 // matrix.h 2 3 4 // This class is designed to handle the input of the integer programming 5 // problem. It offers facilities to convert a two-dimensional integer array 6 // into a matrix and to read a matrix from an input file. 7 // Furhermore, some special routines needed by the IP-algorithms are 8 // implemented: 9 // - the computation of a lattice basis for the integer kernel via the LLL 10 // algorithm; 11 // - the computation of a kernel vector which has no zero components (if 12 // such a vector exists) and is a basis vector for the kernel lattice; 13 // - the procedure of Hosten and Shapiro computing a small set of saturation 14 // variables for the toric ideal given by the matrix kernel. 15 16 17 18 #ifndef MATRIX_H 19 #define MATRIX_H 20 21 22 23 #include "LLL.h" 24 25 26 27 class matrix 28 { 29 30 31 32 private: 33 34 int rows; 35 36 int columns; 37 // Also used as error flag (values <0): 38 // -1 indicates a "semantic" error (which occurs e.g. if some constructor 39 // argument is out of range) 40 // -2 indicates an error occurred when reading from a file 41 42 Integer **coefficients; 43 // the matrix entries 44 45 BigInt **H; 46 // This array is used to store the LLL-reduced lattice basis of the kernel. 47 // Memory allocation is done in the LLL-routines, so the array is only 48 // allocated if such a basis is really computed. 49 50 int _kernel_dimension; 51 // the number of vectors stored in H (the size of these vectors is columns) 52 // If _kernel_dimension==-2, no kernel basis has been computed yet. 53 // If _kernel_dimension==-1, an error has occurred during the kernel basis 54 // computation. 55 56 57 58 public: 59 60 61 62 // constructors and destructor 63 64 matrix(const int& row_number, const int& column_number); 65 // Creates a zero matrix of the specified size. 66 67 matrix(const int& row_number, const int& column_number, 68 Integer** entries); 69 // Builds a matrix from its coefficient array. 70 71 matrix(ifstream& input); 72 // Reads a matrix from the given ifstream. 73 // The input stream must have the following format: 74 // 75 // m=number of rows 76 // n=number of columns 77 // coefficients 0..n-1 of row 1 78 // coefficients 0..n-1 of row 2 79 // ... 80 // coefficients 0..n-1 of row m 81 82 matrix(const int& m, const int& n, ifstream& input); 83 // Reads a (m x n)-matrix from the given ifstream. 84 // The input stream must have the following format: 85 // 86 // coefficients 0..n-1 of row 1; 87 // coefficients 0..n-1 of row 2; 88 // ... 89 // coefficients 0..n-1 of row m. 90 91 matrix(const matrix&); 92 // copy-constructor (also copies H) 93 94 ~matrix(); 95 // destructor 96 97 98 99 // object properties 100 101 BOOLEAN is_nonnegative() const; 102 // Returns TRUE, if all entries of the matrix are >=0, else FALSE. 103 104 int error_status() const; 105 // Returns columns iff columns<0 (this is the "error flag"), else 0. 106 107 int row_number() const; 108 // Retuns the row number. 109 110 int column_number() const; 111 // Returns the column number. 112 113 int kernel_dimension() const; 114 // Returns the kernel dimension. 115 116 117 118 // special routines for the IP-algorithms 119 120 int LLL_kernel_basis(); 121 // Computes a LLL-reduced integer basis of the matrix kernel and returns 122 // the kernel dimension (-1 if an error has occurred). 123 // This dimension is also stored in the member kernel_dimension. 124 125 int compute_nonzero_kernel_vector(); 126 // Transforms the kernel lattice basis stored in H so that it contains 127 // a vector whose components are all !=0; 128 // returns 0 if no such vector exists, else 1. 129 // If no such basis has been computed before, this is done now. 130 131 int compute_flip_variables(int*&); 132 // Computes a set of flip variables for the algorithm of DiBiase and 133 // Urbanke from a kernel vector with no zero components. 134 // Returns the size of that set if such a kernel vector exists, else -1. 135 // If necessary, such a vector is computed. 136 // The computed set is copied to the argument pointer (memory allocation 137 // is done in the routine) to be accessible for the calling function. 138 139 int hosten_shapiro(int*& sat_var); 140 // Computes a set of saturation variables for the ideal defined by the 141 // kernel lattice and returns the size of that set. 142 // If no lattice basis has been computed before, this is done now. 143 // The computed set is stored in the argument pointer (memory allocation 144 // is done in the routine) to be accessible for the calling function. 145 // This routine implements the most simple strategy for computing this set: 146 // The kernel vectors are examined in their actual. A "greedy" strategy 147 // choosing "clever" kernel vectors to begin with could give better results 148 // in many cases, but this is not guaranteed... 149 // (And what is a clever choice?) 150 151 // output 152 153 void print() const; 154 // Writes the matrix to the standard output medium. 155 156 void print(FILE*) const; 157 // Writes the matrix to the referenced file which has to be opened 158 // for writing before. 159 160 void print(ofstream&) const; 161 // Writes the matrix to the given ofstream. 162 163 friend class ideal; 164 // Our toric ideals are all constructed from matrices, and the matrix class 165 // is designed only for the needs of these constructors. So it would be 166 // unnecessary overhead to hide the matrix members from these constructors. 167 168 }; 169 #endif 170