Lecture

Matrix Chain Multiplication: Optimal Substructure and Recursive Formula

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

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, major algorithmic paradigms such as dynamic programming, s ...

Description

This lecture covers the concept of matrix chain multiplication, focusing on optimal substructure and recursive formula. It explains how dynamic programming can be used to minimize the number of scalar multiplications in matrix multiplication. The instructor illustrates the importance of optimal parenthesization and provides examples to demonstrate the application of the recursive formula. The lecture concludes with a detailed explanation of the bottom-up algorithm for solving matrix chain multiplication problems efficiently.

Instructors (3)

Mikhail Kapralov

Teaching & PhD PhD Students Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth Past EPFL PhD Students Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail Past EPFL PhD Students as codirector Paritosh Garg Courses Algorithms II CS-450 The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing alg

Ola Nils Anders Svensson

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Official source

Ontological neighbourhood

Mathematics

Algebra: Linear algebra

Related concepts (27)

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 multiplication

In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.

Scalar (mathematics)

A scalar is an element of a field which is used to define a vector space. In linear algebra, real numbers or generally elements of a field are called scalars and relate to vectors in an associated vector space through the operation of scalar multiplication (defined in the vector space), in which a vector can be multiplied by a scalar in the defined way to produce another vector. Generally speaking, a vector space may be defined by using any field instead of real numbers (such as complex numbers).

Diagonal matrix

In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagonal matrix is , while an example of a 3×3 diagonal matrix is. An identity matrix of any size, or any multiple of it (a scalar matrix), is a diagonal matrix. A diagonal matrix is sometimes called a scaling matrix, since matrix multiplication with it results in changing scale (size).

Generalized eigenvector

In linear algebra, a generalized eigenvector of an matrix is a vector which satisfies certain criteria which are more relaxed than those for an (ordinary) eigenvector. Let be an -dimensional vector space and let be the matrix representation of a linear map from to with respect to some ordered basis. There may not always exist a full set of linearly independent eigenvectors of that form a complete basis for . That is, the matrix may not be diagonalizable.

Related lectures (32)

Matrix Operations: Addition and Transposition

Covers matrix addition, scalar multiplication, transposition, symmetry, and antisymmetry properties.

Vector Spaces: Operations and Linear Transformations

Explores vector space operations, linear transformations, matrix representation, and linear applications.

Multiplications of vectors and matrices MOOC: MATLAB and Octave for Beginners

Covers the multiplication of vectors and matrices using MATLAB and Octave for beginners.

Linear Algebra: Matrices Properties

Explores properties of 3x3 matrices with real coefficients and determinant calculation methods.

Matrix Algebra: Addition, Scalar Multiplication, Transpose MOOC: Linear Algebra (Part 1)