From 991d4e17c873d64d2ad3c262dbcdaea59157ed50 Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Fri, 1 Sep 2017 13:41:59 +0200 Subject: clarified code setting coefficient for column addition --- ripser.cpp | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/ripser.cpp b/ripser.cpp index fceba33..49a1840 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -550,10 +550,13 @@ public: #endif index_t j = i; + + diameter_entry_t pivot; - // start with a dummy pivot entry with coefficient -1 in order to initialize + + // start with coefficient 1 in order to initialize // working_coboundary with the coboundary of the simplex with index column_to_reduce - diameter_entry_t pivot(0, -1, -1 + modulus); + coefficient_t factor = 1; #ifdef ASSEMBLE_REDUCTION_MATRIX // initialize reduction_coefficients as identity matrix @@ -566,7 +569,6 @@ public: bool might_be_apparent_pair = (i == j); do { - const coefficient_t factor = modulus - get_coefficient(pivot); #ifdef ASSEMBLE_REDUCTION_MATRIX #ifdef USE_COEFFICIENTS @@ -624,6 +626,7 @@ public: if (pair != pivot_column_index.end()) { j = pair->second; + factor = modulus - get_coefficient(pivot); continue; } } else { -- cgit v1.2.3 From eb10fdad464f3346663fa0ca6cde9aabd7cdbc14 Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Fri, 1 Sep 2017 18:07:38 +0200 Subject: renamed some variables --- ripser.cpp | 74 +++++++++++++++++++++++++++++++------------------------------- 1 file changed, 37 insertions(+), 37 deletions(-) diff --git a/ripser.cpp b/ripser.cpp index 49a1840..ec5d288 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -518,22 +518,22 @@ public: #endif #ifdef ASSEMBLE_REDUCTION_MATRIX - compressed_sparse_matrix reduction_coefficients; + compressed_sparse_matrix reduction_matrix; #else #ifdef USE_COEFFICIENTS - std::vector reduction_coefficients; + std::vector reduction_matrix; #endif #endif std::vector coface_entries; - for (index_t i = 0; i < columns_to_reduce.size(); ++i) { - auto column_to_reduce = columns_to_reduce[i]; + for (index_t index_column_to_reduce = 0; index_column_to_reduce < columns_to_reduce.size(); ++index_column_to_reduce) { + auto column_to_reduce = columns_to_reduce[index_column_to_reduce]; #ifdef ASSEMBLE_REDUCTION_MATRIX std::priority_queue, greater_diameter_or_smaller_index> - reduction_column; + working_reduction_column; #endif std::priority_queue, @@ -543,60 +543,60 @@ public: value_t diameter = get_diameter(column_to_reduce); #ifdef INDICATE_PROGRESS - if ((i + 1) % 1000000 == 0) + if ((index_column_to_reduce + 1) % 1000000 == 0) std::cout << "\033[K" - << "reducing column " << i + 1 << "/" << columns_to_reduce.size() + << "reducing column " << index_column_to_reduce + 1 << "/" << columns_to_reduce.size() << " (diameter " << diameter << ")" << std::flush << "\r"; #endif - index_t j = i; + index_t index_column_to_add = index_column_to_reduce; diameter_entry_t pivot; - // start with coefficient 1 in order to initialize - // working_coboundary with the coboundary of the simplex with index column_to_reduce - coefficient_t factor = 1; + // start with factor 1 in order to initialize working_coboundary + // with the coboundary of the simplex with index column_to_reduce + coefficient_t factor_column_to_add = 1; #ifdef ASSEMBLE_REDUCTION_MATRIX - // initialize reduction_coefficients as identity matrix - reduction_coefficients.append_column(); + // initialize reduction_matrix as identity matrix + reduction_matrix.append_column(); #endif #ifdef USE_COEFFICIENTS - reduction_coefficients.push_back(diameter_entry_t(column_to_reduce, 1)); + reduction_matrix.push_back(diameter_entry_t(column_to_reduce, 1)); #endif - bool might_be_apparent_pair = (i == j); + bool might_be_apparent_pair = (index_column_to_reduce == index_column_to_add); do { #ifdef ASSEMBLE_REDUCTION_MATRIX #ifdef USE_COEFFICIENTS - auto coeffs_begin = reduction_coefficients.cbegin(j), - coeffs_end = reduction_coefficients.cend(j); + auto reduction_column_begin = reduction_matrix.cbegin(index_column_to_add), + reduction_column_end = reduction_matrix.cend(index_column_to_add); #else std::vector coeffs; - coeffs.push_back(columns_to_reduce[j]); - for (auto it = reduction_coefficients.cbegin(j); - it != reduction_coefficients.cend(j); ++it) + coeffs.push_back(columns_to_reduce[index_column_to_add]); + for (auto it = reduction_matrix.cbegin(index_column_to_add); + it != reduction_matrix.cend(index_column_to_add); ++it) coeffs.push_back(*it); - auto coeffs_begin = coeffs.begin(), coeffs_end = coeffs.end(); + auto reduction_column_begin = coeffs.begin(), reduction_column_end = coeffs.end(); #endif #else #ifdef USE_COEFFICIENTS - auto coeffs_begin = &reduction_coefficients[j], - coeffs_end = &reduction_coefficients[j] + 1; + auto reduction_column_begin = &reduction_matrix[index_column_to_add], + reduction_column_end = &reduction_matrix[index_column_to_add] + 1; #else - auto coeffs_begin = &columns_to_reduce[j], coeffs_end = &columns_to_reduce[j] + 1; + auto reduction_column_begin = &columns_to_reduce[index_column_to_add], reduction_column_end = &columns_to_reduce[index_column_to_add] + 1; #endif #endif - for (auto it = coeffs_begin; it != coeffs_end; ++it) { + for (auto it = reduction_column_begin; it != reduction_column_end; ++it) { diameter_entry_t simplex = *it; - set_coefficient(simplex, get_coefficient(simplex) * factor % modulus); + set_coefficient(simplex, get_coefficient(simplex) * factor_column_to_add % modulus); #ifdef ASSEMBLE_REDUCTION_MATRIX - reduction_column.push(simplex); + working_reduction_column.push(simplex); #endif coface_entries.clear(); @@ -625,8 +625,8 @@ public: auto pair = pivot_column_index.find(get_index(pivot)); if (pair != pivot_column_index.end()) { - j = pair->second; - factor = modulus - get_coefficient(pivot); + index_column_to_add = pair->second; + factor_column_to_add = modulus - get_coefficient(pivot); continue; } } else { @@ -650,34 +650,34 @@ public: } #endif - pivot_column_index.insert(std::make_pair(get_index(pivot), i)); + pivot_column_index.insert(std::make_pair(get_index(pivot), index_column_to_reduce)); #ifdef USE_COEFFICIENTS const coefficient_t inverse = multiplicative_inverse[get_coefficient(pivot)]; #endif #ifdef ASSEMBLE_REDUCTION_MATRIX -// replace current column of reduction_coefficients (with a single diagonal 1 entry) +// replace current column of reduction_matrix (with a single diagonal 1 entry) // by reduction_column (possibly with a different entry on the diagonal) #ifdef USE_COEFFICIENTS - reduction_coefficients.pop_back(); + reduction_matrix.pop_back(); #else - pop_pivot(reduction_column, modulus); + pop_pivot(working_reduction_column, modulus); #endif while (true) { - diameter_entry_t e = pop_pivot(reduction_column, modulus); + diameter_entry_t e = pop_pivot(working_reduction_column, modulus); if (get_index(e) == -1) break; #ifdef USE_COEFFICIENTS set_coefficient(e, inverse * get_coefficient(e) % modulus); assert(get_coefficient(e) > 0); #endif - reduction_coefficients.push_back(e); + reduction_matrix.push_back(e); } #else #ifdef USE_COEFFICIENTS - reduction_coefficients.pop_back(); - reduction_coefficients.push_back(diameter_entry_t(column_to_reduce, inverse)); + reduction_matrix.pop_back(); + reduction_matrix.push_back(diameter_entry_t(column_to_reduce, inverse)); #endif #endif break; -- cgit v1.2.3 From fa4391b17f9aa2e2cedbf8ce855be2a55b7d5b60 Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Wed, 13 Sep 2017 16:51:33 +0200 Subject: add Eirene benchmark --- benchmarks/sphere_3_192/eirene.dim_1.out.txt | 173 +++++++++++++++++++++++++++ benchmarks/sphere_3_192/eirene.dim_2.out.txt | 173 +++++++++++++++++++++++++++ benchmarks/sphere_3_192/run_eirene.sh | 7 ++ 3 files changed, 353 insertions(+) create mode 100644 benchmarks/sphere_3_192/eirene.dim_1.out.txt create mode 100644 benchmarks/sphere_3_192/eirene.dim_2.out.txt create mode 100644 benchmarks/sphere_3_192/run_eirene.sh diff --git a/benchmarks/sphere_3_192/eirene.dim_1.out.txt b/benchmarks/sphere_3_192/eirene.dim_1.out.txt new file mode 100644 index 0000000..3f205e1 --- /dev/null +++ b/benchmarks/sphere_3_192/eirene.dim_1.out.txt @@ -0,0 +1,173 @@ + + +Eirene Library for Homological Algebra +Copyright (C) 2016, 2017 Gregory Henselman +www.gregoryhenselman.org + +Eirene is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +Eirene is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with Eirene. If not, see . + + +WELCOME TO EIRENE! +v0.3.5 + +Please help us document Eirene's recent work! Bibtex entries and +contact information for teaching and outreach can be found at the +Eirene homepage, http://gregoryhenselman.org/eirene. + + +Please Note: MultivariateStats.jl may not be installed. This package is required for +some operations pertaining to multidimensional scaling, but is not required. +To install, enter the following at the Julia prompt: + +Pkg.add("MultivariateStats") +using MultivariateStats + + +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +Constructed Morse boundary operator, columns indexed by cells of dimension 1 +elapsed time: 5.240448941 seconds +Constructed Morse boundary operator, columns indexed by cells of dimension 1 +Constructed Morse boundary operator, columns indexed by cells of dimension 2 +Constructed Morse boundary operator, columns indexed by cells of dimension 3 +elapsed time: 2.614149242 seconds + 22.13 real 21.22 user 1.07 sys + 632369152 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 263754 page reclaims + 0 page faults + 0 swaps + 59 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 5 signals received + 120 voluntary context switches + 165216 involuntary context switches diff --git a/benchmarks/sphere_3_192/eirene.dim_2.out.txt b/benchmarks/sphere_3_192/eirene.dim_2.out.txt new file mode 100644 index 0000000..acfb3db --- /dev/null +++ b/benchmarks/sphere_3_192/eirene.dim_2.out.txt @@ -0,0 +1,173 @@ + + +Eirene Library for Homological Algebra +Copyright (C) 2016, 2017 Gregory Henselman +www.gregoryhenselman.org + +Eirene is free software: you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation, either version 3 of the License, or +(at your option) any later version. + +Eirene is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with Eirene. If not, see . + + +WELCOME TO EIRENE! +v0.3.5 + +Please help us document Eirene's recent work! Bibtex entries and +contact information for teaching and outreach can be found at the +Eirene homepage, http://gregoryhenselman.org/eirene. + + +Please Note: MultivariateStats.jl may not be installed. This package is required for +some operations pertaining to multidimensional scaling, but is not required. +To install, enter the following at the Julia prompt: + +Pkg.add("MultivariateStats") +using MultivariateStats + + +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in __persistF2#19__ at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +WARNING: Base.String is deprecated, use AbstractString instead. + likely near no file:0 +in ezlabel at /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl +Constructed Morse boundary operator, columns indexed by cells of dimension 1 +elapsed time: 5.023364429 seconds +Constructed Morse boundary operator, columns indexed by cells of dimension 1 +Constructed Morse boundary operator, columns indexed by cells of dimension 2 +Constructed Morse boundary operator, columns indexed by cells of dimension 3 +elapsed time: 13.676510239 seconds + 33.14 real 30.90 user 2.37 sys +1508073472 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 810601 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 5 signals received + 46 voluntary context switches + 195015 involuntary context switches diff --git a/benchmarks/sphere_3_192/run_eirene.sh b/benchmarks/sphere_3_192/run_eirene.sh new file mode 100644 index 0000000..4d76795 --- /dev/null +++ b/benchmarks/sphere_3_192/run_eirene.sh @@ -0,0 +1,7 @@ +/usr/bin/time -l julia --load /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl --eval \ +'p = readdlm("/Users/uli/Bitbucket/phat-paper/benchmark/point cloud/sphere_3_192_points.dat"); eirene(p, rowsare="points", bettimax=0); eirene(p, rowsare="points", bettimax=1);' \ +2>&1 | tee eirene.dim_1.out.txt + +/usr/bin/time -l julia --load /Users/uli/Source/Eirene0_3_5/Eirene0_3_5.jl --eval \ +'p = readdlm("/Users/uli/Bitbucket/phat-paper/benchmark/point cloud/sphere_3_192_points.dat"); eirene(p, rowsare="points", bettimax=0); eirene(p, rowsare="points", bettimax=2);' \ +2>&1 | tee eirene.dim_2.out.txt -- cgit v1.2.3 From bebf8d1c30f887de46bc1f6089464fa8e0d80081 Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Fri, 22 Sep 2017 10:50:03 +0200 Subject: removed old value range computation --- ripser.cpp | 2 -- 1 file changed, 2 deletions(-) diff --git a/ripser.cpp b/ripser.cpp index ec5d288..555bde4 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -919,8 +919,6 @@ int main(int argc, char** argv) { std::cout << "distance matrix with " << dist.size() << " points" << std::endl; - auto value_range = std::minmax_element(dist.distances.begin(), dist.distances.end()); - value_t min = std::numeric_limits::infinity(), max = -std::numeric_limits::infinity(); for (auto d: dist.distances) { -- cgit v1.2.3 From a1db43fc46443e1010c81bb04d161907ea852cb2 Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Wed, 25 Oct 2017 23:01:54 +0200 Subject: code cleanup --- ripser.cpp | 17 +++-------------- 1 file changed, 3 insertions(+), 14 deletions(-) diff --git a/ripser.cpp b/ripser.cpp index 555bde4..6bd725e 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -128,19 +128,14 @@ void set_coefficient(entry_t& e, const coefficient_t c) {} const entry_t& get_entry(const entry_t& e) { return e; } -class diameter_index_t : public std::pair { -public: - diameter_index_t() : std::pair() {} - diameter_index_t(std::pair&& p) : std::pair(std::move(p)) {} -}; +typedef std::pair diameter_index_t; value_t get_diameter(const diameter_index_t& i) { return i.first; } index_t get_index(const diameter_index_t& i) { return i.second; } class diameter_entry_t : public std::pair { public: - diameter_entry_t(std::pair p) : std::pair(p) {} - diameter_entry_t(entry_t&& e) : std::pair(0, std::move(e)) {} - diameter_entry_t() : diameter_entry_t(entry_t()) {} + diameter_entry_t() {} + diameter_entry_t(const entry_t& e) : std::pair(0, e) {} diameter_entry_t(value_t _diameter, index_t _index, coefficient_t _coefficient) : std::pair(_diameter, make_entry(_index, _coefficient)) {} diameter_entry_t(const diameter_index_t& _diameter_index, coefficient_t _coefficient) @@ -366,12 +361,6 @@ public: } }; -template -void push_entry(Heap& column, index_t i, coefficient_t c, value_t diameter) { - entry_t e = make_entry(i, c); - column.push(std::make_pair(diameter, e)); -} - class ripser { compressed_lower_distance_matrix dist; index_t dim_max, n; -- cgit v1.2.3 From 9eae733cca3ac379ca447d5abb7289cc37bbeafc Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Thu, 26 Oct 2017 00:25:46 +0200 Subject: extracted add_coboundary_and_get_pivot method --- ripser.cpp | 116 +++++++++++++++++++++++++++++++++++-------------------------- 1 file changed, 66 insertions(+), 50 deletions(-) diff --git a/ripser.cpp b/ripser.cpp index 6bd725e..9085ec2 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -141,7 +141,8 @@ public: diameter_entry_t(const diameter_index_t& _diameter_index, coefficient_t _coefficient) : std::pair(get_diameter(_diameter_index), make_entry(get_index(_diameter_index), _coefficient)) {} - diameter_entry_t(const diameter_index_t& _diameter_index) : diameter_entry_t(_diameter_index, 1) {} + diameter_entry_t(const diameter_index_t& _diameter_index) + : diameter_entry_t(_diameter_index, 1) {} }; const entry_t& get_entry(const diameter_entry_t& p) { return p.second; } @@ -226,10 +227,8 @@ public: euclidean_distance_matrix(std::vector>&& _points) : points(std::move(_points)) { - for (auto p: points) { - assert(p.size() == points.front().size()); - } - } + for (auto p : points) { assert(p.size() == points.front().size()); } + } value_t operator()(const index_t i, const index_t j) const { assert(i < points.size()); @@ -369,6 +368,7 @@ class ripser { const binomial_coeff_table binomial_coeff; std::vector multiplicative_inverse; mutable std::vector vertices; + mutable std::vector coface_entries; public: ripser(compressed_lower_distance_matrix&& _dist, index_t _dim_max, value_t _threshold, @@ -499,6 +499,44 @@ public: #endif } + template + diameter_entry_t add_coboundary_and_get_pivot(Iterator column_begin, Iterator column_end, + coefficient_t factor_column_to_add, +#ifdef ASSEMBLE_REDUCTION_MATRIX + Column& working_reduction_column, +#endif + Column& working_coboundary, const index_t& dim, + hash_map& pivot_column_index, + bool& might_be_apparent_pair) { + for (auto it = column_begin; it != column_end; ++it) { + diameter_entry_t simplex = *it; + set_coefficient(simplex, get_coefficient(simplex) * factor_column_to_add % modulus); + +#ifdef ASSEMBLE_REDUCTION_MATRIX + working_reduction_column.push(simplex); +#endif + + coface_entries.clear(); + simplex_coboundary_enumerator cofaces(simplex, dim, *this); + while (cofaces.has_next()) { + diameter_entry_t coface = cofaces.next(); + if (get_diameter(coface) <= threshold) { + coface_entries.push_back(coface); + if (might_be_apparent_pair && (get_diameter(simplex) == get_diameter(coface))) { + if (pivot_column_index.find(get_index(coface)) == + pivot_column_index.end()) { + return coface; + } + might_be_apparent_pair = false; + } + } + } + for (auto coface : coface_entries) working_coboundary.push(coface); + } + + return get_pivot(working_coboundary, modulus); + } + void compute_pairs(std::vector& columns_to_reduce, hash_map& pivot_column_index, index_t dim) { @@ -516,7 +554,8 @@ public: std::vector coface_entries; - for (index_t index_column_to_reduce = 0; index_column_to_reduce < columns_to_reduce.size(); ++index_column_to_reduce) { + for (index_t index_column_to_reduce = 0; index_column_to_reduce < columns_to_reduce.size(); + ++index_column_to_reduce) { auto column_to_reduce = columns_to_reduce[index_column_to_reduce]; #ifdef ASSEMBLE_REDUCTION_MATRIX @@ -534,14 +573,14 @@ public: #ifdef INDICATE_PROGRESS if ((index_column_to_reduce + 1) % 1000000 == 0) std::cout << "\033[K" - << "reducing column " << index_column_to_reduce + 1 << "/" << columns_to_reduce.size() - << " (diameter " << diameter << ")" << std::flush << "\r"; + << "reducing column " << index_column_to_reduce + 1 << "/" + << columns_to_reduce.size() << " (diameter " << diameter << ")" + << std::flush << "\r"; #endif index_t index_column_to_add = index_column_to_reduce; - - diameter_entry_t pivot; + diameter_entry_t pivot; // start with factor 1 in order to initialize working_coboundary // with the coboundary of the simplex with index column_to_reduce @@ -557,8 +596,7 @@ public: bool might_be_apparent_pair = (index_column_to_reduce == index_column_to_add); - do { - + while (true) { #ifdef ASSEMBLE_REDUCTION_MATRIX #ifdef USE_COEFFICIENTS auto reduction_column_begin = reduction_matrix.cbegin(index_column_to_add), @@ -576,39 +614,18 @@ public: auto reduction_column_begin = &reduction_matrix[index_column_to_add], reduction_column_end = &reduction_matrix[index_column_to_add] + 1; #else - auto reduction_column_begin = &columns_to_reduce[index_column_to_add], reduction_column_end = &columns_to_reduce[index_column_to_add] + 1; + auto reduction_column_begin = &columns_to_reduce[index_column_to_add], + reduction_column_end = &columns_to_reduce[index_column_to_add] + 1; #endif #endif - for (auto it = reduction_column_begin; it != reduction_column_end; ++it) { - diameter_entry_t simplex = *it; - set_coefficient(simplex, get_coefficient(simplex) * factor_column_to_add % modulus); - + pivot = add_coboundary_and_get_pivot(reduction_column_begin, reduction_column_end, + factor_column_to_add, #ifdef ASSEMBLE_REDUCTION_MATRIX - working_reduction_column.push(simplex); -#endif - - coface_entries.clear(); - simplex_coboundary_enumerator cofaces(simplex, dim, *this); - while (cofaces.has_next()) { - diameter_entry_t coface = cofaces.next(); - if (get_diameter(coface) <= threshold) { - coface_entries.push_back(coface); - if (might_be_apparent_pair && - (get_diameter(simplex) == get_diameter(coface))) { - if (pivot_column_index.find(get_index(coface)) == - pivot_column_index.end()) { - pivot = coface; - goto found_persistence_pair; - } - might_be_apparent_pair = false; - } - } - } - for (auto coface : coface_entries) working_coboundary.push(coface); - } - - pivot = get_pivot(working_coboundary, modulus); + working_reduction_column, +#endif + working_coboundary, dim, pivot_column_index, + might_be_apparent_pair); if (get_index(pivot) != -1) { auto pair = pivot_column_index.find(get_index(pivot)); @@ -628,7 +645,6 @@ public: break; } - found_persistence_pair: #ifdef PRINT_PERSISTENCE_PAIRS value_t death = get_diameter(pivot); if (diameter != death) { @@ -670,7 +686,7 @@ public: #endif #endif break; - } while (true); + } } #ifdef INDICATE_PROGRESS @@ -908,19 +924,19 @@ int main(int argc, char** argv) { std::cout << "distance matrix with " << dist.size() << " points" << std::endl; - value_t min = std::numeric_limits::infinity(), max = -std::numeric_limits::infinity(); - - for (auto d: dist.distances) { - if (d != std::numeric_limits::infinity() ) { + value_t min = std::numeric_limits::infinity(), + max = -std::numeric_limits::infinity(); + + for (auto d : dist.distances) { + if (d != std::numeric_limits::infinity()) { min = std::min(min, d); max = std::max(max, d); } else { threshold = std::min(threshold, std::numeric_limits::max()); } } - - std::cout << "value range: [" << min << "," << max << "]" - << std::endl; + + std::cout << "value range: [" << min << "," << max << "]" << std::endl; ripser(std::move(dist), dim_max, threshold, modulus).compute_barcodes(); } -- cgit v1.2.3 From 0ed8c7932825572e49fa5abd50f2338cb66d7fd0 Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Wed, 24 Jan 2018 15:16:34 +0100 Subject: simplified control flow --- ripser.cpp | 76 ++++++++++++++++++++++++++++++-------------------------------- 1 file changed, 37 insertions(+), 39 deletions(-) diff --git a/ripser.cpp b/ripser.cpp index 9085ec2..bc97752 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -619,13 +619,12 @@ public: #endif #endif - pivot = add_coboundary_and_get_pivot(reduction_column_begin, reduction_column_end, - factor_column_to_add, + pivot = add_coboundary_and_get_pivot( + reduction_column_begin, reduction_column_end, factor_column_to_add, #ifdef ASSEMBLE_REDUCTION_MATRIX - working_reduction_column, + working_reduction_column, #endif - working_coboundary, dim, pivot_column_index, - might_be_apparent_pair); + working_coboundary, dim, pivot_column_index, might_be_apparent_pair); if (get_index(pivot) != -1) { auto pair = pivot_column_index.find(get_index(pivot)); @@ -633,59 +632,58 @@ public: if (pair != pivot_column_index.end()) { index_column_to_add = pair->second; factor_column_to_add = modulus - get_coefficient(pivot); - continue; - } - } else { + } else { #ifdef PRINT_PERSISTENCE_PAIRS + value_t death = get_diameter(pivot); + if (diameter != death) { #ifdef INDICATE_PROGRESS - std::cout << "\033[K"; -#endif - std::cout << " [" << diameter << ", )" << std::endl << std::flush; + std::cout << "\033[K"; #endif - break; - } - -#ifdef PRINT_PERSISTENCE_PAIRS - value_t death = get_diameter(pivot); - if (diameter != death) { -#ifdef INDICATE_PROGRESS - std::cout << "\033[K"; -#endif - std::cout << " [" << diameter << "," << death << ")" << std::endl << std::flush; - } + std::cout << " [" << diameter << "," << death << ")" << std::endl + << std::flush; + } #endif - - pivot_column_index.insert(std::make_pair(get_index(pivot), index_column_to_reduce)); + pivot_column_index.insert( + std::make_pair(get_index(pivot), index_column_to_reduce)); #ifdef USE_COEFFICIENTS - const coefficient_t inverse = multiplicative_inverse[get_coefficient(pivot)]; + const coefficient_t inverse = + multiplicative_inverse[get_coefficient(pivot)]; #endif #ifdef ASSEMBLE_REDUCTION_MATRIX -// replace current column of reduction_matrix (with a single diagonal 1 entry) -// by reduction_column (possibly with a different entry on the diagonal) + // replace current column of reduction_matrix (with a single diagonal 1 + // entry) by reduction_column (possibly with a different entry on the + // diagonal) #ifdef USE_COEFFICIENTS - reduction_matrix.pop_back(); + reduction_matrix.pop_back(); #else - pop_pivot(working_reduction_column, modulus); + pop_pivot(working_reduction_column, modulus); #endif - while (true) { - diameter_entry_t e = pop_pivot(working_reduction_column, modulus); - if (get_index(e) == -1) break; + while (true) { + diameter_entry_t e = pop_pivot(working_reduction_column, modulus); + if (get_index(e) == -1) break; #ifdef USE_COEFFICIENTS - set_coefficient(e, inverse * get_coefficient(e) % modulus); - assert(get_coefficient(e) > 0); + set_coefficient(e, inverse * get_coefficient(e) % modulus); + assert(get_coefficient(e) > 0); #endif - reduction_matrix.push_back(e); - } + reduction_matrix.push_back(e); + } #else #ifdef USE_COEFFICIENTS - reduction_matrix.pop_back(); - reduction_matrix.push_back(diameter_entry_t(column_to_reduce, inverse)); + reduction_matrix.pop_back(); + reduction_matrix.push_back(diameter_entry_t(column_to_reduce, inverse)); #endif #endif - break; + break; + } + } else { +#ifdef PRINT_PERSISTENCE_PAIRS + std::cout << " [" << diameter << ", )" << std::endl << std::flush; +#endif + break; + } } } -- cgit v1.2.3