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.