-synx-'s blog

By -synx-, history, 8 years ago, In English

e-maxx
This link mentions that we can speed up conventional Gaussian elimination by using bitset
to achieve O(n3 / 32) using bitwise operations.
I have 3 questions:
1. Do they mean mod 2 inverses (1 + 1 = 0, 0 + 0 = 0, 0 + 1 = 1 + 0 = 1)?
2. For mod 2 inverse to exist, does this imply det(A) mod 2 ≠ 0?
3. Can someone please help correct the following implementation?

vector<bitset<N>>gaussModTwo(vector<bitset<N>>a,vector<bitset<N>>b){
	int n=a.size(), i, j;
	for(i=0;i<n;++i){
		for(j=i;j<n;++j) if(a[j][i]){
			swap(a[j],a[i]);
			swap(b[j],b[i]);
			break;
		}
		for(j=0;j<n;++j) if(j!=i) {
			a[j]^=a[i];
			b[j]^=b[i];
		}
	}
	return b;
}
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?