harsh-apcr's blog

By harsh-apcr, history, 3 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.