Re: Solving large-scale sparse binary linear systems EXACTLY?

Don't ask a numerical analysis newgroup if you need
an exact rational solution.

Of course I quite understand that at first glance, asking a numerical analysis group for an exact solution is a bit odd. But on the other hand, the people here are the ones with the real expertise in solving linear systems, and I'm sure they know the existing software packages and their pros and cons inside and out. If anyone can direct me, I think they would be reading here!

You might try Maple.

Of course that it is the first choice, and my initial application prototype is written in Maple. But unfortuneatly, I am now dealing that matrices that are 1/2 million by 1/2 million (give or take a couple of 100 thousand rows/colums here and there), and Maple (although I love it!) is just too slow.

My matrices are EXTREMELY sparse, and as I mentioned earlier, they are underdetermined and only consist of 1s, -1s and 0s. I only need one solution, and I can just set all the free variables to 0 and take whatever bubbles up. I'm sure that someone somewhere has already done this... maybe I could modify an algorithm in an existing library? Or implement an algorithm written up in some obscure paper?

Advice from the experts would be appreciated. :)

Best,
Susan

PS> I have taken your advice, and posted elsewhere too. Thank you for your comments!
.