Matrix Multiplication: Strassen's Algorithm

This lecture covers the concept of matrix multiplication, starting with the naive algorithm and then introducing Strassen's algorithm to improve efficiency. The instructor explains the divide-and-conquer approach, pseudocode, and analysis of Strassen's method. The lecture also discusses the idea behind Strassen's algorithm, its analysis, and its comparison with other matrix multiplication methods. Additionally, the lecture explores the concept of data structures, focusing on heaps, their properties, height calculation, storage methods, and maintaining the heap property using MAX-HEAPIFY. The presentation concludes with a summary of the divide-and-conquer algorithmic paradigm.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (33)

Related concepts (33)

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Matrix multiplication algorithm

Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).

Matrix norm

In mathematics, a matrix norm is a vector norm in a vector space whose elements (vectors) are matrices (of given dimensions). Given a field of either real or complex numbers, let be the K-vector space of matrices with rows and columns and entries in the field . A matrix norm is a norm on . This article will always write such norms with double vertical bars (like so: ).

Computational complexity of matrix multiplication

In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the right amount of time it should take is of major practical relevance. Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires n3 field operations to multiply two n × n matrices over that field (Θ(n3) in big O notation).

Binary heap

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort. A binary heap is defined as a binary tree with two additional constraints: Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

Pseudocode

In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine reading. It typically omits details that are essential for machine understanding of the algorithm, such as variable declarations and language-specific code. The programming language is augmented with natural language description details, where convenient, or with compact mathematical notation.

Matrix Multiplication and Heap Data Structure CS-250: Algorithms I

Covers the divide-and-conquer algorithm for matrix multiplication and introduces the (binary) heap data structure.

Matrix Multiplication: Divide-and-Conquer CS-250: Algorithms I

Explores the Divide-and-Conquer algorithm for matrix multiplication, including Strassen's Method and its significance in optimizing time complexity.

Introduction to R Programming for Genetics & Genomics BIO-373: Genetics and genomics

Introduces a course on Genetics & Genomics, focusing on R programming with interactive exercises.

Matrix-Matrix Multiplication: Algorithms and Applications

Explores theoretical and practical aspects of fast matrix-matrix multiplication algorithms and their significance in computer science.

O-Notation, Local Extrema MATH-101(de): Analysis I (German)

Covers O-Notation, local extrema, and critical points in functions.