3 ms·
If you had just stopped at "finding lineearly dependent rows of a sodding enormous matrix modulo 2" I wouldn't have said anything -- but mentioning elementary l
by cperciva 16y ago
If you had just stopped at "finding lineearly dependent rows of a sodding enormous matrix modulo 2" I wouldn't have said anything -- but mentioning elementary linear algebra was potentially misleading, so I figured it was worth adding the details there. :-)
For what it's worth, there is actually some elementary linear algebra done before the heavy guns are brought out: If a prime only occurs in two or three relations, adding one of those relations to the other(s) will decrease n while increasing w by a small enough factor as to make the final Lanczos solve faster. (In rare cases it can be worth eliminating primes which occur in 4 relations or more, but usually not.)