Lars Hellström:How Eigenvalues Solve Polynomial Equation Systems

Abstract:

The subject of this talk is the use of Gröbner bases for solving polynomial equation systems. Solving polynomial equation systems is fundamentally a problem in algebraic geometry, and as such striding the algebra--geometry dualism of this subject. Classical methods tend to lean heavily on the algebra side, treating equation solving primarily as a matter of finding better equations for describing the solution set; Gaussian elimination is definitely a matter of this, and there is a tradition of using Gröbner bases like that as well. Elimination orders do however often lead to (more) computationally expensive Gröbner basis calculations, which can make them impractical.

An alternative approach, which turns out to make readily available the coordinates of solution points, is to instead focus on the quotient algebra. On the one hand, any Gröbner basis can be utilised to perform effective calculations in the quotient. On the other hand, the quotient algebra has a geometric interpretation as the algebra of functions on the solution variety, which can be used to for example locate the points of that variety. Numerical approximations can be found through eigenvalue/eigenvector calculations, the practical stability and implementation efficiency of which has been thoroughly studied in recent decades.