Improved matrix multiplication algorithm Repeated squaring: A2k=Ak A' Compute A.A O(g n) squarings Note:An-1=An=An+1=… Time=o(nlgn To detect negative-weight cycles, check the diagonal for negative values in O(n) additional time c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.8© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.8 Improved matrix multiplication algorithm Repeated squaring: A2k = Ak × Ak. Compute A2, A4, …, A2lg(n–1) . O(lg n) squarings Time = Θ(n3 lg n). To detect negative-weight cycles, check the diagonal for negative values in O(n) additional time. Note: An–1 = An = An+1 = L