Gauss-Seidel is 5x slower than Jacobi — and loop unrolling alone won't fix it
Measuring Gauss-Seidel loop-carried dependency and fixing it via loop unrolling
Gauss-Seidel converges in half the iterations of Jacobi, yet runs 4–5 times slower because its in-place update creates a loop-carried dependency that blocks vectorization. Using OSACA on compiled assembly, the author measures a 12-cycle latency bound per element versus Jacobi's 1-cycle dependency and 3-cycle throughput floor. Naive unrolling fails because the dependency is mathematical, not a compiler oversight. The post explores how to rewrite the dependency away to recover Gauss-Seidel's convergence advantage without sacrificing hardware efficiency.
Gauss-Seidel's faster convergence is bought entirely at the price of a serialized, 12-cycle-per-element dependency chain that the compiler simply cannot break on its own.
- mota7
"... and this is the whole ballgame: ", "jump out immediately", "... and the idea is disarmingly simple", etc etc.
Written by Claude AI. Which is a problem because Claude text is riddled with engagement bait and filler, making it exhausting to read.
- hwita
It looks like this analysis extends to the successive over-relaxation (SOR) method. Does it extend to the symmetric successive over-relaxation method?
- sheafification
I doubt outside of a few exceptional cases that one is going to do better on CPU-bound problems than a well-written LAPACK implementation built for the architecture you intend to run on.
Maybe pedagogy was the point? I didn’t really get that from the article, maybe some intention was lost by filtering it through AI.