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 occured 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 occured 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 |
---|