From 1f307594244dd4c274b64d028823cbcfff302f37 Mon Sep 17 00:00:00 2001 From: Nathan Cassereau <84033440+ncassereau-idris@users.noreply.github.com> Date: Wed, 1 Jun 2022 08:52:47 +0200 Subject: [MRG] numItermax in 64 bits in EMD solver (#380) * Correct test_mm_convergence for cupy * Fix bug where number of iterations is limited to 2^31 * Update RELEASES.md * Replace size_t with long long * Use uint64_t instead of long long --- ot/lp/EMD_wrapper.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'ot/lp/EMD_wrapper.cpp') diff --git a/ot/lp/EMD_wrapper.cpp b/ot/lp/EMD_wrapper.cpp index 2bdc172..457216b 100644 --- a/ot/lp/EMD_wrapper.cpp +++ b/ot/lp/EMD_wrapper.cpp @@ -20,7 +20,7 @@ int EMD_wrap(int n1, int n2, double *X, double *Y, double *D, double *G, - double* alpha, double* beta, double *cost, int maxIter) { + double* alpha, double* beta, double *cost, uint64_t maxIter) { // beware M and C are stored in row major C style!!! using namespace lemon; @@ -122,7 +122,7 @@ int EMD_wrap(int n1, int n2, double *X, double *Y, double *D, double *G, int EMD_wrap_omp(int n1, int n2, double *X, double *Y, double *D, double *G, - double* alpha, double* beta, double *cost, int maxIter, int numThreads) { + double* alpha, double* beta, double *cost, uint64_t maxIter, int numThreads) { // beware M and C are stored in row major C style!!! using namespace lemon_omp; -- cgit v1.2.3 From e547fe30c59be72ae93c9f017786477b2652776f Mon Sep 17 00:00:00 2001 From: Nathan Cassereau <84033440+ncassereau-idris@users.noreply.github.com> Date: Mon, 13 Jun 2022 14:49:55 +0200 Subject: [MRG] Correct pointer overflow in EMD (#381) * avoid overflow on openmp version of emd solver * monothread version updated * Fixed typo in readme * added PR in releases * typo in releases.md * added a precision to releases.md * added a precision to releases.md * correct readme * forgot to cast * lower error --- README.md | 4 ++-- RELEASES.md | 5 ++++- ot/lp/EMD_wrapper.cpp | 36 ++++++++++++++++++------------------ ot/lp/network_simplex_simple_omp.h | 4 ++-- 4 files changed, 26 insertions(+), 23 deletions(-) (limited to 'ot/lp/EMD_wrapper.cpp') diff --git a/README.md b/README.md index 12340d5..7c9475b 100644 --- a/README.md +++ b/README.md @@ -26,8 +26,8 @@ POT provides the following generic OT solvers (links to examples): * Debiased Sinkhorn barycenters [Sinkhorn divergence barycenter](https://pythonot.github.io/auto_examples/barycenters/plot_debiased_barycenter.html) [37] * [Smooth optimal transport solvers](https://pythonot.github.io/auto_examples/plot_OT_1D_smooth.html) (dual and semi-dual) for KL and squared L2 regularizations [17]. * Weak OT solver between empirical distributions [39] -* Non regularized [Wasserstein barycenters [16] ](https://pythonot.github.io/auto_examples/barycenters/plot_barycenter_lp_vs_entropic.html)) with LP solver (only small scale). -* [Gromov-Wasserstein distances](https://pythonot.github.io/auto_examples/gromov/plot_gromov.html) and [GW barycenters](https://pythonot.github.io/auto_examples/gromov/plot_gromov_barycenter.html) (exact [13] and regularized [12]), differentiable using gradients from +* Non regularized [Wasserstein barycenters [16] ](https://pythonot.github.io/auto_examples/barycenters/plot_barycenter_lp_vs_entropic.html) with LP solver (only small scale). +* [Gromov-Wasserstein distances](https://pythonot.github.io/auto_examples/gromov/plot_gromov.html) and [GW barycenters](https://pythonot.github.io/auto_examples/gromov/plot_gromov_barycenter.html) (exact [13] and regularized [12]), differentiable using gradients from Graph Dictionary Learning [38] * [Fused-Gromov-Wasserstein distances solver](https://pythonot.github.io/auto_examples/gromov/plot_fgw.html#sphx-glr-auto-examples-plot-fgw-py) and [FGW barycenters](https://pythonot.github.io/auto_examples/gromov/plot_barycenter_fgw.html) [24] * [Stochastic solver](https://pythonot.github.io/auto_examples/others/plot_stochastic.html) and diff --git a/RELEASES.md b/RELEASES.md index fdaff59..b384617 100644 --- a/RELEASES.md +++ b/RELEASES.md @@ -13,7 +13,10 @@ - Fixed an issue where Sinkhorn solver assumed a symmetric cost matrix (Issue #374, PR #375) - Fixed an issue where hitting iteration limits would be reported to stderr by std::cerr regardless of Python's stderr stream status (PR #377) - Fixed an issue where the metric argument in ot.dist did not allow a callable parameter (Issue #378, PR #379) -- Fixed an issue where the max number of iterations in ot.emd was not allow to go beyond 2^31 (PR #380) +- Fixed an issue where the max number of iterations in ot.emd was not allowed to go beyond 2^31 (PR #380) +- Fixed an issue where pointers would overflow in the EMD solver, returning an +incomplete transport plan above a certain size (slightly above 46k, its square being +roughly 2^31) (PR #381) ## 0.8.2 diff --git a/ot/lp/EMD_wrapper.cpp b/ot/lp/EMD_wrapper.cpp index 457216b..4aa5a6e 100644 --- a/ot/lp/EMD_wrapper.cpp +++ b/ot/lp/EMD_wrapper.cpp @@ -24,7 +24,7 @@ int EMD_wrap(int n1, int n2, double *X, double *Y, double *D, double *G, // beware M and C are stored in row major C style!!! using namespace lemon; - int n, m, cur; + uint64_t n, m, cur; typedef FullBipartiteDigraph Digraph; DIGRAPH_TYPEDEFS(Digraph); @@ -51,15 +51,15 @@ int EMD_wrap(int n1, int n2, double *X, double *Y, double *D, double *G, // Define the graph - std::vector indI(n), indJ(m); + std::vector indI(n), indJ(m); std::vector weights1(n), weights2(m); Digraph di(n, m); - NetworkSimplexSimple net(di, true, n+m, ((int64_t)n)*((int64_t)m), maxIter); + NetworkSimplexSimple net(di, true, (int) (n + m), n * m, maxIter); // Set supply and demand, don't account for 0 values (faster) cur=0; - for (int i=0; i0) { weights1[ cur ] = val; @@ -70,7 +70,7 @@ int EMD_wrap(int n1, int n2, double *X, double *Y, double *D, double *G, // Demand is actually negative supply... cur=0; - for (int i=0; i0) { weights2[ cur ] = -val; @@ -79,12 +79,12 @@ int EMD_wrap(int n1, int n2, double *X, double *Y, double *D, double *G, } - net.supplyMap(&weights1[0], n, &weights2[0], m); + net.supplyMap(&weights1[0], (int) n, &weights2[0], (int) m); // Set the cost of each edge int64_t idarc = 0; - for (int i=0; i indI(n), indJ(m); + std::vector indI(n), indJ(m); std::vector weights1(n), weights2(m); Digraph di(n, m); - NetworkSimplexSimple net(di, true, n+m, ((int64_t)n)*((int64_t)m), maxIter, numThreads); + NetworkSimplexSimple net(di, true, (int) (n + m), n * m, maxIter, numThreads); // Set supply and demand, don't account for 0 values (faster) cur=0; - for (int i=0; i0) { weights1[ cur ] = val; @@ -172,7 +172,7 @@ int EMD_wrap_omp(int n1, int n2, double *X, double *Y, double *D, double *G, // Demand is actually negative supply... cur=0; - for (int i=0; i0) { weights2[ cur ] = -val; @@ -181,12 +181,12 @@ int EMD_wrap_omp(int n1, int n2, double *X, double *Y, double *D, double *G, } - net.supplyMap(&weights1[0], n, &weights2[0], m); + net.supplyMap(&weights1[0], (int) n, &weights2[0], (int) m); // Set the cost of each edge int64_t idarc = 0; - for (int i=0; i::epsilon()*10 -#define _EPSILON 1e-8 +#define EPSILON std::numeric_limits::epsilon() +#define _EPSILON 1e-14 #define MAX_DEBUG_ITER 100000 /// \ingroup min_cost_flow_algs -- cgit v1.2.3