CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Chain Multiplication of Dense Matrices: Proposing a Shared Memory based Parallel Algorithm

by Tirtharaj Dash, Tanistha Nayak
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 58 - Number 1
Year of Publication: 2012
Authors: Tirtharaj Dash, Tanistha Nayak
10.5120/9245-3408

Tirtharaj Dash, Tanistha Nayak . Chain Multiplication of Dense Matrices: Proposing a Shared Memory based Parallel Algorithm. International Journal of Computer Applications. 58, 1 ( November 2012), 11-16. DOI=10.5120/9245-3408

@article{ 10.5120/9245-3408,
author = { Tirtharaj Dash, Tanistha Nayak },
title = { Chain Multiplication of Dense Matrices: Proposing a Shared Memory based Parallel Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { November 2012 },
volume = { 58 },
number = { 1 },
month = { November },
year = { 2012 },
issn = { 0975-8887 },
pages = { 11-16 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume58/number1/9245-3408/ },
doi = { 10.5120/9245-3408 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:01:24.227382+05:30
%A Tirtharaj Dash
%A Tanistha Nayak
%T Chain Multiplication of Dense Matrices: Proposing a Shared Memory based Parallel Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 58
%N 1
%P 11-16
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Chain multiplication of matrices is widely used for scientific computing. It becomes more challenging when there is large number of floating point dense matrices. Because, floating point operations take more time than integer operations. It would be interesting to lower the time of such chain operations. Now-a-days every multicore processor system has built in parallel computational power. This power can only be utilized when compatible parallel algorithms were used. So, in this work, a shared memory based parallel algorithms has been proposed to compute the multiplication of a long sequence of dense matrices. The algorithms have been tested with long sequence of matrices as input. The approach has been with 2×108 flops. The input matrix sequence length was typically varied from 2 to 30. Maximum number of processors used was eight (Eight core processor). Different parameters like speedup, efficiency etc. were also noted. It was concluded that the parallel algorithms could achieve approximately 90% efficiency at best case. The algorithms also showed improved scalability.

References
  1. Cormen, Thomas H. ; Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). "15. 2: Matrix-chain multiplication". Introduction to Algorithms. Second Edition. PHI Learning Private Limited. pp. 331-338. ISBN 978-81-203-2141-0.
  2. Hu, T C. ; M T. Shing (1984). Computation of matrix chain products. Part II. SIAM Journal on Computing (Univ. of California at San Diego: Springer-Verlag) 13 (2): 228–251. doi:10. 1137/0213017. ISSN 0097-5397.
  3. Kreyszig, E; Advanced Engineering Mathematics. Wiley-India Edition. 8th edition. ISBN: 978-81-265-0827-3.
  4. Dou, Y. ; Vassiliadis, S. ; Kuzmanov, G. K. ; Gaydadjiev, G. N. ; 64-bit Floating-Point FPGA Matrix Multiplication. FPGA'05, February 20–22, 2005, Monterey, California, USA, pages 86-95.
  5. Choi, J. ; A Fast Scalable Universal Matrix Multiplication Algorithm on Distributed-Memory Concurrent Computers. In11th IEEE International Parallel Processing Symposium (IPPS '97), pages 310–314, April 1997.
  6. Yuster, R. ; Zwick, U. ; Fast sparse matrix multiplication. In the proceedings of the 12th Annual European Symposium on Algorithms (ESA'04).
  7. Demetrescu, C. ; Italiano, G. F. ; Fully dynamic transitive closure: Breaking through the O(n2) barrier. In Proc. of 41st FOCS, pages 381–389, 2000.
  8. Roditty, L; Zwick, U; Improved dynamic reachability algorithms for directed graphs. In Proc. of 43rd FOCS, pages 679–688, 2002.
  9. Mulmuley, K; Vazirani, U. V. ; Vazirani, V. V. ; Matching is as easy as matrix inversion. Com-binatorica, 7:105–113, 1987.
  10. Rabin, M. O; Vazirani, V. V. ; Maximum matchings in general graphs through randomization. Journal of Algorithms, 10:557–567, 1989.
  11. N. Alon, R. Yuster, and U. Zwick. Color-coding. Journal of the ACM, 42:844–856, 1995.
  12. N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17:209–223, 1997.
  13. R. Yuster and U. Zwick. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In Proc. of 15th SODA, pages 247–253, 2004.
  14. J. Ne?set?ril and S. Poljak. On the complexity of the subgraph problem. Commentationes Mathe-maticae Universitatis Carolinae, 26(2):415–419, 1985.
  15. L. Roditty and U. Zwick. Improved dynamic reachability algorithms for directed graphs. In Proc. of 43rd FOCS, pages 679–688, 2002.
  16. K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105–113, 1987.
  17. Czumaj, A; Parallel Algorithm for Matrix Chain Product and the Optimal Triangulation Problems (Extended abstract). STACS'93 version. Supported in part by the EC Cooperative Action IC 1000 Algorithms for Future Technologies "ALTEC" and by the grant KBN 2-1190-91-01, Pages 1-12.
  18. T. C. Hu, M. T. Shing; Some theorems about matrix multiplications, FOCS 1980, pp. 28-35.
  19. E. Horowitz, S. Sahani, S. Rajasekaran; Fundamental of Computer Algorithms, 2nd edition. Universities Press (India) Private Limited (2008), ISBN: 81-7371-612-9.
  20. R. Chandra, L. Dagum, D. Kohr, D. Maydan, J. McDonald, R. Menon, Parallel programming in OpenMP, Morgan Kaufmann Publisher (2001). ISBN 1-55860-671-8.
  21. D. A. Patterson, J. L. Hennessy; Computer Organization and Design: The Hardware/Software Interface ARM edition. 4th edition. Morgan Kaufmann Publisher (2009), ISBN: 978-81-312-2274-4.
  22. C. Hamacher, Z. Vranesic, S. Zaky; Computer Organization. International Edition 2002. McGraw-Hill Higher Education, ISBM: 007-120411-3.
  23. M. J. Quinn; Parallel Programming in C with MPI and OpenMP. International Edition 2003. McGraw-Hill Higher Education, ISBM: 007-282256-2.
  24. T. Dash, T. Nayak, S. Chattopadhyay; Offline Handwritten Signature Verification using Associative Memory Net. International Journal of Advanced Research in Computer Engineering & Technology, Volume 1, Issue 4, pp. 370-374, 2012.
  25. T. Dash, S. Chattopadhyay, T. Nayak; Handwritten Signature Verifications Using Adaptive Resonance Theory Type-2 (ART-2) Net. Journal of Global Research in Computer Science, Volume 3, No. 8, pp. 21-25, 2012.
  26. A. Silberschatz, P. B. Galvin, G. Gagne; Operating System Concepts. International student version, 8th edition. John Wiley & Sons Inc. , U. K. , ISBN: 978-81-265-2051-0.
  27. M. A. Ismail, S. H. Mirza, T. Altaf; Concurrent Matrix Multiplication on Multi-Core Processors. International Journal of Computer Science and Security (IJCSS), Volume (5): Issue (2): 2011, pp. 208-220.
  28. T. Dash, T. Nayak, S. Chattopadhyay; Handwritten Signature Verification (Offline) using Neural Network Approaches: A Comparative Study. International Journal of Computer Applications. ISSN: 0975-8887, November'12. (accepted, in press)
  29. T. Dash; Time Efficient Approach to Offline Hand Written Character Recognition using Associative Memory Net. International Journal of Computing and Business Research. ISSN: 2229–6166, Vol. 3, Issue-3, 2012.
  30. T. Dash, T. Nayak, S. Chattopadhyay; Offline Verification of Hand Written Signature Using Adaptive Resonance Theory Net (Type-1). In Proc. of ICECT-2012, Vol-2, pp. 205-210.
Index Terms

Computer Science
Information Sciences

Keywords

Chain multiplication computing dense matrix multicore shared memory flops efficiency speedup scalability

Powered by PhDFocusTM