<story><title>Use Gröbner bases to solve polynomial equations</title><url>https://jingnanshi.com/blog/groebner_basis.html</url></story><parent_chain></parent_chain><comment><author>Fermat963</author><text>I did my master&amp;#x27;s thesis on the Gaussian Elimination part of Gröbner Bases making multiple optimizations to the Faugère-Lachartre method (working with Faugere himself) and had the first C (C++ish) public implementation at the time. The thesis can be found here &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;hpac.imag.fr&amp;#x2F;gbla&amp;#x2F;data&amp;#x2F;bib&amp;#x2F;Mart12.pdf&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;hpac.imag.fr&amp;#x2F;gbla&amp;#x2F;data&amp;#x2F;bib&amp;#x2F;Mart12.pdf&lt;/a&gt;.&lt;p&gt;Many ideas from the thesis ended up in the GBLA library used for fast Gaussian Elimination over these large matrices: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;dl.acm.org&amp;#x2F;doi&amp;#x2F;10.1145&amp;#x2F;2930889.2930914&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;dl.acm.org&amp;#x2F;doi&amp;#x2F;10.1145&amp;#x2F;2930889.2930914&lt;/a&gt;&lt;p&gt;This is a nice presentation from Christian Eder explaining how the algorithm works and the different optimization techniques implemented in GBLA &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www-user.rhrk.uni-kl.de&amp;#x2F;~ederc&amp;#x2F;download&amp;#x2F;gbla-aca-2015.pdf&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www-user.rhrk.uni-kl.de&amp;#x2F;~ederc&amp;#x2F;download&amp;#x2F;gbla-aca-201...&lt;/a&gt;</text></comment>
<story><title>Use Gröbner bases to solve polynomial equations</title><url>https://jingnanshi.com/blog/groebner_basis.html</url></story><parent_chain></parent_chain><comment><author>wenc</author><text>I tried using Groebner bases in grad school to solve implicit polynomial equations (part of an optimization problem) but found quickly that it didn’t scale. I ran into trouble with a system of about 300 polynomials and this was with Maple which implemented state of the art algorithms at the time.&lt;p&gt;The computational complexity of Groebner is doubly exponential in the number of variables.</text></comment>