Add DGKS iterative reorthogonalization utility

Add internal::dgks_orthogonalize() implementing the Daniel-Gragg-Kaufman-Stewart criterion for Classical Gram-Schmidt with iterative refinement.

Uses BLAS-2 operations (GEMV) for orthogonalization and checks whether the norm dropped by more than 1/sqrt(2) to decide if reorthogonalization is needed. The primary benefit is numerical robustness — CGS with DGKS reorthogonalization achieves the same stability as MGS while using block operations that can be more efficient when paired with an optimized BLAS in the tall-matrix regime.

API

// Orthogonalize v against first numCols columns of Q.
// Returns stable norm of v after orthogonalization.
RealScalar internal::dgks_orthogonalize(Q, v, numCols, &coeffs, maxIter=2);
RealScalar internal::dgks_orthogonalize(Q, v, numCols, maxIter=2);

Benchmark

Orthogonalizing a random vector against an orthonormal basis (g++ -O3 -march=native -DNDEBUG, double precision):

Size (n x k) MGS (us) DGKS (us) Speedup Winner
8 x 4 0.1 0.2 0.3x MGS
16 x 8 0.1 0.1 0.5x MGS
32 x 16 0.2 0.2 0.9x ~tie
64 x 32 0.4 0.4 1.2x ~tie
128 x 64 1.5 1.6 0.9x ~tie
256 x 128 5.7 6.2 0.9x MGS
512 x 256 21.4 27.1 0.8x MGS
1024 x 512 96.6 168.1 0.6x MGS

Tall matrices (many rows, moderate basis):

Size (n x k) MGS (us) DGKS (us) Speedup Winner
100 x 10 0.2 0.3 0.8x MGS
500 x 10 0.9 1.0 0.9x ~tie
1000 x 10 2.4 2.5 0.9x ~tie
1000 x 50 8.2 6.5 1.3x DGKS
1000 x 100 18.1 14.0 1.3x DGKS

DGKS wins in the tall-matrix regime where GEMV arithmetic intensity is high. For square-ish cases, MGS loop has less overhead. The primary value of DGKS is numerical robustness — guaranteed orthogonality via iterative reorthogonalization, not raw speed.

Tests

13 subtests covering: basic orthogonality (float/double/complex), coefficient accumulation, vector-in-span, already-orthogonal, nearly-dependent, extreme magnitudes, single column, zero columns.

Reference

J.W. Daniel, W.B. Gragg, L. Kaufman, G.W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp. 30 (1976), 772-795.

Edited by Pavel Guzenfeld

Merge request reports

Loading
Loading