The well-known Gauss pivot method can be used to solve a system of linear equations over a field. I'm aware of two extensions of this method: (i) the Büchberger algorithm for computation of Gröbner bases, (ii) the resolution algorithms for CSPs with Maltsev polymorphisms (see 'Malt'sev Constraints made Simple' by V. Dalmau, 'Constraint satisfaction on finite groups with near subgroups' by T. Feder).

I would like to hear about other variants/extensions of Gauss pivot to settings where we don't have an explicit field/group structure. For instance, can we solve efficiently a system of equations over a permutation group by a similar approach? This problem does not fall in case (ii) above as in general the solutions of an equation will not form a coset, although it should contain problem (ii) as a special case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.