Loading...
Searching...
No Matches
Multi_field_operators.h
Go to the documentation of this file.
/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* Author(s): Hannah Schreiber, Clément Maria
*
* Copyright (C) 2022-24 Inria
*
* Modification(s):
* - YYYY/MM Author: Description of the modification
*/
#ifndef MATRIX_FIELD_MULTI_OPERATORS_H_
#define MATRIX_FIELD_MULTI_OPERATORS_H_
#include <utility>
#include <vector>
#include <gmpxx.h>
#include <stdexcept>
namespace Gudhi {
namespace persistence_fields {
class Multi_field_operators
{
public:
using Element = mpz_class;
using Characteristic = Element;
Multi_field_operators() : productOfAllCharacteristics_(0) /* , multiplicativeID_(1) */
{}
Multi_field_operators(int minCharacteristic, int maxCharacteristic)
: productOfAllCharacteristics_(0) //, multiplicativeID_(1)
{
set_characteristic(minCharacteristic, maxCharacteristic);
}
Multi_field_operators(const Multi_field_operators& toCopy)
: primes_(toCopy.primes_),
productOfAllCharacteristics_(toCopy.productOfAllCharacteristics_),
partials_(toCopy.partials_) /* ,
multiplicativeID_(toCopy.multiplicativeID_) */
{}
Multi_field_operators(Multi_field_operators&& toMove) noexcept
: primes_(std::move(toMove.primes_)),
productOfAllCharacteristics_(std::move(toMove.productOfAllCharacteristics_)),
partials_(std::move(toMove.partials_)) /* ,
multiplicativeID_(std::move(toMove.multiplicativeID_)) */
{}
void set_characteristic(int minimum, int maximum) {
if (maximum < 2) throw std::invalid_argument("Characteristic must be strictly positive");
if (minimum > maximum) throw std::invalid_argument("The given interval is not valid.");
if (minimum == maximum && !_is_prime(minimum))
throw std::invalid_argument("The given interval does not contain a prime number.");
unsigned int curr_prime = minimum;
mpz_t tmp_prime;
mpz_init_set_ui(tmp_prime, minimum);
// test if min_prime is prime
int is_prime = mpz_probab_prime_p(tmp_prime, 25); // probabilistic primality test
if (is_prime == 0) { // min_prime is composite
mpz_nextprime(tmp_prime, tmp_prime);
curr_prime = mpz_get_ui(tmp_prime);
}
primes_.clear();
while (curr_prime <= static_cast<unsigned int>(maximum)) {
primes_.push_back(curr_prime);
mpz_nextprime(tmp_prime, tmp_prime);
curr_prime = mpz_get_ui(tmp_prime);
}
mpz_clear(tmp_prime);
if (primes_.empty()) throw std::invalid_argument("The given interval does not contain a prime number.");
productOfAllCharacteristics_ = 1;
for (const unsigned int p : primes_) {
productOfAllCharacteristics_ *= p;
}
partials_.resize(primes_.size());
for (unsigned int i = 0; i < primes_.size(); ++i) {
unsigned int p = primes_[i];
partials_[i] = productOfAllCharacteristics_ / p;
mpz_powm_ui(partials_[i].get_mpz_t(), partials_[i].get_mpz_t(), p - 1, productOfAllCharacteristics_.get_mpz_t());
}
// If I understood the paper well, multiplicativeID_ always equals to 1. But in Clement's code,
// multiplicativeID_ is computed (see commented loop below). TODO: verify with Clement.
// for (unsigned int i = 0; i < partials_.size(); ++i) {
// multiplicativeID_ = (multiplicativeID_ + partials_[i]) % productOfAllCharacteristics_;
// }
}
const Characteristic& get_characteristic() const { return productOfAllCharacteristics_; }
Element get_value(Element e) const {
get_value_inplace(e);
return e;
}
void get_value_inplace(Element& e) const {
if (e >= productOfAllCharacteristics_ || e < -productOfAllCharacteristics_)
mpz_mod(e.get_mpz_t(), e.get_mpz_t(), productOfAllCharacteristics_.get_mpz_t());
if (e < 0) e += productOfAllCharacteristics_;
}
Element add(Element e1, const Element& e2) const {
add_inplace(e1, e2);
return e1;
}
void add_inplace(Element& e1, const Element& e2) const {
e1 += e2;
get_value_inplace(e1);
}
Element subtract(Element e1, const Element& e2) const {
subtract_inplace_front(e1, e2);
return e1;
}
void subtract_inplace_front(Element& e1, const Element& e2) const {
e1 -= e2;
get_value_inplace(e1);
}
void subtract_inplace_back(const Element& e1, Element& e2) const {
mpz_sub(e2.get_mpz_t(), e1.get_mpz_t(), e2.get_mpz_t());
get_value_inplace(e2);
}
Element multiply(Element e1, const Element& e2) const {
multiply_inplace(e1, e2);
return e1;
}
void multiply_inplace(Element& e1, const Element& e2) const {
e1 *= e2;
get_value_inplace(e1);
}
Element multiply_and_add(Element e, const Element& m, const Element& a) const {
multiply_and_add_inplace_front(e, m, a);
return e;
}
void multiply_and_add_inplace_front(Element& e, const Element& m, const Element& a) const {
e *= m;
e += a;
get_value_inplace(e);
}
void multiply_and_add_inplace_back(const Element& e, const Element& m, Element& a) const {
a += e * m;
get_value_inplace(a);
}
Element add_and_multiply(Element e, const Element& a, const Element& m) const {
add_and_multiply_inplace_front(e, a, m);
return e;
}
void add_and_multiply_inplace_front(Element& e, const Element& a, const Element& m) const {
e += a;
e *= m;
get_value_inplace(e);
}
void add_and_multiply_inplace_back(const Element& e, const Element& a, Element& m) const {
m *= e + a;
get_value_inplace(m);
}
bool are_equal(const Element& e1, const Element& e2) const {
if (e1 == e2) return true;
return get_value(e1) == get_value(e2);
}
Element get_inverse(const Element& e) const {
return get_partial_inverse(e, productOfAllCharacteristics_).first;
}
std::pair<Element, Characteristic> get_partial_inverse(
const Element& e, const Characteristic& productOfCharacteristics) const {
Characteristic QR;
mpz_gcd(QR.get_mpz_t(), e.get_mpz_t(), productOfCharacteristics.get_mpz_t()); // QR <- gcd(x,QS)
if (QR == productOfCharacteristics) return {0, get_multiplicative_identity()}; // partial inverse is 0
Characteristic QT = productOfCharacteristics / QR;
Characteristic inv_qt;
mpz_invert(inv_qt.get_mpz_t(), e.get_mpz_t(), QT.get_mpz_t());
std::pair<Element, Characteristic> res(get_partial_multiplicative_identity(QT), QT);
res.first *= inv_qt;
get_value_inplace(res.first);
return res;
}
static const Element& get_additive_identity() { return additiveID_; }
static const Element& get_multiplicative_identity() { return multiplicativeID_; }
Element get_partial_multiplicative_identity(const Characteristic& productOfCharacteristics) const {
if (productOfCharacteristics == 0) {
return get_multiplicative_identity();
}
Element multIdentity(0);
for (unsigned int idx = 0; idx < primes_.size(); ++idx) {
if ((productOfCharacteristics % primes_[idx]) == 0) {
multIdentity += partials_[idx];
}
}
get_value_inplace(multIdentity);
return multIdentity;
}
// static constexpr bool handles_only_z2() { return false; }
Multi_field_operators& operator=(Multi_field_operators other) {
primes_.swap(other.primes_);
productOfAllCharacteristics_ = other.productOfAllCharacteristics_;
partials_.swap(other.partials_);
return *this;
}
friend void swap(Multi_field_operators& f1, Multi_field_operators& f2) {
f1.primes_.swap(f2.primes_);
std::swap(f1.productOfAllCharacteristics_, f2.productOfAllCharacteristics_);
f1.partials_.swap(f2.partials_);
}
private:
std::vector<unsigned int> primes_;
Characteristic productOfAllCharacteristics_;
std::vector<Characteristic> partials_;
inline static const Element multiplicativeID_ = 1;
inline static const Element additiveID_ = 0;
static constexpr bool _is_prime(const int p) {
if (p <= 1) return false;
if (p <= 3) return true;
if (p % 2 == 0 || p % 3 == 0) return false;
for (long i = 5; i * i <= p; i = i + 6)
if (p % i == 0 || p % (i + 2) == 0) return false;
return true;
}
};
} // namespace persistence_fields
} // namespace Gudhi
#endif // MATRIX_FIELD_MULTI_OPERATORS_H_
Gudhi::persistence_fields::Multi_field_operators::add_and_multiply_inplace_back
void add_and_multiply_inplace_back(const Element &e, const Element &a, Element &m) const
Adds the first element to the second one and multiplies the third one with it, that is ((e + a) * m) ...
Definition Multi_field_operators.h:323
Gudhi::persistence_fields::Multi_field_operators::set_characteristic
void set_characteristic(int minimum, int maximum)
Set the characteristics of the field, which are stored in a single value as a product of all of them....
Definition Multi_field_operators.h:86
Gudhi::persistence_fields::Multi_field_operators::get_multiplicative_identity
static const Element & get_multiplicative_identity()
Returns the multiplicative identity of a field.
Definition Multi_field_operators.h:389
Gudhi::persistence_fields::Multi_field_operators::swap
friend void swap(Multi_field_operators &f1, Multi_field_operators &f2)
Swap operator.
Definition Multi_field_operators.h:427
Gudhi::persistence_fields::Multi_field_operators::Multi_field_operators
Multi_field_operators()
Default constructor, sets the product of all characteristics to 0.
Definition Multi_field_operators.h:43
Gudhi::persistence_fields::Multi_field_operators::are_equal
bool are_equal(const Element &e1, const Element &e2) const
Returns true if the two given elements are equal in the field, false otherwise.
Definition Multi_field_operators.h:336
Gudhi::persistence_fields::Multi_field_operators::Characteristic
Element Characteristic
Definition Multi_field_operators.h:38
Gudhi::persistence_fields::Multi_field_operators::multiply_and_add_inplace_front
void multiply_and_add_inplace_front(Element &e, const Element &m, const Element &a) const
Multiplies the first element with the second one and adds the third one, that is (e * m + a) % produc...
Definition Multi_field_operators.h:267
Gudhi::persistence_fields::Multi_field_operators::subtract_inplace_front
void subtract_inplace_front(Element &e1, const Element &e2) const
Stores in the first element the subtraction in the field of the first element by the second element,...
Definition Multi_field_operators.h:205
Gudhi::persistence_fields::Multi_field_operators::get_characteristic
const Characteristic & get_characteristic() const
Returns the current characteristics as the product of all of them.
Definition Multi_field_operators.h:136
Gudhi::persistence_fields::Multi_field_operators::subtract_inplace_back
void subtract_inplace_back(const Element &e1, Element &e2) const
Stores in the second element the subtraction in the field of the first element by the second element,...
Definition Multi_field_operators.h:216
Gudhi::persistence_fields::Multi_field_operators::multiply_and_add_inplace_back
void multiply_and_add_inplace_back(const Element &e, const Element &m, Element &a) const
Multiplies the first element with the second one and adds the third one, that is (e * m + a) % produc...
Definition Multi_field_operators.h:281
Gudhi::persistence_fields::Multi_field_operators::multiply_inplace
void multiply_inplace(Element &e1, const Element &e2) const
Stores in the first element the multiplication of two given elements in the field,...
Definition Multi_field_operators.h:240
Gudhi::persistence_fields::Multi_field_operators::operator=
Multi_field_operators & operator=(Multi_field_operators other)
Assign operator.
Definition Multi_field_operators.h:417
Gudhi::persistence_fields::Multi_field_operators::multiply_and_add
Element multiply_and_add(Element e, const Element &m, const Element &a) const
Multiplies the first element with the second one and adds the third one. Returns the result in the fi...
Definition Multi_field_operators.h:253
Gudhi::persistence_fields::Multi_field_operators::get_value_inplace
void get_value_inplace(Element &e) const
Stores in the given element the value of this element in the field. That is the positive value of the...
Definition Multi_field_operators.h:156
Gudhi::persistence_fields::Multi_field_operators::get_additive_identity
static const Element & get_additive_identity()
Returns the additive identity of a field.
Definition Multi_field_operators.h:383
Gudhi::persistence_fields::Multi_field_operators::Multi_field_operators
Multi_field_operators(const Multi_field_operators &toCopy)
Copy constructor.
Definition Multi_field_operators.h:61
Gudhi::persistence_fields::Multi_field_operators::Element
mpz_class Element
Definition Multi_field_operators.h:37
Gudhi::persistence_fields::Multi_field_operators::get_partial_inverse
std::pair< Element, Characteristic > get_partial_inverse(const Element &e, const Characteristic &productOfCharacteristics) const
Returns the inverse of the given element in the multi-field corresponding to the given sub-product of...
Definition Multi_field_operators.h:359
Gudhi::persistence_fields::Multi_field_operators::subtract
Element subtract(Element e1, const Element &e2) const
Returns the subtraction in the field of the first element by the second element.
Definition Multi_field_operators.h:193
Gudhi::persistence_fields::Multi_field_operators::multiply
Element multiply(Element e1, const Element &e2) const
Returns the multiplication of two elements in the field.
Definition Multi_field_operators.h:228
Gudhi::persistence_fields::Multi_field_operators::add_inplace
void add_inplace(Element &e1, const Element &e2) const
Stores in the first element the sum of two given elements in the field, that is (e1 + e2) % productOf...
Definition Multi_field_operators.h:181
Gudhi::persistence_fields::Multi_field_operators::get_value
Element get_value(Element e) const
Returns the value of an element in the field. That is the positive value of the integer modulo the cu...
Definition Multi_field_operators.h:145
Gudhi::persistence_fields::Multi_field_operators::add_and_multiply_inplace_front
void add_and_multiply_inplace_front(Element &e, const Element &a, const Element &m) const
Adds the first element to the second one and multiplies the third one with it, that is ((e + a) * m) ...
Definition Multi_field_operators.h:309
Gudhi::persistence_fields::Multi_field_operators::get_inverse
Element get_inverse(const Element &e) const
Returns the inverse of the given element in the sense of boissonnat:hal-00922572 with respect to the ...
Definition Multi_field_operators.h:348
Gudhi::persistence_fields::Multi_field_operators::add_and_multiply
Element add_and_multiply(Element e, const Element &a, const Element &m) const
Adds the first element to the second one and multiplies the third one with it. Returns the result in ...
Definition Multi_field_operators.h:295
Gudhi::persistence_fields::Multi_field_operators::Multi_field_operators
Multi_field_operators(int minCharacteristic, int maxCharacteristic)
Constructor setting the characteristics to all prime numbers between the two given integers.
Definition Multi_field_operators.h:51
Gudhi::persistence_fields::Multi_field_operators::add
Element add(Element e1, const Element &e2) const
Returns the sum of two elements in the field.
Definition Multi_field_operators.h:169
Gudhi::persistence_fields::Multi_field_operators::Multi_field_operators
Multi_field_operators(Multi_field_operators &&toMove) noexcept
Move constructor.
Definition Multi_field_operators.h:72
Gudhi::persistence_fields::Multi_field_operators::get_partial_multiplicative_identity
Element get_partial_multiplicative_identity(const Characteristic &productOfCharacteristics) const
Returns the partial multiplicative identity of the multi-field from the given product....
Definition Multi_field_operators.h:398
Gudhi::persistence_fields
Field namespace.
Definition Intro_field_elements_and_operators.h:16
Gudhi
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14