harsh-apcr's blog

Gaussian elimination over GF(2)
By harsh-apcr, history, 2 years 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

»
2 years ago, hide # |
 
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.

→ Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi there, I was just working on a problem and stumble on this topic guided by a chat with an AI. The AI actually proposed an algorithm that runs in O($$$n^2$$$ $$$log\ n$$$) and performs gaussian elimination treating the rows as numbers (as I guess you usually do in these kinds of problem) and using a minimum between $$$a_i$$$ and $$$a_i$$$ ^ $$$b$$$ for some linearly independent row b.

I'll leave here the code for the solution. I would like to ask if anybody knows how or why it works.

vector<long long> find_basis(const vector<long long>& nums) {
    vector<long long> basis;
    for (long long num : nums) {
        long long x = num;
        for (long long b : basis) {
            x = min(x, x ^ b);
        }
        if (x > 0) {
            basis.push_back(x);
            sort(basis.begin(), basis.end(), greater<long long>());
        }
    }
    return basis;
}
→ Reply
  • »
    »
    13 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Actually, this algorithm works because the size of the matrix in columns is at most 64 (long long) for my problem. If you want to have a larger number of columns you would use bitsets as another user suggested. It would also be wise to sort the rows at the start to avoid having to sort the basis at each step.

    → Reply
    • »
      »
      »
      13 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      There is no need to sort at all. Many years ago there was a discussion about this in the comments in a blog on cf (I don't remember which blog). The conclusion is that you can just do:

      def find_basis(nums):
  basis = []
  for x in nums:
    for b in basis:
      x = min(x, x ^ b)
    if x:
      basis.append(x)
  return basis

def in_basis(x, basis):
  for b in basis:
    x = min(x, x ^ b)
  return x == 0
      → Reply