Volume computation - GeomScale/gsoc24 GitHub Wiki

Problem

The problem of volume computation is fundamental in computational convex geometry and volesti provides to our knowledge the most efficient implementation today [1]. The latter is based on uniform sampling.

In this project the student has to exploit new non_uniform sampling algorithms to implement a new more efficient volume algorithm.

References

[1] Chalkis, Emiris, Fisikopoulos - A practical algorithm for volume estimation based on billiard trajectories and simulated annealing

[2] Cousins, Vempala - A practical volume algorithm

[3] Ari Pakman, Liam Paninski, Exact Hamiltonian Monte Carlo for Truncated Multivariate Gaussians.

Difficulty: Hard

Size

Large (350 hours)

Skills

  • Required: C++, probability theory, linear algebra
  • Preferred: Experience with mathematical software is a plus

Expected impact

The projects will provide GeomScale with a even faster volume computation algorithm that can scale to thousands of dimensions in hours. Volume computation is a special case of integration, a fundamental problem in applied mathematics and has numerous applications.

Mentors

  • Vissarion Fisikopoulos <vissarion.fisikopoulos at gmail.com> is an international expert in mathematical software, computational geometry, and optimization, and has previous GSOC mentoring experience with Boost C++ libraries (2016-2020) and the R-project (2017-2019).

  • Elias Tsigaridas <elias.tsigaridas at inria.fr> is an expert in computational nonlinear algebra and geometry with experience in mathematical software. He has contributed to the implementation, in C and C++, of several solving algorithms for various open source computer algebra libraries and has previous GSOC mentoring experience with the R-project (2019) and Geomscale (2020).

  • Matias Bender holds a Ph.D. in algebraic algorithms and he is an expert in computational algebra.

Tests

  • Easy: Download, compile and run a simple volume estimation example with both C++ and R interfaces of volesti.
  • Medium: Write a volume algorithm that uses Cooling Gaussians method with Hamiltonian MC sampling (both already implemented in volesti).
  • Hard: Write in your proposal methods to improve the complexity of the sampling step used in the Medium test.