COMMUNICATION COMPLEXITY AND SPEED-UP IN THE EXPLICIT DIFFERENCE METHOD
Abstract
An earlier suggested parallel "ring" algorithm for solving the spatially one-dimensional initial-boundary-value problem (IBVP) for a parabolic equation using an explicit difference method is shortly described. Theoretical estimates for both of the speed-up function and the communication complexity of this parallel algorithm are studied. The speed-up function is determined as the ratio between times for realization of the algorithm in sequentional and parallel cases. Theoretical estimates of the speed-up function show the significant speed-up of the parallel algorithm in comparison with the serial one for a large number of values computed by one processor during one time level and it is shown that the the speed-up tends to the number of used processors. Communication complexity is determined as a ratio between the number of interchanges and the number of arithmetical operations. It has been proven that the coefficient of the communication complexity for spatially m-dimensional IBVP tends in general to ¾.
References
- J. Appl. Num. Math. 11, 5 (1993). Crossref, ISI, Google Scholar
- Proc. Camb. Phil. Soc. 43, 60 (1947). Google Scholar
-
T. L. Freeman and C. Phillips , Parallel Numerical Algorithms ( Prentice Hall , 1992 ) . Google Scholar - SIAM Review 32(1), 54 (1990). Crossref, ISI, Google Scholar
-
G. H. Golub and C. F. Van Loan , Matrix Computations ( The Johns Hopkins University Press , Baltimore and London , 1989 ) . Google Scholar - IBM Journal of Research and Development 18(2), 138 (1974). Crossref, ISI, Google Scholar
-
J. M. Ortega and R. G. Voigt , Solution of PDE on Vector and Parallel Computers ( SIAM , Philadelphia , 1985 ) . Crossref, Google Scholar - Journal of Electrical Engineering 50(10/s), 36 (1999). Google Scholar
- J. Soc. Indust. Appl. Math. 3, 28 (1955). Crossref, ISI, Google Scholar
- Kybernetika 37(2), 171 (2001). ISI, Google Scholar
-
E. E. Tyrtyshnikov , Numerical Solution of Partial Differential Equation ( Kosice , Slovakia , 1992 ) . Google Scholar - Computational Processes and Systems N9, 3 (1993). Google Scholar
P. Zoeteweij ,Lecture Notes in Computer Science 2627 (2003) pp. 171–184. Google ScholarV. S. Adve , An Integrated Compilation and Performance Analysis Environment for Data Parallel Programs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM) p. 50–es. Google Scholar- Int. J. Numer. Meth. in Engineering 40, 2653 (1997). Crossref, ISI, Google Scholar
- Building Research Journal 48(1), 43 (2000). ISI, Google Scholar
V. Horak and P. Gruber , Parallel Numerics '05 (Theory and Applications) (University of Salzburg and Jozef Stefan Institute Ljubljana, 2005) pp. 47–56. Google Scholar


