Yes, if the matrix has <= 64 rows, then you can store the columns as 64-bit integers and perform column operations using bitwise XOR. Also, you can determine the uppermost and lowermost non-zero elements in a column using the __builtin_clzll() instruction and variants thereof. This generalises, of course; with N rows, you can store each column as a vector of ceil(N/64) 64-bit integers and perform column operations with as many instructions. With SIMD, you can actually get away with as few as ceil(N/256) instructions per column operation. The fact that there's only one non-zero element of GF(2) is also helpful since there's no need to multiply the columns -- add/subtract (i.e. XOR) is the only operation you ever need to perform! I'm using exactly this procedure in my PhD research on topological data analysis. In particular, computing the persistent homology barcode from the boundary map is (a slightly modified version of) Gaussian elimination over GF(2). Best wishes, Adam P. Goucher

Sent: Sunday, July 02, 2017 at 6:29 PM From: "Henry Baker" <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Any cool hacks for Gaussian elimination over GF(2) ?

Other than Strassen?

I.e., are there any bit-twiddling hacks that are particular to GF(2) for Gaussian elimination?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun