линейное вычисление на очень большой матрицы

Question

Мы должны вычислить всю линейную комбинацию (двоичные числа по модулю 2) на строки матрицы

[C1|C2|C3|C4|C5|C6|C7] 
R1: [1 |0 | 0| 0| 0| 0|1 ] 
R2: [1 |0 | 0| 0| 0| 0|1 ] 
R3: [1 |0 | 0| 0| 0| 0|1 ] 
R4: [1 |0 | 0| 0| 0| 0|1 ] 

1) R 1, R 2, R 3, R 4

2) R1 + R2, R1 + R3, R1 + R4, R2 + R3, R2 + R4, R3 + R4

3) R1 + R2 + R3, R1 + R2 + R4, R1 + R3 + R4

4) R1 + R2 + R3 + R4

я) ...

Я использовал биномиальное дерево, но это очень медленно, потому что матрица огромен (около ~ 50000 * 50000)

bool Util::binomialTree(int start, int end, int depth, 
     int *tab_index, vector<YNumber*> resultatY, int size_factor, mpz_t n){ 
    int i; 
    // tab_index contains all the index of the 
    // matrix and depth contains the index numbers in tab_index 
    // computation here 
    for (i = start + 1; i < end; i++){ 
      if (binomialTree (i, end, depth + 1,tab_index, 
         resultatY, size_factor, n)){ 
       return true; 
      } 
    } 
    return false; 
} 

Вы можете предложить эффективный алгоритм?

Answer 1

Я думаю о дереве префикса, в котором символы являются координатами в матрице. когда вы добавляете в дерево, добавьте значение следующей координаты к значению узла-отца. таким образом, вам нужно будет только один раз (R1 + R2 + R3) (R1 + R2 + R3 + R4) и (R1 + R2 + R3 + R4 + R5).

Я надеюсь, что это понятно ...

Уход объяснить, почему вы выбрали биномиальное дерево?