Strassen's Matrix Multiplication

Duration: 27 min

This video lesson is available to enrolled students.

Return to /learn/NTA-UGC-NET-PAPER-2/unit-7-data-structures-and-algorithms/advanced-algorithms/algebraic-computation/asset-strassens-matrix-multiplication after enrolling

Inside: a video lesson and guided study material.

Module outline

  1. Course Overview: About the Course
  2. Paper - 1 | Unit - 1 | Teaching Aptitude: Concept and Objectives of Teaching / शिक्षण की अवधारणा एवं उद्देश्य, Levels of Teaching / शिक्षण के स्तर, Learner's Characteristics / शिक्षार्थी की विशेषताएँ, Learning: Nature and Theories / अधिगम: प्रकृति एवं सिद्धांत, Cognition, Memory and Metacognition / संज्ञान, स्मृति एवं अधिसंज्ञान, Factors Affecting Teaching / शिक्षण को प्रभावित करने वाले कारक, Effective Teaching and the Teacher / प्रभावी शिक्षण एवं शिक्षक, Instructional Objectives and Lesson Planning / अनुदेशनात्मक उद्देश्य एवं पाठ नियोजन, Methods of Teaching / शिक्षण विधियाँ, Offline and Online Teaching Methods / ऑफ़लाइन एवं ऑनलाइन शिक्षण विधियाँ, Teaching Support System / शिक्षण सहायक प्रणाली, Evaluation Systems / मूल्यांकन प्रणाली, Sāṃkhya / सांख्य, Individual Behaviour / व्यक्तिगत व्यवहार, Human Resource Management / मानव संसाधन प्रबंधन, Domains of Child Development / बाल्यावस्था में विकास के क्षेत्र, Biological Basis of Emotion / संवेग का जैविक आधार, Upanishads and Bhagavad Gita / उपनिषद और भगवद्गीता, Central and Peripheral Nervous Systems / केन्द्रीय और परिधीय तंत्रिका तंत्र
  3. Paper - 1 | Unit - 2 | Research Aptitude: Research: Meaning, Features and Scientific Method / अनुसंधान: अर्थ, लक्षण व वैज्ञानिक विधि, Research Paradigms and Approaches / अनुसंधान के प्रतिमान एवं उपागम, Types of Research / अनुसंधान के प्रकार, Variables and Measurement / चर एवं मापन, Methods of Research / अनुसंधान की विधियाँ, Steps of Research / अनुसंधान के चरण, Sampling / प्रतिचयन, Tools and Methods of Data Collection / आँकड़ा संग्रह के उपकरण एवं विधियाँ, Data Analysis and Statistics in Research / आँकड़ा विश्लेषण एवं शोध सांख्यिकी, Thesis and Article Writing / शोध-प्रबंध एवं लेख लेखन, Application of ICT in Research / अनुसंधान में ICT का अनुप्रयोग, Research Ethics / शोध नैतिकता
  4. Paper - 1 | Unit - 3 | Comprehension: Literal Comprehension, Vocabulary and Language in Context, Inferential Comprehension, Critical Comprehension, Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Restoration and Eighteenth-Century Drama, Modern British Fiction, William Shakespeare, Mid-Twentieth-Century and Contemporary British Fiction, American Drama
  5. Paper - 1 | Unit - 4 | Communication: Communication: Meaning, Nature and Process / संचार: अर्थ, प्रकृति एवं प्रक्रिया, Types and Levels of Communication / संचार के प्रकार एवं स्तर, Verbal and Non-verbal Communication / मौखिक एवं अमौखिक संचार, Semiotics and Meaning / संकेत विज्ञान एवं अर्थ, Models and Theories of Communication / संचार के मॉडल एवं सिद्धांत, Effective Communication / प्रभावी संचार, Barriers to Communication / संचार की बाधाएँ, Classroom Communication / कक्षा संचार, Mass Media: Types and Evolution / जनसंचार माध्यम: प्रकार एवं विकास, Mass Media and Society / जनसंचार एवं समाज, Digital and New Media / डिजिटल एवं नव माध्यम, Static General Knowledge / स्थैतिक सामान्य ज्ञान, Morphology and Syntax, Public Health Nutrition / जन स्वास्थ्य पोषण, Newtonian Motion and Stability, GK- Current Affairs / GK- समसामयिकी, Indian Economy / भारतीय अर्थव्यवस्था, Art and Architecture / कला और स्थापत्य, India after Independence / स्वतंत्रता के बाद भारत
  6. Paper - 1 | Unit - 5 | Mathematical Reasoning and Aptitude: Number System and Simplification / संख्या पद्धति एवं सरलीकरण, Algebra and Ages / बीजगणित एवं आयु, Percentage / प्रतिशतता, Ratio, Proportion, Partnership and Mixtures / अनुपात, समानुपात, साझेदारी एवं मिश्रण, Averages / औसत, Profit, Loss and Discount / लाभ, हानि एवं बट्टा, Simple and Compound Interest / साधारण एवं चक्रवृद्धि ब्याज, Time and Work / समय एवं कार्य, Speed, Time and Distance / चाल, समय एवं दूरी, Mensuration and Geometry / क्षेत्रमिति एवं ज्यामिति, Series / श्रेणी, Coding-Decoding / कूटलेखन-कूटवाचन, Relationships, Directions and Ranking / संबंध, दिशा एवं क्रम, Arrangements, Puzzles, Clock and Calendar / व्यवस्था, पहेलियाँ, घड़ी एवं कैलेंडर, Mathematical Foundations, Polity / राजव्यवस्था, जीवनी, Deconstruction, Gender and Queer Theory, Modern British and Irish Poetry, Central Force and Scattering, Chemical thermodynamics, Microscopic techniques, Philosophy of the Constitution / संविधान का दर्शन, Waves, Optics and Charged-Particle Motion, Membrane structure and function, Analysis
  7. Paper - 1 | Unit - 6 | Logical Reasoning: Structure of Arguments / युक्ति की संरचना, Terms, Definitions and Uses of Language / पद, परिभाषा एवं भाषा के उपयोग, Categorical Propositions / निरुपाधिक प्रतिज्ञप्तियाँ, Categorical Syllogism / निरुपाधिक न्यायवाक्य, Venn Diagrams / वेन आरेख, Deduction, Induction and Analogy / निगमन, आगमन एवं सादृश्यता, Fallacies / तर्कदोष, Indian Logic: Pramanas / भारतीय तर्कशास्त्र: प्रमाण, Anumana and Vyapti / अनुमान एवं व्याप्ति, Hetvabhasa / हेत्वाभास, Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning), Aristotle / अरस्तू, Western Schools of Philosophy / पाश्चात्य दर्शन की विचारधाराएँ, Kant / कांट, Sadhana Paada, Vaiśeṣika / वैशेषिक
  8. Paper - 1 | Unit - 7 | Data Interpretation: Data and Graphical Representation / आँकड़े एवं आलेखीय निरूपण, Data Interpretation: Tables / आँकड़ा निर्वचन: तालिका
  9. Paper - 1 | Unit - 8 | Information and Communication Technology: Computer Fundamentals and Hardware, Memory, Storage and Data Representation, Computer Software, Office Applications, Multimedia and File Formats, Computer Networks, Internet and World Wide Web, Email and Online Communication, Cyber Security, Digital Ethics, IPR and Society, Cloud and Distributed Computing, Emerging Technologies, ICT in Education and Governance, Cyber Threats and Malware Attacks, Role of Internet and Web Services, Electronic Data Interchange and E-Commerce, Internet Fundamentals, Web Design & Development, Web Publishing & Hosting, Emerging Technologies, Terms & Abbreviations, Society, Law & Ethics, Keyboard Shortcuts, Website, Browser & Services, Protection of Geographical Indications / भौगोलिक संकेतों का संरक्षण
  10. Paper - 1 | Unit - 9 | People Development and Environment: Ecosystems and Biodiversity / पारितंत्र और जैव विविधता, Human and Environment Interaction / मानव और पर्यावरण की अंतःक्रिया, Development and Environment / विकास और पर्यावरण, Natural Resources – Forests, Water and Soil / प्राकृतिक संसाधन: वन, जल और मृदा, Energy Resources / ऊर्जा संसाधन, Air Pollution / वायु प्रदूषण, Water Pollution and Treatment / जल प्रदूषण और उपचार, Noise Pollution / ध्वनि प्रदूषण, Waste Management / अपशिष्ट प्रबंधन, Environmental Health and Toxicology / पर्यावरणीय स्वास्थ्य और विषविज्ञान, Climate Change and Global Environmental Issues / जलवायु परिवर्तन और वैश्विक पर्यावरणीय समस्याएँ, Natural Hazards and Disaster Management / प्राकृतिक प्रकोप और आपदा प्रबंधन, Indian Environmental Laws and Policies / भारतीय पर्यावरण कानून और नीतियाँ, International Environmental Agreements / अंतर्राष्ट्रीय पर्यावरण समझौते, Environment / पर्यावरण, Geography / भूगोल, Factory and Industry Systems / कारखाना और उद्योग व्यवस्थाएँ, Earth Materials, Surface Features and Processes, Communicable Diseases and Immunization / संक्रामक रोग और प्रतिरक्षण
  11. Paper - 1 | Unit - 10 | Higher Education System: Education in Ancient India / प्राचीन भारत में शिक्षा, Ancient Centres of Higher Learning / प्राचीन भारत के उच्च शिक्षा केंद्र, Colonial Education Policies and Commissions / औपनिवेशिक काल की शिक्षा नीतियाँ और आयोग, Colonial Colleges, Universities and Reformers / औपनिवेशिक कॉलेज, विश्वविद्यालय व सुधारक, Education Commissions and Policies after Independence / स्वतंत्र भारत में शिक्षा आयोग और नीतियाँ, National Education Policy 2020 / राष्ट्रीय शिक्षा नीति 2020, Types of Higher Education Institutions / उच्च शिक्षा संस्थानों के प्रकार, Learning Programmes and Academic Credits / अधिगम कार्यक्रम और अकादमिक क्रेडिट, Professional, Technical and Skill-Based Education / व्यावसायिक, तकनीकी और कौशल आधारित शिक्षा, Value Education and Environmental Education / मूल्य शिक्षा और पर्यावरण शिक्षा, Governance, Administration and Financing / शासन, प्रशासन और वित्तपोषण, Regulation, Accreditation and Ranking / उच्च शिक्षा का नियमन, प्रत्यायन और रैंकिंग
  12. Paper 2 | Unit 1 | Discrete Structures and Optimization: Propositional and Predicate Logic, Set Theory, Relations, Functions, Permutation, Combination and Probability / क्रमचय, संचय एवं प्रायिकता, Graph Theory, Group Theory, Digital Systems & Boolean Basics, Boolean Expression, Boolean Minimization, Optimization, Markov Chains
  13. Paper 2 | Unit 2 | Computer System Architecture: Logic Gates & Hardware, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Floating Point Rep, Basics of COA, Register Transfer and Microoperations, Programming the Basic Computer, Instr Formats & Modes, Control Unit Design, Pipelining, Input Output Organisation, Cache Memory Organization, Multiprocessors
  14. Paper 2 | Unit 3 | Programming Languages and Computer Graphics: Language Design, C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums, DMA, Macros, Scoping & File Handling, HTML Basics, XML, JavaScript-Basics, Java, Basics of Computer Graphics, 2-D Geometrical Transforms and Viewing, 3-D Object Representation, Geometric Transformations and Viewing, OOPS with C++, Java Fundamentals, Array, String, IO & References, OOPS with Java
  15. Paper 2 | Unit 4 | Database Management Systems: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, File Organization & Indexing, Relational Algebra, SQL, Relational Calculus, Transaction Management, Concurrency Control, Database Recovery, ORDBMS, Database Security & Authorization, Query Processing & Optimization, Enhanced Data Models, Data Warehousing & Mining, Big Data Systems, NoSQL
  16. Paper 2 | Unit 5 | System Software and Operating System: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, Disc Scheduling, File Management, Windows OS, Linux OS, Security, Distributed Systems, Virtual Machines
  17. Paper 2 | Unit 6 | Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management
  18. Paper 2 | Unit 7 | Data Structures and Algorithms: Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs, Hashing, Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos, Advanced Algorithms
  19. Paper 2 | Unit 8 | Theory of Computation and Compilers: Introduction to TOC, Deterministic FA (DFA), Non-Deterministic FA, Regular Expressions, Grammar, Regular Language Properties, Moore & Mealy Machines, Pushdown Automata & CFG, Turing Machines, Complexity Theory, Intro to Compilers, Lexical Analysis, Grammar & CFG, Syntax Analysis: Top-Down, Syntax Analysis: Bottom-Up, Semantic Analysis & SDT, Intermediate Code Gen, Code Optimization, Run Time Environment
  20. Paper 2 | Unit 9 | Data Communication and Computer Networks: Introduction to CN, Data Communication, DLL: Access Control, DLL: Flow Control, DLL: Error Control, DLL: Framing, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics, Network Security, Cloud Computing, Mobile Computing
  21. Paper 2 | Unit 10 | Artificial Intelligence: Approaches to AI, Search Algorithms, Game Playing, Knowledge Representation, Planning, Multi Agent Systems, Fuzzy Sets, Natural Language Processing, Artificial Neural Networks, Genetic Algorithms
  22. Live Classes: NTA UGC NET 2025 Live Class
  23. Paper 1 | Full Mock Tests:
  24. Paper 2 | Full Mock Tests:
  25. Paper 1 | Previous Year Papers:
  26. Paper 2 | Previous Year Papers:
AI summary & chapters

AI Summary

An AI-generated summary of this video lecture.

This lecture introduces Strassen's Matrix Multiplication algorithm as a Divide and Conquer optimization over the standard cubic-time approach. The instructor begins by establishing the baseline complexity of matrix multiplication, demonstrating how two n x n matrices are multiplied using nested loops resulting in O(n^3) time complexity. The core problem addressed is the computational cost of performing n^2 multiplications for each element in the result matrix. The lecture then transitions to block matrix decomposition, where 4x4 matrices are partitioned into four equal-sized sub-matrices. The instructor derives the standard recurrence relation T(n) = 8T(n/2) + O(n^2), explaining that multiplying two partitioned matrices requires eight recursive multiplications of sub-matrices plus linear-time additions. Strassen's key innovation is presented as reducing these eight multiplications to seven by introducing additional addition and subtraction operations. The instructor details the specific formulas for these seven intermediate products (labeled P through V), which combine sub-matrices in unique ways to allow the final result matrix C to be reconstructed using only seven recursive calls. This reduction changes the recurrence relation to T(n) = 7T(n/2) + O(n^2), yielding a time complexity of O(n^log_2(7)), which is approximately O(n^2.81). The lecture emphasizes the trade-off between increased arithmetic operations (additions/subtractions) and reduced multiplications, which is beneficial for large matrices.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The instructor introduces Strassen's Matrix Multiplication as a Divide and Conquer algorithm designed to improve efficiency over standard methods. He explains the core concept of reducing 8 multiplications to 7 by using additional additions and subtractions. The instructor begins writing on the screen, setting up an example with two 4x4 matrices labeled A and B to demonstrate the working steps. On-screen text explicitly states 'Strassen's Matrix Multiplication' and 'Divide and Conquer algorithm', while the instructor writes out matrix elements a11 through a44 for matrix A and begins labeling B. The teaching cue highlights the efficiency improvement for large matrices by dividing them into submatrices.

  2. 2:00 – 5:00 02:00-05:00

    The instructor defines the matrix multiplication problem where two 4x4 matrices, A and B, are multiplied to produce a resulting matrix C. He writes out the general form of the 4x4 matrices A and B with their respective elements (a_ij and b_ij) and sets up the equation A x B = C. He then begins to write out the standard algorithmic approach for matrix multiplication using nested loops (i=1 to n, j=1 to n) before presumably moving on to the Strassen's algorithm optimization mentioned in the header. The visual content shows the instructor writing matrices A and B, setting up the matrix multiplication equation, and writing standard algorithm loops. Text on screen includes 'A 4x4', 'B 4x4', and loop structures like 'for (i=1 to n)'. The instructor establishes the problem statement by defining input matrices and introducing standard multiplication logic.

  3. 5:00 – 10:00 05:00-10:00

    The instructor explains the standard matrix multiplication algorithm using pseudocode and a visual example. He writes out nested loops to iterate through rows (i), columns (j), and the summation index (k) to compute each element of the resulting matrix C. The complexity O(n^3) is explicitly written next to the loop structure, indicating the cubic time complexity of this approach. The instructor expands the formula for element C11 and shows the recurrence relation C[i][j] = C[i][j] + A[i][k]*B[k][j]. Key visible events include the instructor writing pseudocode for matrix multiplication, displaying nested loops for i, j, and k iterations, and writing the complexity O(n^3). The instructor points to the loop structure and writes out the mathematical expansion for a specific element, highlighting the cubic complexity.

  4. 10:00 – 15:00 10:00-15:00

    The instructor explains the block matrix multiplication method for multiplying two 4x4 matrices, A and B. He demonstrates how to partition the matrices into sub-matrices (A11, A12, B11, etc.) and shows the resulting product matrix C. The visual focus is on deriving the formula for the top-left block of the result, C11, by multiplying and adding corresponding sub-matrices. The instructor writes A = [A11 A12; A21 A22] and B = [B11 B12; B21 B22], then derives C11 = A11B11 + A12B21. He gestures to show the multiplication of sub-matrices and writes out the expansion formula for C11. The instructor points to specific sub-matrices A11 and B11, using hand gestures to indicate the combination of blocks. The text on screen shows the partitioned matrices and the formula C11 = A11B11 + A12B21.

  5. 15:00 – 20:00 15:00-20:00

    The instructor explains the standard matrix multiplication algorithm using block matrices to derive its time complexity. He breaks down 4x4 matrices into sub-matrices (A11, A12, etc.) and shows how the resulting matrix C is computed by multiplying these blocks. The lecture transitions to analyzing the recurrence relation for this standard approach, demonstrating that it results in O(n^3) complexity. The instructor writes the recurrence relation T(n) = 8T(n/2) + O(n^2), concluding the complexity is O(n^3). Key visible events include the instructor pointing to sub-matrices A11, A12 of matrix A, deriving C11 = A11B11 + A12B21, and writing the recurrence relation T(n) = 8T(n/2) + O(n^2). The instructor visualizes matrix partitioning, performs step-by-step block multiplication derivation, and analyzes the recurrence relation.

  6. 20:00 – 25:00 20:00-25:00

    The instructor explains Strassen's algorithm for matrix multiplication, specifically focusing on the reduction of multiplications from 8 to 7. The visual content shows the derivation of the recurrence relation T(n) = 7T(n/2) + O(n^2), leading to a time complexity of O(n^log_2(7)). The instructor writes out the 7 intermediate products (P through V) and the final matrix formation steps. The instructor points to specific terms in the recurrence relation, writes out the 7 products step-by-step, and highlights the reduction from 8 to 7 multiplications. Text on screen includes 'Step 2: Compute 7 Products' and formulas for P, Q, R, S, T, U. The instructor explains that instead of 8 multiplications, Strassen computes only these specific products.

  7. 25:00 – 27:08 25:00-27:08

    The instructor continues detailing the 7 intermediate products required for Strassen's algorithm. The screen shows formulas such as P = (A11 + A22)(B11 + B22), Q = (A21 + A22)B11, R = A11(B12 - B22), S = A22(B21 - B11), T = (A11 + A12)B22, and U = (A21 - A11)(B11 + B12). The instructor likely explains how these products are combined to form the final matrix C, although the specific combination formulas for C11 through C22 are not fully visible in the sampled screenshots. The instructor highlights the reduction from 8 to 7 multiplications and points to specific terms in the recurrence relation. The text on screen explicitly lists the 7 products P through V, emphasizing that Strassen computes only these to achieve O(n^log_2(7)) complexity.

The lecture systematically builds the case for Strassen's algorithm by first establishing the limitations of standard matrix multiplication. The instructor demonstrates that multiplying two n x n matrices using the naive approach requires three nested loops, resulting in a time complexity of O(n^3). This is derived by showing that each element C[i][j] requires n multiplications and additions, leading to a total of n^3 operations. The instructor then introduces the Divide and Conquer strategy, partitioning matrices into four sub-matrices of size n/2 x n/2. In the standard block multiplication approach, computing the four blocks of the result matrix C requires eight recursive multiplications (e.g., C11 = A11B11 + A12B21), leading to the recurrence T(n) = 8T(n/2) + O(n^2). Solving this recurrence using the Master Theorem yields T(n) = O(n^log_2(8)) = O(n^3), confirming no asymptotic improvement over the naive method. Strassen's breakthrough lies in reducing the number of recursive multiplications from 8 to 7. The instructor details seven intermediate products (P through V) that are computed using additions and subtractions of the sub-matrices. For example, P = (A11 + A22)(B11 + B22) and Q = (A21 + A22)B11. These products are then combined linearly to form the blocks of the result matrix C, such as C11 = P + S - T + V. By reducing the multiplicative term in the recurrence to 7, the new relation becomes T(n) = 7T(n/2) + O(n^2). Applying the Master Theorem to this recurrence gives T(n) = O(n^log_2(7)), which is approximately O(n^2.81). This represents a significant asymptotic improvement for large matrices, despite the overhead of additional additions and subtractions. The lecture emphasizes that while Strassen's algorithm is theoretically faster, it may not be practical for small matrices due to the constant factors involved in the extra arithmetic operations. The visual progression from standard loops to block partitioning and finally to Strassen's 7-product scheme illustrates the evolution of algorithmic optimization. The instructor uses concrete examples with 4x4 matrices to make the abstract recurrence relations tangible. By writing out the specific formulas for P, Q, R, S, T, and U, the instructor provides a clear blueprint for implementing Strassen's algorithm. The key takeaway is that reducing the number of multiplications, even at the cost of more additions, can lead to better asymptotic performance. This principle is fundamental in algorithm design and highlights the importance of analyzing both time complexity and constant factors when choosing an algorithm for practical applications.

Loading lesson…