Matrices are used almost in every place imaginable… Matrices are used for computer graphics, risk management in the financial industry and all sorts of decision making.. This makes matrix multiplication a necessary operation in various industries.. However matrix multiplication is a very space and time consuming process, specially for huge matrices and this poses a big problem..specially in industries like finance where decisions have to made quickly. Its main significance for combinatorial algorithms is its equivalence to a variety of other problems, such as transitive closure and reduction, solving linear systems, and matrix inversion. Thus a faster algorithm for matrix multiplication implies faster algorithms for all of these problems. Matrix multiplication arises in its own right in computing the results of such coordinate transformations as scaling, rotation, and translation for robotics and computer graphics.

I realised all this when I was doing the shadowbox project. .and my computer frequently ran out of memory.. On searching for algorithms which were space efficient and time efficient.. I was surprised to find out that there were no such algorithms which beat the normal multiplication method in practice. There are algorithms like Strassen’s algorithm which have a lower asymptotic complexity, but are unstable and do not make that much of a difference in practice.

However, parallel computing..provides faster ways of matrix multiplication  using smart divide and conquer techniques. A novel algorithm, called SRUMMA (Shared and Remote memory access based Universal Matrix Multiplication Algorithm), was developed as that provides a better performance and scalability on variety computer architectures than the leading algorithms used today. Unlike other algorithms that are based on message-passing, the new algorithm relies on ARMCI a high performance remote memory access communication (one-sided communication) library developed under the DoE PModels project. In addition to the fast communication (shared memory, remote memory access nonblocking communication), the new algorithm relies on careful scheduling of communication operations to minimize contention in access to blocks of distributed matrices.