Posted by Tim Stinchcombe on August 19, 1998 at 18:39:47:
I seek a routine (preferably in C) that finds the FULL solution set (if such exists) to an overdetermined, BINARY, linear system of equations (i.e. I'm working 'mod 2'). The system is small, approx. 95x65, but I have >2^30 of them to solve, so I need something as efficient as possible.
I have performed various web searches, and checked out a number of numerical libraries, such as LAPACK, but of course these all work with reals or complex numbers. I have coded one of the algorithms from Cohen's book 'A course in computational algebraic number theory', which I have 'customised' to work mod 2, but I doubt that this is really that efficient - I'd like something really slick.
If anyone can point me at a source of efficient linear algebra routines that work over fields OTHER than the reals or the complex numbers, or can tell me where to start looking, or has a smart idea for how I might use a numerical one to give me results mod 2, then I would be most grateful. (One obstacle is that I want ALL solutions, i.e. a particular solution and a basis for the kernel of the associated homogeneous system - most numerical routines for overdetermined systems seem to return ONE particular least-squares solution, which is not of much use...)