|
PARALLEL CLASSICAL ALGORITHMS AND THEIR COMMUNICATION COSTS
2
Author(s):
ARVIND SINGH , R. K. KATARE
Vol - 5, Issue- 10 ,
Page(s) : 42 - 47
(2014 )
DOI : https://doi.org/10.32804/IRJMST
Abstract
Abstract
In the present study the benefits of the new algorithms for symmetric-indefinite factorizations and computing the symmetric eigen decomposition along with SVD are discussed. The algorithms presented here assume limitations on local memory that are often not necessary, especially in strong-scaling scenarios. We have analyzed the fast parallel algorithms and algorithms which are more effective in practice, making it robust for library deployment, applying it to other linear algebra computations, and developing even faster matrix multiplication algorithms to all areas of future work.
- G. Ballard, D. Becker, J. Demmel, J. Dongarra, A. Druinsky, I. Peled, O. Schwartz, S. Toledo, and I. Yamazaki. Communication-Avoiding Symmetric-Indefinite Factorization. Tech. rep. UCB/EECS-2013-127. EECS Department, University of California, Berkeley, July 2013.
- G. Ballard, J. Demmel, and N. Knight. Avoiding Communication in Successive Band Reduction. Tech. rep. UCB/EECS-2013-131. EECS Department, University of California, Berkeley, July 2013.
- G. Ballard, J. Demmel, and I. Dumitriu. Communication-optimal parallel and sequential eigenvalue and singular value algorithms. EECS Technical Report EECS-2011-14. UC Berkeley, Feb. 2011.
- G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz. “Communication-optimal parallel algorithm for Strassen's matrix multiplication". In: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA '12. New York, NY, USA: ACM, 2012, pp. 193-204.
- B. Lipshitz, G. Ballard, J. Demmel, and O. Schwartz. “Communication-avoiding parallel Strassen: Implementation and performance". In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. SC '12. Salt Lake City, Utah, 2012, 101:1-101:11.
- L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley. ScaLAPACK Users' Guide. Also available from http://www.netlib.org/scalapack/. Philadelphia, PA, USA: SIAM, May 1997.
- L. Cannon. “A cellular computer to implement the Kalman filter algorithm". PhD thesis. Bozeman, MN: Montana State University, 1969.
- R. Agarwal, F. Gustavson, and M. Zubair. “A high-performance matrix-multiplication algorithm on a distributed-memory parallel computer, using overlapped communication". In: IBM Journal of Research and Development 38.6 (1994), pp. 673-681.
- R. A. van de Geijn and J. Watts. “SUMMA: scalable universal matrix multiplication algorithm". In: Concurrency - Practice and Experience 9.4 (1997), pp. 255-274.
- L. Grigori, J. Demmel, and H. Xiang. “CALU: A Communication Optimal LU Factorization Algorithm". In: SIAM Journal on Matrix Analysis and Applications 32.4 (2011), pp. 1317-1350.
- G. Ballard, J. Demmel, B. Lipshitz, O. Schwartz, and S. Toledo. “Communication efficient Gaussian elimination with partial pivoting using a shape morphing data layout". In: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA '13. Montreal, Quebec, Canada: ACM, 2013, pp. 232-240.
- J. Demmel, L. Grigori, M. Hoemmen, and J. Langou. “Communication-optimal Parallel and Distributed QR and LU Factorizations". In: SIAM Journal on Scientific Computing 34.1 (2012), A206-A239.
- M. Mohiyuddin, M. Hoemmen, J. Demmel, and K. Yelick. “Minimizing communication in sparse matrix solvers". In: Proceedings of the International Conference on High Performance Computing Networking, Storage and Analysis. SC '09. Portland, Oregon, 2009, 36:1-36:12.
|