-
Notifications
You must be signed in to change notification settings - Fork 1
Improve the Cpp implementation of rounding method in volesti library
Rounding a convex polytope is crucial to improve the mixing rate of several MCMC methods that sample uniformly from the polytope. A standard method to round a convex polytope is to bring it to John position. This can be achieved by computing the largest inscribed ellipsoid of the polytope (or the John ellipsoid) and apply to it the transformation that maps the ellipsoid to the unit ball. The final polytope would be in John position. There are several software packages that round polytopes by computing the John ellipsoid. The best implementations lie in PolyRound and in Cobra Matlab library. The first is a pure Python implementation of [1] and the second a pure Matlab implementation of [1]. This project will improve the C++ implementation of [1] in volesti library; the goal is to develop a C++ implementation as fast as PolyRound's implementation.
The volesti C++ library computes the John ellipsoid by implementing in C++ (using Eigen library) the optimization method in [1]. However, this implementation is orders of magnitude slower than PolyRound or Cobra as it lacks vectorized and optimized computations.
The contributor will have to discuss with the mentors and find together the parts of the code that can be improved and/or optimized. Then, she/he will develop a new C++ implementation of [1]. The contributor will also compare her/his implementation against PolyRound and will write an experimental report with her/his findings.
This project is marked as medium (175 hours). However, the mentors are open to discuss with the contributors how it can be extended to a large project (350 hours).
Difficulty: Medium
Medium (175 hours)
- Required: C++, Linear Algebra, Convex optimization theory
- Preferred: Experience with statistical or other mathematical software is a plus
The project will be a very useful addition to package volesti as it will crucially contribute to the implementation of efficient Rounding of convex polytopes.
-
Apostolos Chalkis <tolis.chal at gmail.com> is a Research Engineer at Quantagonia GmbH. He is an expert in statistical software, computational geometry, and optimization, and has previous GSoC student experience (2018 & 2019) and mentoring experience with GeomScale (from 2020 to 2023).
-
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-2017) and the R-project (2017).
Students, please contact the mentors after completing at least one of the tests below.
Students, please do one or more of the following tests before contacting the mentors above.
- Easy: Compile and run volesti library. Run the rounding routines.
- Medium: Compare the C++ implementation of [1] in volesti with PolyRound. The contribute could use the Python interface in dingo to access the volesti's implementation.
- Hard: Find at least two parts in the C++ implementation in volesti that can be improved/optimized and write in your report how are you going to do it.
For tips and references contact the Mentors!
[1] Yin Zhang, Liyan Gao, On Numerical Solution of the Maximum Volume Ellipsoid Problem, 2003.
Students, please post a link to your test results here.
- EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.