Understanding Transitive Closure and Boolean Matrix Multiplication
Learn about transitive closure in directed graphs and how it can be computed using Boolean matrix multiplication. Explore the concept of reachability through adjacency matrices and discover the significance of matrix operations in graph theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Transitive Closure Let ? = (?,?) be a directed (unweighted) graph. The transitive closure ? = (?,? ) is the graph in which (?,?) ? iff there is a path from ? to ? in ?. Can be easily computed in ?(??) time. 1
Boolean Matrix Multiplication j = = = = = = = C c ( ) A a ( ) B b ( ) i ij ij ij Can be computed naively in ?(?3) time. 2
Recall: The adjacency matrix 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 ? ? ? ? = ? 3
The meaning of ?? ? 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 ? ? ? ? 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 = 4
The adjacency matrix and reachability Exercise: If ? is the adjacency matrix of a graph, then ?? ??= 1 iff there is a path (not necessarily simple) of length ? from ? to ?. 5
The meaning of ? ?? 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 ? ? ? ? ? = ? 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 = 6
The adjacency matrix and reachability Exercise: If ? is the adjacency matrix of a graph, then ?? ??= 1 iff there is a path (not necessarily simple) of length ? from ? to ?. Exercise: If ? is the adjacency matrix of a graph, then (A I)? ??= 1 iff there is a path (not necessarily simple) of length ? from ? to ?. 7
Transitive Closure using Boolean matrix multiplication Compute (A I)n 1 How much time does it take ? 8
Multiplying nn matrices recursively ?11 ?21 ?12 ?22 ?11 ?21 ?12 ?22 =?11 ?21 ?12 ?22 8 matrix multiplications 4 matrix additions ? 2 + ??2 ? ? = 8 ? ?(?) = ?(??? 8) = ?(?3) 9
Strassens algorithm = = = = + + + + = = = = = = = + + + C C C C A B A B A B A B A B A B A B A B ( ( A B A )( ) B B B ) M M M M M M M A A A A B B B 11 Subtraction! 11 11 11 12 21 1 22 11 22 12 11 12 12 22 2 21 ( 22 11 ) ) 21 21 11 22 21 3 11 12 22 ( B + 22 21 12 22 22 4 22 A A A 21 A A A 11 ( ( ( ) )( )( 5 11 12 22 B B = = = + + + + C C C C M M M M M M M M M M + ) B B 11 1 4 5 7 6 21 11 11 12 + ) 12 3 5 7 12 22 21 22 21 2 4 7 multiplications 18 additions/subtractions = + + M M 22 1 2 3 6 Works over any ring! 11
Strassens algorithm ? 2 + ??2 ?(?) = 7 ? ?(?) = ?(??? 7) = ?(?2.81) 12
Matrix multiplication algorithms Complexity n3 n2.81 Authors Strassen (1969) n2.38 Coppersmith-Winograd (1990) Conjecture/Open problem:n2+o(1) ??? 13
Matrix multiplication algorithms - Recent developments Complexity n2.376 n2.374 n2.3729 n2.37287 Authors Coppersmith-Winograd (1990) Stothers (2010) Williams (2011) Le Gall (2014) Conjecture/Open problem:n2+o(1) ??? 14
Multiplying Boolean matrices Well, and is not a ring ( is not a group) But, we can multiply over the integers (any non-zero in the result is in fact a 1) Can compute transitive closure is ? ??log? time by repeated squaring of ? ?
