Matrix Chain Multiplication by using JavaScript

Matrix Chain Multiplication | DP-8

In this article, we are going to learn about Matrix Chain Multiplication by using JavaScript, Matrix Chain Multiplication refers to finding the most efficient way to multiply a sequence of matrices together, minimizing the total number of scalar multiplications required.

Approaches to perform Matrix Chain Multiplication by using JavaScript

Recursive Solution (Naive)
Top-Down Memoization

We will explore all the above methods along with their basic implementation with the help of examples.

Approach 1: Recursive Solution (Naive)

The recursive solution (naive) for matrix chain multiplication repeatedly splits the chain at different positions and calculates the cost, returning the minimum number of multiplications needed.

Example:

Javascript

function matrixChain(p, i, j) {
    if (i === j) return 0;
    let minCost = Number.MAX_SAFE_INTEGER;
 
    for (let k = i; k < j; k++) {
        let cost = matrixChain(p, i, k) +
            matrixChain(p, k + 1, j) +
            p[i - 1] * p[k] * p[j];
 
        if (cost < minCost) {
            minCost = cost;
        }
    }
 
    return minCost;
}
 
const dimensions = [10, 30, 5, 60];
const result = matrixChain(dimensions, 1, dimensions.length - 1);
console.log("Minimum number of multiplications:", result);

Output

Minimum number of multiplications: 4500

Approach 2: Top-Down Memoization

Top-Down Memoization for matrix chain multiplication optimizes by storing computed results, reducing redundant calculations, and recursively finding the minimum multiplications needed for matrix chain ordering.

Syntax:

Example:

Javascript

function matrixChain(p) {
    const n = p.length;
    const memo = Array.from({ length: n }, () => Array(n).fill(-1));
 
    function recursive(i, j) {
        if (i === j) return 0;
        if (memo[i][j] !== -1) return memo[i][j];
 
        let minCost = Number.MAX_SAFE_INTEGER;
 
        for (let k = i; k < j; k++) {
            let cost = recursive(i, k) +
                recursive(k + 1, j) + p[i - 1] * p[k] * p[j];
            if (cost < minCost) minCost = cost;
        }
 
        memo[i][j] = minCost;
        return minCost;
    }
 
    return recursive(1, n - 1);
}
 
const matrix = [10, 20, 25, 60];
const result = matrixChain(matrix);
console.log("Minimum number of multiplications:", result);

Output

Minimum number of multiplications: 20000

Tags:

#JavaScript-DSA #JavaScript-Program #JavaScript #Web Technologies

Matrix Chain Multiplication | DP-8

Matrix Chain Multiplication by using JavaScript

Approaches to perform Matrix Chain Multiplication by using JavaScript

Approach 1: Recursive Solution (Naive)

Javascript

Approach 2: Top-Down Memoization

Javascript

Contact Us