Participants Info

Name Yao Sun
Institute SKLOIS, Institute of Information Engineering, CAS

Submission Details

Date 2020/05/07
Type I
Number of variables (n) 74
Number of equations (m) 148
Seed (0,1,2,3,4) 2
Algorithm Improved Parallel Crossbred
Hardware Intel i7 8700, GeForce GTX 1080Ti
Running Time 82.44 hours
Answer v=[v1,…,vn] in Fn [0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0]
Notes 8 computers with Intel i7 8700 and 32 GB RAM are used to eliminate Macaulay matrices. The maximal runtime is 455.11 CPU-hours (for a single thread), and it is done by 32 threads in 14.22 hours. 10 GeForce GTX 1080Ti cards are used for brute force searches. The maximal runtime is 2275.56 GPU-hours (for a single card), which can be finished in 9.5 days by 10 cards. We are lucky to find the solution in 68.22 hours. We improve the CPU computation by using techniques of computing Grobner basis. We also improve the GPU computation (based on the codes from MQsolver, https://github.com/kcning/mqsolver) in theory, and obtain about 20% improvements (which is not from the usage of new hardwares). Theoretically, the co mplexity of our improved Parallel Crossbred algorithm is only half of the original algorithm given by Kai-Chun Ning and Ruben Niederhagen.