source:git/IntegerProgramming/matrix.h

spielwiese
Last change on this file was 1a3778, checked in by Frédéric Chapoton <chapoton@…>, 17 months ago
fix some typos in IntegerProgramming
• Property mode set to `100644`
File size: 5.1 KB
Line
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// Furthermore, 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
27class matrix
28{
29
30
31
32private:
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
58public:
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  // Returns 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
Note: See TracBrowser for help on using the repository browser.