World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

COMMUNICATION COMPLEXITY AND SPEED-UP IN THE EXPLICIT DIFFERENCE METHOD

    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

    • K. Burrage, J. Appl. Num. Math. 11, 5 (1993). Crossref, ISIGoogle Scholar
    • J. Crank and P. Nicolson, Proc. Camb. Phil. Soc. 43, 60 (1947). Google Scholar
    • T. L.   Freeman and C.   Phillips , Parallel Numerical Algorithms ( Prentice Hall , 1992 ) . Google Scholar
    • K. Gallivan, R. J. Plemmons and A. H. Sameh, SIAM Review 32(1), 54 (1990). Crossref, ISIGoogle Scholar
    • G. H.   Golub and C. F.   Van Loan , Matrix Computations ( The Johns Hopkins University Press , Baltimore and London , 1989 ) . Google Scholar
    • P. M. Kogge, IBM Journal of Research and Development 18(2), 138 (1974). Crossref, ISIGoogle Scholar
    • J. M.   Ortega and R. G.   Voigt , Solution of PDE on Vector and Parallel Computers ( SIAM , Philadelphia , 1985 ) . CrossrefGoogle Scholar
    • P. Purcz, Journal of Electrical Engineering 50(10/s), 36 (1999). Google Scholar
    • D. W. Peaceman and H. H. Rachford, J. Soc. Indust. Appl. Math. 3, 28 (1955). Crossref, ISIGoogle Scholar
    • P. Purcz, Kybernetika 37(2), 171 (2001). ISIGoogle Scholar
    • E. E.   Tyrtyshnikov , Numerical Solution of Partial Differential Equation ( Kosice , Slovakia , 1992 ) . Google Scholar
    • E. E. Tyrtyshnikov, Computational Processes and Systems N9, 3 (1993). Google Scholar
    • P. Zoeteweij, Lecture Notes in Computer Science 2627 (2003) pp. 171–184. Google Scholar
    • V. S. Adveet al., 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
    • G. Pini and M. Putti, Int. J. Numer. Meth. in Engineering 40, 2653 (1997). Crossref, ISIGoogle Scholar
    • M. Pavluš, Building Research Journal 48(1), 43 (2000). ISIGoogle 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