QRF, direct rotations

Instead of eliminating one entry at a time, the method rotates an entire active column directly into its coordinate direction.

• For each active column, construct a proper rotation in the plane spanned by that column and the first active coordinate vector
• Choose the sign of the completed pivot so the column rotates toward the nearer of e₁ and −e₁, keeping the angle at most π/2
• The rotation leaves the orthogonal complement of the active plane unchanged and zeros the entire subdiagonal part of the active column in one step
• The completed row and column are deflated, and the same construction is repeated on the trailing submatrix
• The rotation can be written as U = I + B(J − I₂)Bᵀ and reduced to a compact block form
• The product UA can be computed without constructing U, using a row-vector product and a rank-1 update
• A numerical example shows that the Householder and direct-rotation next matrices differ only in the sign of the completed first row
• In the active 2D plane, the direct rotation equals an e₁-coordinate reflection composed with the corresponding Householder reflection
• In the full space, this gives U = P H, so direct rotation is not a fundamentally different QR elimination mechanism from Householder QR
• The direct-rotation representation makes the active plane and signed angle explicit, which gives an immediate continuous orientation-preserving interpolation from I to U
• The same plane-angle data can be recovered from LAPACK Householder QR output — the completed pivot, reflector scalar and stored reflector tail — with linear work in the number of active rows

The active column and its first coordinate vector determine a two-dimensional plane. Rotating inside that plane can align the column with either the positive or negative coordinate direction while leaving the orthogonal complement fixed. Choosing the nearer direction limits the rotation angle, and once the column is aligned, only its leading active entry remains, so every entry below it is zero simultaneously. The later Householder derivation shows that this endpoint elimination is the same Householder step up to a simple orientation-correcting sign reflection.

The PDF page links below are best-effort: most browsers support them, but some viewers may ignore the page hint.

How is this different from Householder QR?

It is closely aligned with Householder QR. The direct rotation and the corresponding Householder reflection act in the same two-dimensional plane and leave the same orthogonal complement unchanged. The direct rotation can be written as the Householder reflection followed by an orientation-correcting reflection: U = P H. The main distinction is therefore the representation: Householder QR uses a reflector normal and scalar, while the direct-rotation form makes the active plane and signed rotation angle explicit.

Was this direct-rotation idea known previously?

Yes. After developing this construction, we found that the underlying one-vector rotation and its possible use for matrix triangularization had been described by Constantine and Gower in 1978. The paper discusses Householder transformations, but its title—Some Properties and Applications of Simple Orthogonal Matrices—does not signal that it contains a direct plane rotation for matrix triangularization. It therefore did not appear readily in the QR and direct-rotation searches under which we were looking.

Reference: A. G. Constantine and J. C. Gower, “Some Properties and Applications of Simple Orthogonal Matrices,” IMA Journal of Applied Mathematics, vol. 21, no. 4, June 1978, pp. 445–454.

What changes after one Householder step versus one direct-rotation step?

With the sign conventions used here, the transformed matrices differ only in the sign of the completed pivot row. The trailing active matrix is the same, so the subsequent elimination steps are the same up to the corresponding row-sign convention.

Why keep the direct-rotation representation?

It makes the active plane and the signed rotation angle explicit. Those quantities give a direct geometric interpretation and an immediate continuous, orientation-preserving path from the identity to the endpoint QR transformation.

Why is this not Givens QR?

Givens QR normally uses a sequence of coordinate-plane rotations and eliminates one subdiagonal entry at a time. This representation uses one active plane and one proper rotation for the whole active column.

How are matrix multiplications avoided?

The rotation matrix is never formed. Its action on the active matrix is reduced algebraically to a row-vector product and a rank-1 update.

Can the plane and angle be recovered from LAPACK Householder QR output?

Yes. From the completed pivot β, reflector scalar τ and reflector tail stored below the diagonal, the corresponding direct-rotation plane and signed angle can be reconstructed with work linear in the number of active rows.

Quick feedback helps us improve the site.