kzaky / Threaded-Implementation-of-Berkowitz-s-Algorithm

In this implementation, we are going to implement Berkowitz’s parallel algorithm for comput- ing the characteristic polynomial of a matrix. Berkowitz’s algorithm, is the fastest known parallel algorithm for computing the characteristic polynomial of a matrix. For the sake of simplicity we assume that the matrices are over {0,1}, i.e., the two field elements, where plus is XOR and multiplication is AND. The algorithm was designed such that the process takes no more than log2 n sequentially many steps. The program was then rigorously tested to ensure its accuracy.