Sparse optimizations for UniformABW sampling

[lucaperju]

optimized the complexity of the reflection when the A matrix is sparse

Sampled 1000 points from the same order polytope with the same seed using both sparse and dense abw, here are the last 2 points: Dense: 0.947133 0.13444 0.417853 0.499325 0.995814 0.775422 0.728527 0.715522 0.0377974 0.428896 0.708553 0.119995 0.224509 0.549352 0.919391 0.649939 0.648627 0.55607 0.0863634 0.500581

Sparse: 0.947133 0.13444 0.417853 0.499325 0.995814 0.775422 0.728527 0.715522 0.0377974 0.428896 0.708553 0.119995 0.224509 0.549352 0.919391 0.649939 0.648627 0.55607 0.0863634 0.500581

points_sparse.txt points_dense.txt

[TolisChal]

Hi @lucaperju! This is a really high quality PR! Thanks a lot!

1. I left a few comments on your changes.
2. Could you please copy paste in the description of this PR the results of an example that shows that the new implementation gives the same result with the previous one? For example, fix the seed and sample 1000 points from a 10-th dimensional order polytope with the current implementation and this new implementation. Print the last 10 points sampled from each polytope to the description of this PR. Also attach the txt files that contain the samples and add a script (in any programming language) that does an epsilon equality check for all points. Does this make sense?

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 75.23810% with 26 lines in your changes missing coverage. Please review.

Project coverage is 57.32%. Comparing base (d424f3e) to head (fe5641d).

Files	Patch %	Lines
...random_walks/uniform_accelerated_billiard_walk.hpp	74.69%	4 Missing and 17 partials :warning:
include/convex_bodies/hpolytope.h	77.27%	0 Missing and 5 partials :warning:

Additional details and impacted files

[](https://app.codecov.io/gh/GeomScale/volesti/pull/329?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=GeomScale) ```diff @@ Coverage Diff @@ ## develop #329 +/- ## =========================================== + Coverage 56.95% 57.32% +0.37% =========================================== Files 114 114 Lines 7155 7241 +86 Branches 3215 3236 +21 =========================================== + Hits 4075 4151 +76 + Misses 978 976 -2 - Partials 2102 2114 +12 ``` | [Files](https://app.codecov.io/gh/GeomScale/volesti/pull/329?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=GeomScale) | Coverage Δ | | |---|---|---| | [include/preprocess/rounding\_util\_functions.hpp](https://app.codecov.io/gh/GeomScale/volesti/pull/329?src=pr&el=tree&filepath=include%2Fpreprocess%2Frounding_util_functions.hpp&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=GeomScale#diff-aW5jbHVkZS9wcmVwcm9jZXNzL3JvdW5kaW5nX3V0aWxfZnVuY3Rpb25zLmhwcA==) | `58.62% <ø> (ø)` | | | [...andom\_walks/gaussian\_accelerated\_billiard\_walk.hpp](https://app.codecov.io/gh/GeomScale/volesti/pull/329?src=pr&el=tree&filepath=include%2Frandom_walks%2Fgaussian_accelerated_billiard_walk.hpp&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=GeomScale#diff-aW5jbHVkZS9yYW5kb21fd2Fsa3MvZ2F1c3NpYW5fYWNjZWxlcmF0ZWRfYmlsbGlhcmRfd2Fsay5ocHA=) | `61.47% <ø> (ø)` | | | [include/convex\_bodies/hpolytope.h](https://app.codecov.io/gh/GeomScale/volesti/pull/329?src=pr&el=tree&filepath=include%2Fconvex_bodies%2Fhpolytope.h&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=GeomScale#diff-aW5jbHVkZS9jb252ZXhfYm9kaWVzL2hwb2x5dG9wZS5o) | `76.64% <77.27%> (+1.24%)` | :arrow_up: | | [...random\_walks/uniform\_accelerated\_billiard\_walk.hpp](https://app.codecov.io/gh/GeomScale/volesti/pull/329?src=pr&el=tree&filepath=include%2Frandom_walks%2Funiform_accelerated_billiard_walk.hpp&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=GeomScale#diff-aW5jbHVkZS9yYW5kb21fd2Fsa3MvdW5pZm9ybV9hY2NlbGVyYXRlZF9iaWxsaWFyZF93YWxrLmhwcA==) | `64.84% <74.69%> (+8.84%)` | :arrow_up: | ... and [2 files with indirect coverage changes](https://app.codecov.io/gh/GeomScale/volesti/pull/329/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=GeomScale)