QR with Shifts

A Julia implementation of QR algorithms. This project implements symmetric matrix reduction to Hessenberg form using Householder reflections, Givens rotation, and QR shift with both Single Shift and Wilson Shift (with deflation).

Overview

This project implements the QR algorithm—one of the most important algorithms in numerical linear algebra for computing eigenvalues. The implementation includes:

• Hessenberg Reduction: Transform any matrix to upper Hessenberg form using Householder reflectors
• Givens QR Iteration: Perform QR decomposition using Givens rotations (efficient for Hessenberg matrices)
• Shifted QR Algorithm: Accelerate convergence using Rayleigh quotient (single) and Wilkinson shifts

Files

File	Description
qr_main.jl	Core algorithm implementations
qr_driver.jl	Test driver and validation scripts

Algorithms

Hessenberg Form

hessenberg_form!(T)

Reduces a matrix T to upper Hessenberg form in-place using Householder reflectors. The implementation uses zero memory allocations.

Givens QR Iteration

givens_qr!(T)

Performs one iteration of the unshifted QR algorithm on a Hessenberg matrix using Givens rotations. Computes T = RQ where QR = T.

Practical QR with Shifts

practical_QR_with_shifts!(T, shift)

Implements the deflation-based practical QR algorithm with two shift strategies:

• "single": Rayleigh quotient shift (μ = T[m,m])
• "wilkinson": Wilkinson shift (eigenvalue of bottom 2×2 block closer to T[m,m])

Features:

• Deflation
• Recursive processing of decoupled submatrices
• Tolerance-based convergence criterion (tol = 1e-35)

Convergence Analysis

convergence_QR(T, shift)

Helper function for analyzing and plotting convergence rates of different shift strategies.