Matrix multiplication Compute C=A·B, where C,A, and b are n×n matrices k=1 Time =0(n)using the standard algorithm What if we map“+”imin”and”->“+”? Cimino(aik+ buji Thus.Dm)=Dm-1)×A Identity matrix =I 0 0 c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.6© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.6 Matrix multiplication Compute C = A · B, where C, A, and B are n × n matrices: ∑ = = n k ij aik bkj c 1 . Time = Θ ( n 3) using the standard algorithm. What if we map “ + ” → “min” and “·” → “ +”? cij = min k { aik + bkj }. Thus, D ( m ) = D ( m–1) “ × ” A. Identity matrix = I =           ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0 0 0 = D 0 = ( dij(0) )