>>1067596
I found the old code. Well, you know if you want a full 46200*46200 array of integers you're probably fucked. The point is, most of the entries in the equation were zero, so it was what you call a "sparse system".
It was actually a set of equalities between two systems, something along the lines of:
y1 + y2 = x1 + 2*x2 + x4
y1 = 5*x1 + x3
y2 = x2
And I was actually looking for a combination of terms such that the left-hand side gives 0.
I ended up storing the linear system as a linked-list of pairs of (non-fixed length) arrays. Representing the right hand side and left-hand side of the equation. Now, since the majority of terms were zero-valued, i used an array of (index,value) type elements, and stored only the non-zero values. Eg:
6*x1 + 2*x2 + 5*x7 = y1 + y2 would be "abstractly", something along the lines of:
3, [(1,6) , (2,2) , (7,5)]
for the left-hand side and something similar for the right hand side. A structure formed from an integer representing the size of the array and an array of (index,value) pairs representing the indices of the non-zero values in the equation. The indices were always sorted. So you see, because I used sparse representation, the size would alter dynamically if I added two equations, because the number of non-zero indices would change.
I kept the list of equations "sorted" so that the equations with the smallest non-zero index on the left-hand side would always appear first. The empty list would be considered to be smallest of all. Then, if the left-hand side was zero we were done, and if it wasn't, I could check if the next equation in line had a greater first non-zero index. If it had a greater index, we could eliminate the first equation, because there was no combination of it that would eliminate its first index. If they had the same index, we added them in linear combination to eliminate it, insert the resulting equation to the list (it would now either be 0 of the left-hand side or have a greater first non-zero index), delete the first equation, and continue on with the algorithm.
That's the algorithm. Now, why modular arithmetic? I actually used arithmetic mod 2147483647, which is one of the largest primes smaller than or equal to max-int. The system had integer coefficients, and I needed an integer solution. The problem with C++ is I kept getting (unnoticed) overflows and they fucked with the result. If you use modular arithmetic you're safe from overflows, but you only get the result mod p. The point is, p was big enough and the coefficients of the result small enough that I could recover the result r from (r times a constant) mod p.
The code itself is not very readable, tough I'll upload if if you want. i learned tough that it makes a ton of difference in memory usage and performance what structures you use. I initially used linked-lists instead of arrays for the equations, but the pointer-arithmetic and memory overhead was not worth it. You're not sorting the members, you're just adding and subtracting them. Linked lists are not worth it in this case.