Skip to content

Schur Decomposition

quatica.decomp.schur

Quaternion Schur Decomposition via Hessenberg reduction and implicit shifted QR.

Strategy: - Reduce once to Hessenberg: H0 = P0 * A * P0^H - Iterate implicit shifted QR steps in Realp (4n x 4n) using quaternion-structured Givens rotations and optional Francis double-shift for improved convergence: HR_{k+1} = R_k @ Q_k + sigma_k I, where Q_k R_k ≈ HR_k - sigma_k I - Accumulate total Q in real block, then contract to quaternion and combine with P0

Notes: - Shift: Rayleigh, Wilkinson (1x1/2x2 trailing block), or double (Francis-style two shifts) - Deflation: aggressively zero H[i, i-1] when sufficiently small within the active window - All operations preserve quaternion structure through Realp mapping + fixed 8x8 permutation

quaternion_schur(A, max_iter=5000, tol=1e-12, shift='wilkinson', verbose=False, return_diagnostics=False)

Compute a (quaternion) Schur-like decomposition A = Q T Q^H.

Parameters: - A: square quaternion matrix (n x n) - max_iter: maximum number of QR iterations - tol: deflation tolerance for subdiagonal entries - shift: 'rayleigh' | 'wilkinson' | 'double' (Francis two-shift surrogate) - verbose: print progress

Returns: - Q: unitary quaternion matrix - T: upper (quasi-)triangular quaternion matrix (Schur form)

quaternion_schur_experimental(A, variant='aed_windowed', max_iter=1000, tol=1e-10, window=12, verbose=False, return_diagnostics=False)

Experimental Schur variants with windowed AED and a Francis-like two-shift chase.

WARNING: Experimental. API and behavior may change. Does not affect stable variants.

Variants
  • 'aed_windowed' : restrict bulge-chase and deflation to a trailing window (approx. AED)
  • 'francis_ds' : perform a two-shift bulge chase per outer iteration (surrogate DS)
Notes
  • Operates purely in quaternion domain using 2x2 Householder similarities.
  • Uses real scalar shifts derived from trailing block; keeps quaternion structure.
  • Maintains similarity via left-row and right-column updates.

quaternion_schur_pure(A, max_iter=500, tol=1e-10, verbose=False, return_diagnostics=False, shift_mode='none')

Pure quaternion QR iteration (unshifted), no real expansion.

Algorithm

1) Reduce A to Hessenberg H via quaternion Householder similarity. 2) For k=1..max_iter: compute QR of H using quaternion Householders (left) then set H <- R @ Q (QR iteration). Accumulate Q_total.

Note: Convergence is generally slower than shifted QR; intended as a structure-preserving baseline for Lead 2 experiments.

quaternion_schur_pure_implicit(A, max_iter=500, tol=1e-10, verbose=False, return_diagnostics=False, shift_mode='rayleigh')

Pure quaternion implicit QR via 2x2 Householder (bulge-chasing style).

  • Keeps computation in quaternion domain
  • Uses optional simple shift (Rayleigh) to accelerate convergence
  • Left-apply 2x2 Householder to zero subdiagonal, right-apply its Hermitian to preserve similarity

quaternion_schur_unified(A, variant='rayleigh', max_iter=1000, tol=1e-10, aed_factor=None, precompute_shifts=True, power_shift_steps=5, aed_window=None, verbose=False, return_diagnostics=False)

Unified Schur API exposing common variants.

Variants
  • 'none' : pure QR iteration, no shift (Lead 2 baseline)
  • 'rayleigh' : pure QR iteration with Rayleigh shift (Lead 2 simple shift)
  • 'implicit' : pure quaternion implicit QR (bulge-chase) with Rayleigh shift
  • 'aed' : implicit + aggressive early deflation (AED) (quaternion-only)
  • 'ds' : implicit + double-shift surrogate from trailing 2x2 (quaternion-only)
Notes
  • For 'aed' and 'ds', operations stay in the quaternion domain using 2x2 Householder similarities.
  • aed_window (optional): when set, restrict AED checks to the trailing window of size aed_window to improve efficiency on larger matrices. Defaults to full sweep when None.