CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

Views: 418423
1
/*
2
* Normaliz
3
* Copyright (C) 2007-2014 Winfried Bruns, Bogdan Ichim, Christof Soeger
4
* This program is free software: you can redistribute it and/or modify
5
* it under the terms of the GNU General Public License as published by
6
* the Free Software Foundation, either version 3 of the License, or
7
* (at your option) any later version.
8
*
9
* This program is distributed in the hope that it will be useful,
10
* but WITHOUT ANY WARRANTY; without even the implied warranty of
11
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
* GNU General Public License for more details.
13
*
14
* You should have received a copy of the GNU General Public License
15
* along with this program. If not, see <http://www.gnu.org/licenses/>.
16
*
17
* As an exception, when this program is distributed through (i) the App Store
18
* by Apple Inc.; (ii) the Mac App Store by Apple Inc.; or (iii) Google Play
19
* by Google Inc., then that store may impose any digital rights management,
20
* device limits and/or redistribution restrictions that are required by its
21
* terms of service.
22
*/
23
//---------------------------------------------------------------------------
24
#ifndef VECTOR_OPERATIONS_H
25
#define VECTOR_OPERATIONS_H
26
//---------------------------------------------------------------------------
27
28
#include <vector>
29
#include <ostream>
30
#include <list>
31
32
#include <libnormaliz/libnormaliz.h>
33
#include <libnormaliz/integer.h>
34
#include <libnormaliz/convert.h>
35
36
namespace libnormaliz {
37
using std::vector;
38
39
//---------------------------------------------------------------------------
40
// Data access
41
//---------------------------------------------------------------------------
42
43
template <typename T>
44
std::ostream& operator<< (std::ostream& out, const vector<T>& vec) {
45
for (size_t i=0; i<vec.size(); ++i) {
46
out << vec[i] << " ";
47
}
48
out << std::endl;
49
return out;
50
}
51
52
//---------------------------------------------------------------------------
53
// Vector operations
54
//---------------------------------------------------------------------------
55
template<typename Integer>
56
Integer v_scalar_product(const vector<Integer>& a,const vector<Integer>& b);
57
58
template<typename Integer>
59
bool v_scalar_product_nonnegative(const vector<Integer>& a,const vector<Integer>& b);
60
61
template<typename Integer>
62
bool v_scalar_product_positive(const vector<Integer>& a,const vector<Integer>& b);
63
64
//returns the scalar product of the truncations of vectors a and b to minimum of lengths
65
template<typename Integer>
66
Integer v_scalar_product_vectors_unequal_lungth(const vector<Integer>& a,const vector<Integer>& b);
67
68
//returns the addition a + b, vectors must be of equal size
69
template<typename Integer>
70
vector<Integer> v_add(const vector<Integer>& a,const vector<Integer>& b);
71
template<typename Integer>
72
vector<Integer> v_add_overflow_check(const vector<Integer>& a,const vector<Integer>& b);
73
template<typename Integer>
74
void v_add_result(vector<Integer>& result, const size_t length, const vector<Integer>& a,const vector<Integer>& b);
75
76
//adds b to a reduces the result modulo m, a and b must be reduced modulo m!
77
template<typename Integer>
78
vector<Integer>& v_add_to_mod(vector<Integer>& a, const vector<Integer>& b, const Integer& m);
79
80
//---------------------------------------------------------------------------
81
// abs, gcd and lcm
82
//---------------------------------------------------------------------------
83
84
// takes the absolute value of the elements and returns a reference to the changed vector
85
template<typename Integer>
86
vector<Integer>& v_abs(vector<Integer>& v);
87
88
// returns the vector of absolute values, does not change the argument
89
template<typename Integer>
90
vector<Integer> v_abs_value(vector<Integer>& v);
91
92
//returns gcd of the elements of v
93
template<typename Integer>
94
Integer v_gcd(const vector<Integer>& v);
95
96
//returns lcm of the elements of v
97
template<typename Integer>
98
Integer v_lcm(const vector<Integer>& v);
99
100
//returns lcm of the elements of v from index k up to index j
101
template<typename Integer>
102
Integer v_lcm_to(const vector<Integer>& v,const size_t k, const size_t j);
103
104
//divides the elements by their gcd and returns the gcd
105
template<typename Integer>
106
Integer v_make_prime(vector<Integer>& v);
107
108
nmz_float l1norm(vector<nmz_float>& v);
109
110
template<>
111
nmz_float v_make_prime<>(vector<nmz_float>& v);
112
113
//---------------------------------------------------------------------------
114
// Scalar operations
115
//---------------------------------------------------------------------------
116
117
//v = v * scalar
118
template<typename Integer>
119
void v_scalar_multiplication(vector<Integer>& v, const Integer scalar){
120
size_t i,size=v.size();
121
for (i = 0; i <size; i++) {
122
v[i] *= scalar;
123
}
124
}
125
126
//---------------------------------------------------------------------------
127
128
template<typename Integer>
129
void v_scalar_division(vector<Integer>& v, const Integer scalar){
130
size_t i,size=v.size();
131
for (i = 0; i <size; i++) {
132
assert(v[i]%scalar == 0);
133
v[i] /= scalar;
134
}
135
}
136
137
//returns v * scalar mod modulus
138
template<typename Integer>
139
vector<Integer> v_scalar_mult_mod(const vector<Integer>& v, const Integer& scalar, const Integer& modulus, bool& success);
140
141
template<typename Integer>
142
void v_reduction_modulo(vector<Integer>& v, const Integer& modulo);
143
//v = v mod modulo
144
145
//---------------------------------------------------------------------------
146
// Test
147
//---------------------------------------------------------------------------
148
149
template<typename Integer>
150
bool v_test_scalar_product(const vector<Integer>& a,const vector<Integer>& b, const Integer& result, const long& m);
151
// test the main computation for arithmetic overflow
152
// uses multiplication mod m
153
154
//---------------------------------------------------------------------------
155
// General vector operations
156
//---------------------------------------------------------------------------
157
158
//returns a new vector with the content of a extended by b
159
template<typename T>
160
vector<T> v_merge(const vector<T>& a, const T& b);
161
162
//returns a new vector with the content of a and b
163
template<typename T>
164
vector<T> v_merge(const vector<T>& a, const vector<T>& b);
165
166
//returns a new vector with the last size entries of v
167
template<typename T>
168
vector<T> v_cut_front(const vector<T>& v, size_t size);
169
170
//the input vectors must be ordered of equal size
171
//if u is different from v by just one element, it returns that element
172
//else returns 0 (the elements of u and v are >0)
173
//int v_difference_ordered_fast(const vector<size_t>& u,const vector<size_t>& v);
174
175
176
template<typename Integer>
177
bool compare_last (const vector<Integer>& a, const vector<Integer>& b)
178
{
179
return a.back() < b.back();
180
}
181
182
//returns a key vector containing the positions of non-zero entrys of v
183
template<typename Integer>
184
vector<key_t> v_non_zero_pos(const vector<Integer>& v);
185
186
// counts the number of positive entries
187
template<typename Integer>
188
size_t v_nr_positive(const vector<Integer>& v);
189
190
template<typename Integer>
191
size_t v_nr_negative(const vector<Integer>& v);
192
193
template<typename Integer>
194
bool v_non_negative(const vector<Integer>& v);
195
196
// check whether the vector only contains 0
197
template<typename Integer>
198
bool v_is_zero(const vector<Integer>& v);
199
200
template<typename Integer>
201
bool v_is_symmetric(const vector<Integer>& v);
202
203
template<typename Integer>
204
bool v_is_nonnegative(const vector<Integer>& v);
205
206
template<typename Integer>
207
Integer v_max_abs(const vector<Integer>& v){
208
Integer tmp = 0;
209
for (size_t i=0; i<v.size(); i++){
210
if (Iabs(v[i])>tmp) tmp=Iabs(v[i]);
211
}
212
return tmp;
213
}
214
215
//---------------------------------------------------------------------------
216
// bool vector operations
217
//---------------------------------------------------------------------------
218
219
vector<bool> v_bool_andnot(const vector<bool>& a, const vector<bool>& b);
220
221
// swaps entry i and j of the vector<bool> v
222
void v_bool_entry_swap(vector<bool>& v, size_t i, size_t j);
223
224
//---------------------------------------------------------------------------
225
// Special
226
//---------------------------------------------------------------------------
227
228
// computes integral simplex containing a rational vector
229
template<typename Integer>
230
void approx_simplex(const vector<Integer>& q, std::list<vector<Integer> >& approx,const long k);
231
232
vector<key_t> identity_key(size_t n);
233
234
// compute the degree vector of a hsop
235
template<typename Integer>
236
vector<Integer> degrees_hsop(const vector<Integer> gen_degrees,const vector<size_t> heights);
237
238
//---------------------------------------------------------------------------
239
// Sorting
240
//---------------------------------------------------------------------------
241
242
template <typename T>
243
void order_by_perm(vector<T>& v, const vector<key_t>& permfix);
244
245
// compare sizes of v_scalar_product_unequal_vectors_begin
246
247
248
} // namespace
249
250
//---------------------------------------------------------------------------
251
#endif
252
//---------------------------------------------------------------------------
253
254