### harsh-apcr's blog

By harsh-apcr, history, 3 months ago,

How fast can we do gaussian elimination over $\mathbb{Z}/2\mathbb{Z}$ ?

I know the usual time complexity of gaussian elimination over reals is $O(n^3)$ which is horrible, but can we do very fast over $\mathbb{Z}/2\mathbb{Z}$ ?

Any references would be nice if there are such techniques, I searched the internet but couldn't find my answer

• 0

 » 3 months ago, # |   +10 Basically, there are no special techniques for gaussian elimination in $\mathbb{Z}/2\mathbb{Z}$, but the speedup from $O(n^3)$ to $O(\frac{n^3}{w})$ is quite easy ($w$ is the size of machine word, which is $32$ or $64$, depending on the compiler.The most "expensive" operation in ordinary gaussian elimination is, basically, summation of two rows: we do $n$ iterations and do $O(n)$ summations per one iteration, each summation takes $O(n)$ time, which leads to $O(n^3)$ complexity.The key fact that addition of binary vectors can be done in $O(\frac{n}{w})$ using std::bitset (a += b is just a ^= b), and one can easily achieve $O(\frac{n^3}{w})$ complexity by just doing all operations with bitsets instead of arrays/vectors.