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.