matrix-multiplication Algorithm
The matrix-multiplication algorithm is a fundamental mathematical operation that allows two matrices to be combined into a single matrix by performing a series of arithmetic operations on their corresponding elements. Matrices are essentially a collection of numbers arranged in rows and columns, used to represent linear equations, geometric transformations, or other mathematical systems. The algorithm takes two matrices as input, usually denoted as A and B, and produces a new matrix, C, which represents the product of these two matrices. The primary condition for matrix multiplication is that the number of columns in matrix A must be equal to the number of rows in matrix B, allowing the resulting matrix C to have the same number of rows as matrix A and the same number of columns as matrix B.
The matrix-multiplication algorithm works by iterating through each element in the rows of matrix A and the columns of matrix B, performing a series of multiplications and additions. For each element in the resulting matrix C, the algorithm multiplies the corresponding row elements of matrix A with the corresponding column elements of matrix B, and adds them up to form a single value. This process is repeated for all elements in the matrices until the entire resulting matrix C is filled. Due to its computational complexity, which is typically O(n^3) for an n x n matrix, various optimizations and parallelization techniques have been proposed over the years to improve the performance of matrix multiplication, such as the Strassen algorithm, the Karatsuba algorithm, and the Coppersmith-Winograd algorithm. These optimized algorithms have found numerous applications in fields such as computer graphics, data science, and machine learning, where efficient matrix manipulation is crucial for solving complex problems.
// matrix chain multiplication problem
// https://en.wikipedia.org/wiki/Matrix_chain_multiplication
// www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/
// package main
package matrixChainMultiplication
import "fmt"
func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}
func matrixChainRec(D []int, i, j int) int {
// d[i-1] x d[i] : dimension of matrix i
if i == j {
return 0
}
q := 1 << 32
for k := i; k < j; k++ {
prod := matrixChainRec(D, i, k) + matrixChainRec(D, k+1, j) + D[i-1]*D[k]*D[j]
q = min(prod, q)
}
return q
}
func matrixChainDp(D []int) int {
// d[i-1] x d[i] : dimension of matrix i
N := len(D)
dp := make([][]int, N) // dp[i][j] = matrixChainRec(D, i, j)
for i := 0; i < N; i++ {
dp[i] = make([]int, N)
dp[i][i] = 0
}
for l := 2; l < N; l++ {
for i := 1; i < N-l+1; i++ {
j := i + l - 1
dp[i][j] = 1 << 31
for k := i; k < j; k++ {
prod := dp[i][k] + dp[k+1][j] + D[i-1]*D[k]*D[j]
dp[i][j] = min(prod, dp[i][j])
}
}
}
return dp[1][N-1]
}
/*
func main() {
D := []int{2, 2, 2, 2, 2} // 4 matrices
fmt.Print(matrixChainRec(D, 1, 4), "\n")
fmt.Print(matrixChainDp(D), "\n")
}
*/
