[ont.events] QR Factorization with Column Pivoting on a Hypercube Multiprocessor.

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.