RFC 6330 §5.4.2 — 5-phase sparse Gaussian elimination.

Solves A·C = D for intermediate symbols C given constraint matrix A and received encoding symbols D, using the sparse 5-phase algorithm that is O(L²) instead of O(L³).

Algorithm outline

Phase 1 — Forward elimination on I+U columns. Phase 2 — Dense GE on U columns of residual rows. Phase 3 — Eliminate U columns from first i rows (Errata 9/10). Phase 4 — Eliminate I columns from rows i..M-1. Phase 5 — Final scaling and below-diagonal elimination.

Operations applied to A during Phase 1 are tracked and replayed on D during Phase 3 (reverse) and Phase 5 (forward), per Errata 9.