Gauss-Seidel algorithm convergence
Posted: Tue Aug 04, 2020 11:39 am
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
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