LECTURE 2
Communication and computation in some parallel algorithms
This lecture will consider the issues of communication and
computation in parallel algorithms for both numerical and non-numerical
problems. Numerical problems will be illustrated by Gaussian elimination
for the solution of linear systems,
the method of Hestenes for the SVD, and Jacobi's method for the computation
of eigenvalues of a symmetric matrix. Non-numerical problems will be
illustrated by merging and sorting.
The importance of communication in hardware will also be mentioned.
Related lectures
Much of the material is covered in my lectures
Bibliography
-
R. P. Brent,
Parallel algorithms for digital signal processing,
Numerical Linear Algebra, Digital Signal
Processing and Parallel Algorithms,
Springer-Verlag, 1991, 93-110.
- R. P. Brent,
Parallel algorithms in linear algebra,
Proceedings Second NEC Research Symposium
(Tsukuba, Japan, August 1991), SIAM, Philadelphia, 1993, 54-72.
-
R. P. Brent,
The LINPACK benchmark on the AP 1000,
Proc. Frontiers '92, IEEE Press, 1992, 128-135.
-
R. P. Brent and H. T. Kung,
The area-time complexity of binary multiplication,
J. ACM 28 (1981), 521-534.
- A. Tridgell
and R. P. Brent,
A general-purpose parallel sorting algorithm,
International J. High Speed Computing 7 (1995), 285-301.
- A. Tridgell,
R. P. Brent and
B. D. McKay,
Parallel integer sorting,
Tech. Report TR-CS-97-10, ANU, May 1997.
Compressed postscript file of the transparencies used in the lecture
Go to next lecture
Return to list of special lectures on algorithms