ylfink@water.waterloo.edu (ylfink) (10/18/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
SCIENTIFIC COMPUTATION SEMINAR
- Thursday, October 20, 1988
Dr. Eleanor Chu, a member of this department, will
speak on
``QR Factorization with Column Pivoting on a Hypercube
Multiprocessor''.
TIME: 4:00 PM
ROOM: DC 1304
ABSTRACT
In this talk we present a new concurrent algorithm for
performing QR factorization with column pivoting on a
hypercube multiprocessor. The scheme involves the
embedding of a two-dimensional grid in the hypercube
network. The resulting processor grid allows us to take
full advantage of the recursive structure of a
hypercube network in directing the interprocessor
communications traffic. The global communication
scheme we employ uses redundant computation to maintain
data proximity and the scheme works equally well
whether pivoting is present or not. Our mapping and
pivoting strategies are such that for a fixed number of
processors the processor idle time is small and either
constant or grows linearly with the dimension of the
matrix. For a given problem the aspect ratio of the
embedded grid is chosen with the objective to minimize
its execution time and storage requirement. A
complexity analysis tells us what the aspect ratio
should be in terms of the shape of the matrix and the
relative speeds of communication and computation. We
shall report numerical experiments performed on a
64-node Intel Hypercube multiprocessor which support
the theoretical results.