An Empirical Distributed Matrix Multiplication Algorithm to Reduce Time Complexity

摘要

Matrix multiplication is an integral component of most of the systems implementing Graph theory, Numerical algorithms, Digital control, Signal and image processing (i.e robotics, computer vision, artificial intelligence e.t.c). So reduction of multiplication time can influence drastically the overall system performance. Based on the importance, this paper presents a novel distributed algorithm for matrix multiplication to lower the time complexity efficiently. For distributed processing, computational time is usually analyzed assuming that all processors are of the same type and operating at same speed. i.e., homogeneous system. A number of autonomous machines are connected by a local area network that makes a distributed computing environment where server and multiple clients exchange their data or information by using message passing technique. The result shows that an enormous amount of time can be reduced by adopting such technique by dividing the tasks on different clients, where execution time grows rapidly with the increase of data on a single machine.