



01321nas a2200157   4500008004100000022001400041245005800055210005800113260001500171300001000186490000700196520083300203100002401036700002501060856007801085       2005                        eng d  a1068-961300aQR Factorizations Using a Restricted Set of Rotations0 aQR Factorizations Using a Restricted Set of Rotations  c2005/07/11  a20-270 v213 aAny matrix A of dimension m × n (m ≥ n) can be reduced to upper triangular form
by multiplying by a sequence of mn − n(n + 1)/2 appropriately chosen rotation matrices. In this
work, we address the question of whether such a factorization exists when the set of allowed rotation
planes is restricted. We introduce the rotation graph as a tool to devise elimination orderings in
QR factorizations. Properties of this graph characterize sets of rotation planes that are sufficient (or
sufficient under permutation) and identify rotation planes to add to complete a deficient set. We
also devise a constructive way to determine all feasible rotation sequences for performing the QR
factorization using a restricted set of rotation planes. We present applications to quantum circuit
design and parallel QR factorization.1 aO'Leary, Dianne, P.1 aBullock, Stephen, S.  uhttp://www.emis.ams.org/journals/ETNA/vol.21.2005/pp20-27.dir/pp20-27.pdf