Hybrid optimization technique for matrix chain multiplication using Strassen's algorithm.

Area of Science:

• Computational Mathematics
• Computer Science
• Scientific Computing

Background:

• Matrix Chain Multiplication (MCM) is crucial in scientific computing, graphics, and machine learning.
• Traditional MCM uses Dynamic Programming (DP) with Memoization but suffers from O(n^3) complexity for large matrices.
• Standard matrix multiplication is inefficient for large-scale computations.

Purpose of the Study:

• To develop a hybrid optimization technique for Matrix Chain Multiplication.
• To accelerate matrix multiplication by integrating Strassen's algorithm into MCM.
• To reduce computational complexity and improve efficiency for large matrices.

Main Methods:

• A two-phase approach: (i) optimizing matrix chain order with top-down DP and memoization, and (ii) a hybrid multiplication strategy.
• Selective application of Strassen's algorithm (O(n^2.81)) for matrices with n ≥ 128.
• Comparison with traditional MCM and standalone Strassen's algorithm via computational experiments.

Main Results:

• The hybrid MCM method achieved significant speedups (4x-8x) compared to traditional methods.
• Demonstrated reduction in memory consumption for large-scale applications.
• Maintained numerical accuracy while improving performance.

Conclusions:

• The proposed hybrid MCM approach effectively reduces execution time and memory usage.
• Selective integration of Strassen's algorithm enhances MCM efficiency for large matrices.
• Opens avenues for parallel computing and GPU acceleration in matrix operations.