NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
QR Factorizations Using a Restricted Set of Rotations
Published
Author(s)
Dianne M. O'Leary, Stephen Bullock
Abstract
Any matrix of dimension m x n (m greater than or equal to 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.
Givens rotations, parallel QR decomposition, plane rotations, QR decomposition, quantum circuit design, qudits
Citation
O'Leary, D.
and Bullock, S.
(2005),
QR Factorizations Using a Restricted Set of Rotations, Electronic Transactions on Numerical Analysis, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150891
(Accessed October 18, 2025)