CODEWITHSUNDEEP
haskellmatrixlinear-algebragalois-field
Rob
Rob

Reputation: 5286

Algorithm to calculate rref in GF(2)?

I have a matrix :: [[Int]] whose elements are all either zero or one.

How can I efficiently implement rref in GF(2)?

If LU decomposition can be used to calculate rref(matrix) in GF(2), any example or elaboration on the algorithm would be greatly appreciated.

Upvotes: 2

Views: 1047

Answers (1)

Changaco
Changaco

Reputation: 790

  1. I don't think it's possible to make an efficient GF(2) implementation using hmatrix, it was designed to handle "big" numbers, not bits.

  2. You definitely don't want to use a Double to encode a Bit, that's 64 times more memory than what you actually need.

  3. Have you searched for rref algorithms that are optimized for GF(2) ? A generic Gaussian elimination or LU decomposition might not be the best solution in GF(2).

Upvotes: 3

Related Questions