In factoring methods based on the quadratic sieve, finding the left null space of a binary matrix (values computed mod 2) is a crucial step. (This is also the null space of the transpose.) Does numpy or scipy have tools to do this quickly?
For reference, here is my current code:
# Row-reduce binary matrix
def binary_rr(m):
rows, cols = m.shape
l = 0
for k in range(min(rows, cols)):
print(k)
if l >= cols: break
# Swap with pivot if m[k,l] is 0
if m[k,l] == 0:
found_pivot = False
while not found_pivot:
if l >= cols: break
for i in range(k+1, rows):
if m[i,l]:
m[[i,k]] = m[[k,i]] # Swap rows
found_pivot = True
break
if not found_pivot: l += 1
if l >= cols: break # No more rows
# For rows below pivot, subtract row
for i in range(k+1, rows):
if m[i,l]: m[i] ^= m[k]
l += 1
return m
It is pretty much a straightforward implementation of Gaussian elimination, but since it's written in python it is very slow.
from Finding null space of binary matrix in python
No comments:
Post a Comment