Algorithm for computing transitive closures on DAGs by harnessing machine words?

Question

Let G be DAG with n vertices and m edges given by adjacency matrix. I need to calculate it's closure in form of a matrix as well. We have a computer that each word is b bits. and I need to find an algorithm that calculate the transitive closure in (n^2+nm/b)

I'm not really sure I understand what bits means and how can I use it

Adding the algorithm for finding transitive closure of dag:

TransitiveForDAG (Graph G)
int T[1...n,1...n] ={0,...,0}
List L <- TopologicalSort(G)
For each v in reverse(L)
   T[v,v]<-1
    For each u in Adj[v]
       for j<-1,...,n do
         T[v,j]<-T[v,j] or T[u,j]

Answer 1

You say you don't know what bits mean, so let's start with that.

• Bit is the smallest unit of digital information - a 0 or a 1
• Word is the unit of data processed by a computer at once. Processors don't take and process individual bits, but small chunks of them. Most today's computer architectures use words of 32 or 64 bits.

Now, how to work with words of binary data? In most programming languages, you'll use a numeric data type to store the data. To manipulate them, most languages provide bitwise operators - bitwise or (|) is one needed here.

So, how to make your algorithm faster? Look at the T matrix. It can only have values of 0 or 1 - a single bit is enough to store that information. You're processing fields of the matrix one by one; every time you process the last line of your algorithm, you only use one bit from the v'th row and one from the u'th row.

As said before, the processor has to read a whole word to read and process each of those bits. That's ineffective; mostly you wouldn't care about such a detail, but here it's in a critical place - the last line is in the innermost cycle and will be executed very many times.

Now, how to be more effective? Change the way you store the data - use a type with the length of a word as the data type for your matrix. Store b values from your original matrix in every value of the new one - this is called packing. Because of the way your algorithm works, you'll want to store them by row - the first value in the i-th row will contain first b values from the i-th row of the original matrix.

Apart from that, you only have to change the innermost cycle of the algorithm - the cycle will iterate over the words instead of individual fields and inside you'll process the whole words at once using bitwise or

T[v,j]<-T[v,j] | T[u,j]

The cycle is what generates the time complexity of the algorithm. You've now managed to iterate b-times less, so the complexity becomes (n^2+nm/b)