Gauss-Seidel algorithm convergence

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Posts: 11
Joined: Sun Apr 23, 2017 12:32 pm

Gauss-Seidel algorithm convergence

Post by Himura78 »

Hi all,

I'm just trying to understand a bit more about constraint solvers, in particular the Gauss-Seidel algorithm. My understanding is that Box2D uses Sequential Impulses, which is analagous to "Projected Gauss-Seidel", and that PGS is simply Gauss-Seidel but with an additional step that clamps the results each iteration to handle inequality constraints.

I'm just curious about the vanilla Gauss-Seidel algorithm, as applied to constrained dynamics problems that only feature equality constraints (and therefore don't require PGS specifically). From what I've read, this algorithm solves a matrix equation Ax = b, but convergence is only assured when the matrix A is "diagonally dominant" or "symmetric and positive definite". In the equation being solved, the matrix in question is (J * W * J^T ).
From my limited understanding of positive definite matrices, it would mean that the calculation (lambda^T * J * W * J^T * lambda) would always be positive... but I don't understand why we can be confident that that's always going to be the case in this context. My question is, is there a way to show that this matrix will always meet the conditions mentioned for convergence? Also, is there an intuitive explanation for why this is the case?

Thanks for your help :)
Post Reply