Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Learn the fundamental concepts of matrix multiplication from both arithmetic and communication complexity perspectives in this 56-minute lecture from UC Berkeley's Olga Holtz at the Simons Institute. Begin with the classical cubic-time algorithm and explore the motivation behind studying arithmetic complexity for bilinear problems. Discover Strassen's revolutionary fast algorithm that reduces 2×2 block matrix multiplication from 8 to 7 recursive operations, achieving O(n^log₂7) ≈ O(n^2.81) complexity and introducing the matrix multiplication exponent ω. Understand why determining ω remains a central open problem driving algorithmic innovation in linear algebra. Explore how matrix multiplication serves as a unifying framework for solving related problems including matrix inversion, determinant computation, rank determination, and linear system solving through classical complexity reductions. Examine communication complexity considerations in both sequential models (focusing on data movement between fast and slow memory) and parallel models (where processors exchange partial results). Analyze known lower bounds demonstrating that matrix multiplication is inherently communication-intensive and requires optimization of data movement alongside arithmetic operations for asymptotically optimal performance.
