Competition for solving an integer system of linear equations
Hello, Habradrug.
I propose to take part in the competition to solve the integer SLN for speed. I just want to warn you that the amateur competition and prizes are not expected, therefore they invite those who find such a competition interesting and to those who have free time for this. Competition can be useful from the point of view that very few people can solve this kind of problem quite effectively.
')
I continue to hold amateur contests on sports programming. Many liked the last competition and I even promised that the next one will be by parallel calculations, but for technical reasons I have to postpone such competition indefinitely.
A year ago, I proposed the task of multiplying matrices with speed. The results were quite interesting: we have achieved more than 100-fold acceleration. Now another problem of linear algebra is proposed — solving an integral system of linear equations Ax = b.
Matrix A and vector b consist of integers that fit into 32 bits with a sign (from -2 31 to 2 31 -1). The answer to this problem is a rational vector x. Since the numerator and denominator of the answer can be very long, it is not forbidden to use libraries with long arithmetic.
The maximum dimension of the system is proposed n = 200. But if one of the participants writes a too fast program, this restriction will be increased. The fact is that the usual Gauss method in integers, written "in the forehead," with such restrictions on the random matrix works for about 10 minutes. Of course, you can write faster.
Anyone interested, please read the details of the competition .
Unfortunately, I continue to hold competitions alone, so there are serious restrictions for participants. I have the opportunity to test programs only under Windows 7 (32 bits), so you can either send EXE files or CPP source files that will be compiled on a working machine (in this case only the MPIR library is available). I have no other way to hold a contest. However, a similar restriction for the competition to multiply the participants' matrices did not stop.
A good result of the competition, I see an implementation that fits in 5-10 seconds.
In the process of searching for information about the exact solution of integral systems, I discovered that very few people can solve this problem. I myself am not an expert in this field, but in my research I came across integer SLNs that need to be resolved very quickly. This contest can help to understand how much progress can be achieved in solving the integer systems and what we can expect in this case. The winner of the competition could share his experience by writing a separate article, which would be very useful for people working in the field of computational linear algebra. It was not possible to find such articles in the Runet, therefore it is proposed to fill this gap.
If it turns out (after the end of the competition) that my methods are faster than the methods of the participants, then I will write such an article myself. Until the end of the competition, I do not interfere in it.
Of course, I am not looking for purely personal gain for myself and I am not going to steal someone else's code and use it for my own purposes. This is not the first time I've been holding a contest, and so far no one seems to have complained. Therefore, complexors on this occasion may not complex:)
Good luck!
I propose to take part in the competition to solve the integer SLN for speed. I just want to warn you that the amateur competition and prizes are not expected, therefore they invite those who find such a competition interesting and to those who have free time for this. Competition can be useful from the point of view that very few people can solve this kind of problem quite effectively.
')
I continue to hold amateur contests on sports programming. Many liked the last competition and I even promised that the next one will be by parallel calculations, but for technical reasons I have to postpone such competition indefinitely.
A year ago, I proposed the task of multiplying matrices with speed. The results were quite interesting: we have achieved more than 100-fold acceleration. Now another problem of linear algebra is proposed — solving an integral system of linear equations Ax = b.
Matrix A and vector b consist of integers that fit into 32 bits with a sign (from -2 31 to 2 31 -1). The answer to this problem is a rational vector x. Since the numerator and denominator of the answer can be very long, it is not forbidden to use libraries with long arithmetic.
The maximum dimension of the system is proposed n = 200. But if one of the participants writes a too fast program, this restriction will be increased. The fact is that the usual Gauss method in integers, written "in the forehead," with such restrictions on the random matrix works for about 10 minutes. Of course, you can write faster.
Anyone interested, please read the details of the competition .
Unfortunately, I continue to hold competitions alone, so there are serious restrictions for participants. I have the opportunity to test programs only under Windows 7 (32 bits), so you can either send EXE files or CPP source files that will be compiled on a working machine (in this case only the MPIR library is available). I have no other way to hold a contest. However, a similar restriction for the competition to multiply the participants' matrices did not stop.
A good result of the competition, I see an implementation that fits in 5-10 seconds.
Why do you need it?
In the process of searching for information about the exact solution of integral systems, I discovered that very few people can solve this problem. I myself am not an expert in this field, but in my research I came across integer SLNs that need to be resolved very quickly. This contest can help to understand how much progress can be achieved in solving the integer systems and what we can expect in this case. The winner of the competition could share his experience by writing a separate article, which would be very useful for people working in the field of computational linear algebra. It was not possible to find such articles in the Runet, therefore it is proposed to fill this gap.
If it turns out (after the end of the competition) that my methods are faster than the methods of the participants, then I will write such an article myself. Until the end of the competition, I do not interfere in it.
Of course, I am not looking for purely personal gain for myself and I am not going to steal someone else's code and use it for my own purposes. This is not the first time I've been holding a contest, and so far no one seems to have complained. Therefore, complexors on this occasion may not complex:)
Good luck!
Source: https://habr.com/ru/post/112939/
All Articles