-
Notifications
You must be signed in to change notification settings - Fork 13
Sampling and volume approximation
Volume computation is a fundamental problem in discrete and computational geometry with many applications in statistics, biology and economics.
The R package 'geometry' makes the qhull library (www.qhull.org) available in R. Qhull can compute volumes of convex polytopes but scales only to low dimensions (typically less than 10).
The first implementation that scales to high (i.e. few hundred) dimensions is implemented in the C++ software package VolEsti (https://github.com/vissarion/volume_approximation). The package contains algorithms for volume approximation as well as uniform sampling for polytopes.
The main purpose of the current project is to provide the functionality of sampling and volume apporximation implemented in VolEsti to the R-project. This will be done using the Rcpp package.
The coding project could be divided in the following steps:
-
Understand the code structure and design of VolEsti.
-
Re-evaluate the dependency from some libraries. For example VolEsti depends on Eigen (https://eigen.tuxfamily.org) and CGAL (https://www.cgal.org). For the first there is an Rcpp library while for the second there is no, hence some parts of code should be rewritten to exclude support from CGAL.
-
Itegrate with or use the functionality of other related R packages. For example, packages that implement random walks for convex bodies such as https://cran.r-project.org/web/packages/walkr and packages that solve linear programs such as https://cran.r-project.org/web/packages/lpSolve
-
Implement new features (depending on the student's background and interests): new sampling and volume computation algorithms, support for polytopes given by the set of vertices of the convex hull, support for spectahedra.
-
Writing tests and documentation.
-
Create an Rcpp package.
A lot of users such as practicioners or researchers from a variety of scientific fields raging from biogeography to economics need a high level programming or scripting environment to test volume computation or sampling algorithms.
Students should have a solid background in C++, algorithms and linear algebra. Knowledge of computational geometry, optimization or statistical computing will be a plus.
Students, please contact mentors below after completing at least one of the tests below.
-
Vissarion Fisikopoulos <vissarion.fisikopoulos at gmail.com> is an expert in computational geometry and optimization, and has previous GSOC experience with Boost C++ libraries in 2016-2017.
-
Zafeirakis Zafeirakopoulos is an expert in implementing and benchmarking geometric and algebraic algorithms and has long experience with mathematical software like SageMath and R.
Students, please do one or more of the following tests before contacting the mentors above.
- Easy: use VolEsti to compute the volume of the 10-dimensional hypercube.
- Medium: write a function that samples using the ball walk (see page 3 of https://www.cc.gatech.edu/~vempala/papers/survey.pdf). Modify VolEsti to compute volumes using your function.
- Hard: modify VolEsti to compute volumes of polytopes given by a set of vertices.
Students, please post a link to your test results here.