Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actual
Posted: Tue Jul 12, 2022 8:04 am
Given a sequence of matrices, find the most efficient way tomultiply these matrices together. The problem is not actually toperform the multiplications, but merely to decide in which order toperform the multiplications. We have many options to multiply achain of matrices because matrix multiplication is associative. Inother words, no matter how we parenthesize the product, the resultwill be the same. For example, if we had four matrices A, B, C, andD, we would have:
(ABC)D = (AB)(CD) =A(BCD) = ....
However, the order in which we parenthesize the product affectsthe number of simple multiplications needed to compute the product,or the efficiency. For example, suppose A is a 10 × 30 matrix, B isa 30 × 5 matrix and C is a 5 × 60 matrix. Then
(AB)C = (10 × 30 × 5) + (10 × 5 × 60) = 1500 + 3000 = 4500multiplications.
How many multiplications does it take to compute A(BC)? Which ofthe two parenthesizations requires less number ofmultiplications?
(ABC)D = (AB)(CD) =A(BCD) = ....
However, the order in which we parenthesize the product affectsthe number of simple multiplications needed to compute the product,or the efficiency. For example, suppose A is a 10 × 30 matrix, B isa 30 × 5 matrix and C is a 5 × 60 matrix. Then
(AB)C = (10 × 30 × 5) + (10 × 5 × 60) = 1500 + 3000 = 4500multiplications.
How many multiplications does it take to compute A(BC)? Which ofthe two parenthesizations requires less number ofmultiplications?