Home Journals Books For Authors and Reviewers Online Submission News About Us Contact Us
Search
magazinelogo

Journal of Applied Mathematics and Computation

ISSN Print: 2576-0645 Downloads: 146194 Total View: 1802086
Frequency: quarterly ISSN Online: 2576-0653 CODEN: JAMCEZ
Email: jamc@hillpublisher.com
Search articles within this journal Submit an article

Journal Menu

Volumes & Issues

Current Issue

Download PDF

How to cite this paper

5909

TOTAL VIEWS

More Articles

Article Open Access http://dx.doi.org/10.26855/jamc.2021.09.004

Statistical Analysis of Amir Schoor’s Algorithm in Sequential and Parallel Environment

Rohit Kumar1, Amritanjali1, Soubhik Chakraborty2,*

1Depatment of Computer Science and Engineering, Birla Institute of Technology, Mesra, Ranchi-835215, Jharkhand, India.

2Department of Mathematics, Birla Institute of Technology, Mesra, Ranchi-835215, Jharkhand, India.

*Corresponding author: Soubhik Chakraborty

Published: September 3,2021

Abstract

Matrix multiplication is an essential constituent of most of the computer models and systems implementing Numerical Algorithms, Signal and image processing, Graph theory, Digital control. So reduction of multiplication time can influence drastically the overall system performance. This paper gives a statistical analysis of average time complexity for matrix multiplication with two dense square matrices of order ‘n’ and achieves an empirical Oemp(n2) complexity in sequential and Oemp(n) complexity in parallel computing environment with Amir Schoor’s Algorithm using different probability distributions characterizing the matrix elements. Amir Schoor’s algorithm, although initially developed for sparse matrices, also performs well for dense matrices for two reasons. First, it is faster to work with rows only (as in Schoor’s algorithm) than to work with both rows and columns (as in classical matrix multiplication). Secondly, as we have shown, the n2 comparisons turn out to be “heavier” (in terms of weight, with time of an operation being considered as its weight) than the O(d1d2n3) multiplications on the average, wherein lies the concept of a weight based statistical bound whose empirical estimate over a finite feasible range is empirical Oemp(n2) in our case. Here d1 and d2 are the densities of the pre and post factor matrices.

References

[1] A. Schoor. (1982). “Fast Algorithm for Sparse Matrix Multiplication”. Information Processing Letters, 15(1982), pp. 87-89.

[2] S. Chakraborty and S. K. Sourabh. (2007). “On why an algorithmic time complexity measure can be system invariant rather than system independent”. Applied Mathematics and Computation, Volume 190, Issue 1, 1 July 2007, pp. 195-204.

[3] A. Kumari, N. K. Singh, and S. Chakraborty. (2015). “A Statistical Comperative Study of Some Sorting Algorithms”. International Journal in Foundations of Computer Science & Technology (IJFCST),Vol. 5, No. 4, pp. 21-29, July 2015.

[4] S. K. Panigrahi, S. Chakraborty, and Jibitesh Mishra. (2012). “Statistical Bond of Bubble Sort Algorithm in Serial and Parallel Computations”. International Journal of Computer Science and Network (IJCSN), Volume 1, Issue 1, pp. 2277-5420, February 2012.

[5] https://www.minitab.com/en-us/support/documentation/.

[6] E. Horowitz, S. Sahni, and S. Rajsekaran. (2008). “Fundamentals of Computer Algorithms”, Universities Press, 2nd Edition, 2008, pp. 495-499.

[7] S. K. Panigrahi, Soubhik Chakraborty, Jibitesh Mishra. (2014). “Statistical analysis of Parallel Matrix Multiplication in SIMD model using ‘p’,‘p2’,‘p3’ processor’s with different interconnection network”. 5th International Conference—Confluence The Next Generation Information Technology Summit (Confluence), IEEE Xplore, 978-1-4799-4236-7/14, pp. 858-865, September 2014.

[8] S. K. Panigrahi and S. Chakraborty. (2014). “Statistical Definition of an Algorithm in PRAM model & Analysis of 2x2 Matrix Multiplication in 2n Processors Using Different Networks”. IEEE International Advanced Computing Conference, 978-1-4799-2572, pp. 717-724, February 2014.

[9] S. Pacheco. (2011). “An Introduction to Parallel Programming”, Elsevier Inc., 2011. 

[10] S. Aldea, A. Estebanez, et al. (2015). “An OpenMP Extension that Supports Thread-Level Speculation”, IEEE Transactions on Parallel and Distributed Systems, ISSN: 1045-9219, pp. 78-91, January 2015.

[11] G. Ballard, A. R. Benson, A. Druinsky, B. Lipshitz, and O. Schwartz. (2016). Improving the numerical stability of fast matrix multiplication. SIAM Journal on Matrix Analysis and Applications, 37(4), 1382-1418, 2016.

[12] G. Beniamini and O. Schwartz. (2019). Faster matrix multiplication via sparse decomposition. In Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures. ACM, 11-22, 2019.

[13] G. Bilardi and L. De Stefani. (2017). The I/O complexity of Strassen’s matrix multiplication with recomputation. In Workshop on Algorithms and Data Structures. Springer, 181-192, 2017.

[14] E. Karstadt and O. Schwartz. (2020). Matrix Multiplication, A Little Faster, Journal of the ACM, Vol. 67, Issue 1, 1-31, April 2020.

How to cite this paper

Statistical Analysis of Amir Schoor's Algorithm in Sequential and Parallel Environment

How to cite this paper: Rohit Kumar, Amritanjali, Soubhik Chakraborty. (2021) Statistical Analysis of Amir Schoor's Algorithm in Sequential and Parallel Environment. Journal of Applied Mathematics and Computation, 5(3), 171-186.

DOI: http://dx.doi.org/10.26855/jamc.2021.09.004

Home　|　Journals　|　Books　|　For Authors and Reviewers　|　Online Submission　|　Contact Us　|　About Us

Copyright © 2023 Hill Publishing Group Inc. All Rights Reserved.