Hacker News new | ask | show | jobs
by Fermat963 1153 days ago
I did my master'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 https://hpac.imag.fr/gbla/data/bib/Mart12.pdf.

Many ideas from the thesis ended up in the GBLA library used for fast Gaussian Elimination over these large matrices: https://dl.acm.org/doi/10.1145/2930889.2930914

This is a nice presentation from Christian Eder explaining how the algorithm works and the different optimization techniques implemented in GBLA https://www-user.rhrk.uni-kl.de/~ederc/download/gbla-aca-201...

2 comments

I was at a conference in Germany where Faugère presented his work. The room was stunned, but didn't understand. Hendrik Lenstra asked me to spend several days with Faugère, then give an expository talk. My marching orders: Assume nothing: groups, rings, fields.

I ended up lecturing on Gröbner Bases and Faugère's algorithm to an audience that included Buchberger and Faugère. Faugère appreciated my efforts. Buchberger was like a shook up soda bottle; he made a twenty minute speech during the question period.

I coauthored the computer algebra system Macaulay, that first introduced Gröbner Bases to algebraic geometry, opening up the field to applications. At the time there was a separate community in France studying "standard bases", from which I learned a lot. Their focus was on power series not polynomials, but the translation is easy.

Algebraic geometry is a great subject, and computerizing it was a noble cause, but it thrust me into a backwater where the difference between polynomials and power series is considering significant. I got out.

Wow, Macaulay is a big deal! Were you involved in any applications that used your software?
It looks like your thesis is inaccessible at the moment due to the HN kiss of death.