Volume 133, Number 6, March 2021
|Number of page(s)||7|
|Published online||13 May 2021|
How we are leading a 3-XORSAT challenge: From the energy landscape to the algorithm and its efficient implementation on GPUs(a)
1 Institute of Applied Computing, CNR - I-00185 Rome, Italy
2 NVIDIA Corporation - Santa Clara, CA 95050, USA
3 Dipartimento di Fisica, Sapienza Università di Roma - I-00185 Rome, Italy
4 INFN, Sezione di Roma 1 - I-00185 Rome, Italy
5 CNR-Nanotec, Rome unit - I-00185 Rome, Italy
6 Departamento de Física Teórica, Universidad Complutense - E-28040 Madrid, Spain
7 Instituto de Biocomputación y Física de Sistemas Complejos (BIFI) - E-50018 Zaragoza, Spain
Received: 31 December 2020
Accepted: 22 February 2021
A recent 3-XORSAT challenge required to minimize a very complex and rough energy function, typical of glassy models with a random first-order transition and a golf-course–like energy landscape. We present the ideas beyond the quasi-greedy algorithm and its very efficient implementation on GPUs that are allowing us to rank first in such a competition. We suggest a better protocol to compare algorithmic performances and we also provide analytical predictions about the exponential growth of the times to find the solution in terms of free-energy barriers.
PACS: 02.70.-c – Computational techniques; simulations / 02.60.Pn – Numerical optimization / 64.60.My – Metastable phases
© 2021 EPLA
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.