Блог пользователя harsh-apcr

Автор harsh-apcr, история, 12 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится +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.