Threaded Implementation of the Berkowitz’s Algorithm [Python]

Purpose

To implement the Berkowitz’s Algorithm for computing the characteristic polynomial of an N x N binary matrix through the use of multithreaded processing in Python. The process must have a step complexity of log^2(n). More on this algorithm can be found here.

The results are available on Github.

Tools

Software used:

  • Python 2.7.1
  • Python Multithreading Library (threading)
  • Other Python Libraries Used:
  • Random
  • Math
  • System
  • Time
  • Queue

Implementation

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 log^2(n) sequentially many steps. The program was then rigorously tested to ensure its accuracy.

The Python threading library was used to accomplish the log^2(n) step complexity requirement. Even though the threaded implementation takes significantly longer to run than the single thread implementation, the purpose of this project was to show methods in which threaded peers can operate to complete this task in less steps.

Results

Our results were successful. We were able to construct, compute, and test a 50×50 matrix in approximately 2 minutes. Our results were checked by a separate function to ensure accuracy. A single thread or multicore implementation would likely run faster, but the result here is enough to conclude that the algorithm is efficient, and the step complexity does in fact meet the log^2(n) requirement (which would not be met by a single thread solution).

Documentation

This project is available on Github, here.