Python: уменьшенная форма эшелона строки (mod p) очень большой матрицы

Question

Я хочу найти уменьшенную эшелонную строку (в поле F_q) большой матрицы. Я пробовал следующий код. Хотя я использовал библиотеку gmpy2 для ускорения работы, программа по-прежнему была не в памяти. потому что моя входная матрица очень велика (100 x 2^15), а p также очень велика (| p | = 256 бит). Может кто-то предложить, как уменьшить сложность этого alg.

Спасибо

def invmodp(a, p): 
    return gmpy2.invert(a,p) 

def division_mod(a, b, p): #a/b mod p 
    invert = invmodp(b, p) 
    return (a * invert) %p 

def row_echelon_form(M, p): 
    lead = 0 
    rowCount = len(M) 
    columnCount = len(M[0]) 
    for r in range(rowCount): 
     if lead >= columnCount: 
      return 
     i = r 
     while M[i][lead] == 0: 
      i += 1 
      if i == rowCount: 
       i = r 
       lead += 1 
       if columnCount == lead: 
        return 
    M[i],M[r] = M[r],M[i] 
    lv = M[r][lead] 
    M[r] = [ division_mod(mrx, lv, p) for mrx in M[r]] 
    for i in range(rowCount): 
     if i != r: 
      lv = M[i][lead] 
      M[i] = [ (iv - lv*rv)%p for rv,iv in zip(M[r],M[i])] 
    lead += 1 
return M 

Answer 1

мне удалось сэкономить несколько секунд эфирного времени с помощью gmpy2.divm заменить division_mod. Я не смог сделать никаких других существенных улучшений. Следующая программа создает случайную матрицу размером 100 x 2^15 и вычисляет форму эшелона строк примерно за 3 минуты и потребляет 425 МБ памяти.

import gmpy2 

bits = 256 
r = 100 
c = 2**15 

p = gmpy2.next_prime(2**bits - 1234) 
seed = gmpy2.random_state(42) 

M = [] 
for i in range(r): 
    M.append([gmpy2.mpz_urandomb(seed, bits) for j in range(c)]) 

def row_echelon_form(M, p): 
    lead = 0 
    rowCount = len(M) 
    columnCount = len(M[0]) 
    for r in range(rowCount): 
     if lead >= columnCount: 
      return 
     i = r 
     while M[i][lead] == 0: 
      i += 1 
      if i == rowCount: 
       i = r 
       lead += 1 
       if columnCount == lead: 
        return 

     M[i],M[r] = M[r],M[i] 
     lv = M[r][lead] 
     M[r] = [ gmpy2.divm(mrx, lv, p) for mrx in M[r]] 
     for i in range(rowCount): 
      if i != r: 
       lv = M[i][lead] 
       M[i] = [ (iv - lv*rv) % p for rv,iv in zip(M[r],M[i])] 
     lead += 1 
    return M 

N = row_echelon_form(M, p) 

Если использование памяти перерастает около 500 МБ, может быть утечка памяти в версии gmpy2. Или я неправильно интерпретировал ваши требования, и матрица значительно больше.

Отказ от ответственности: Я поддерживаю gmpy2.