Models of Computation - Introduction to Computational Complexity in Linear Algebra

Explore foundational models of computation and complexity measurement in this introductory lecture from the Complexity and Linear Algebra Boot Camp at the Simons Institute. Begin with arithmetic models including exact arithmetic over real or integer rings and practical floating-point arithmetic, leading naturally into numerical error analysis through forward and backward error bounds as complementary approaches to quantifying stability. Progress to complexity models, starting with arithmetic complexity that counts operations in idealized exact-arithmetic environments, then advancing to bit complexity which accounts for number representation sizes. Examine communication complexity in both sequential settings where data moves between memory hierarchy levels and parallel environments where multiple processors exchange information. Discover how computational cost depends as much on information movement as on arithmetic operations themselves, gaining essential preparation for understanding the intersection of complexity theory and linear algebra in advanced research contexts.