文章基本信息

标题：AN EFFICIENT ALGORITHM TO MULTIPLY ‘N’ MATRICES ON TWO-DIMENSIONAL MESH NETWORK PARALLEL ARCHITECTURE
本地全文：下载
作者：Shanthi Makka ; Gagandeep Arora
期刊名称：International Journal of Early Childhood Special Education
电子版ISSN：1308-5581
出版年度：2022
卷号：14
期号：1
页码：2204-2214
DOI：10.9756/INT-JECSE/V14I1.256
语种：English
出版社：International Journal of Early Childhood Special Education
摘要：In mathematics, matrix multiplication or matrix product is a binary operation that produces resultant matrix after multiplying two matrices concurrently and matrix multiplication is implemented for composition of linear maps, graphics-Graphic software such as Adobe Photoshop for rendering of images, Cryptography, wireless communication, Economics, for finding area of triangle, collinear points, for finding Solution of Linear Equations, Records, Engineering, Physics and machine learning. Multiple numbers of matrices along with dimensions are given, before multiplying we need to find an optimal sequence of matrices i.e., the order of matrices with a minimum number of multiplications, after that, we can proceed with multiplication process. Deciding of optimal order minimizes time complexity. Matrix multiplication follows the associative law, and if we alter the sequence of the matrices, it does not affect the final result. However, the cost of matrix multiplication greatly depends on the order in which the matrices are multiplied. The sequence which we follw to multiply „n‟ number of matrices saves computational time. First we find out Optimal Sequence using Dynmaic approach and then we construct a complete binary tree for given „n‟ number of matrices, then multiply chain of two matrices using a two-dimensional mesh network on a SIMD model having wrap-around connections, then designed an algorithm to multiply nxn matrices using “n2“ number of processors. The effectiveness of this approach is demonstrated with comparative study with other approaches.
关键词：Two-dimensional mesh network;Dynamic Programming;Optimal Sequence;Parallelism;High performance;SIMD model