Editing Algebraic geometry (section)

== Computational algebraic geometry ==
One may date the origin of computational algebraic geometry to meeting EUROSAM'79 (International Symposium on Symbolic and Algebraic Manipulation) held at [[Marseille]], France, in June 1979. At this meeting,
* Dennis S. Arnon showed that [[George E. Collins]]'s [[Cylindrical algebraic decomposition]] (CAD) allows the computation of the topology of semi-algebraic sets,
* [[Bruno Buchberger]] presented [[Gröbner basis|Gröbner bases]] and his algorithm to compute them,
* [[Daniel Lazard]] presented a new algorithm for solving systems of homogeneous polynomial equations with a [[computational complexity]] which is essentially polynomial in the expected number of solutions and thus simply exponential in the number of the unknowns. This algorithm is strongly related with [[Francis Sowerby Macaulay|Macaulay]]'s [[Resultant|multivariate resultant]].

Since then, most results in this area are related to one or several of these items either by using or improving one of these algorithms, or by finding algorithms whose complexity is simply exponential in the number of the variables.

A body of mathematical theory complementary to symbolic methods called [[numerical algebraic geometry]] has been developed over the last several decades.  The main computational method is [[homotopy continuation]].  This supports, for example, a model of [[floating point]] computation for solving problems of algebraic geometry.

===Gröbner basis===

{{main|Gröbner basis}}

A [[Gröbner basis]] is a system of [[Ideal (ring theory)#Definitions and motivation|generators]] of a polynomial [[ideal (ring theory)|ideal]] whose computation allows the deduction of many properties of the affine algebraic variety defined by the ideal.

Given an ideal ''I'' defining an algebraic set ''V'':
* ''V'' is empty (over an algebraically closed extension of the basis field), if and only if the Gröbner basis for any [[monomial order]]ing is reduced to {1}.
* By means of the [[Hilbert series]] one may compute the [[dimension of an algebraic variety|dimension]] and the [[degree of an algebraic variety|degree]] of ''V'' from any Gröbner basis of ''I'' for a monomial ordering refining the total degree.
* If the dimension of ''V'' is 0, one may compute the points (finite in number) of ''V'' from any Gröbner basis of ''I'' (see [[Systems of polynomial equations]]).
* A Gröbner basis computation allows one to remove from ''V'' all irreducible components which are contained in a given hypersurface.
* A Gröbner basis computation allows one to compute the Zariski closure of the image of ''V'' by the projection on the ''k'' first coordinates, and the subset of the image where the projection is not [[proper morphism|proper]].
* More generally Gröbner basis computations allow one to compute the Zariski closure of the image and the [[critical point (mathematics)|critical point]]s of a rational function of ''V'' into another affine variety.

Gröbner basis computations do not allow one to compute directly the [[primary decomposition]] of ''I'' nor the prime ideals defining the irreducible components of ''V'', but most algorithms for this involve Gröbner basis computation. The algorithms which are not based on Gröbner bases use [[regular chain]]s but may need Gröbner bases in some exceptional situations.

Gröbner bases are deemed to be difficult to compute. In fact they may contain, in the worst case, polynomials whose degree is doubly exponential in the number of variables and a number of polynomials which is also doubly exponential. However, this is only a worst case complexity, and the complexity bound of Lazard's algorithm of 1979 may frequently apply. [[Faugère F5 algorithm]] realizes this complexity, as it may be viewed as an improvement of Lazard's 1979 algorithm. It follows that the best implementations allow one to compute almost routinely with algebraic sets of degree more than 100. This means that, presently, the difficulty of computing a Gröbner basis is strongly related to the intrinsic difficulty of the problem.

===Cylindrical algebraic decomposition (CAD)===
CAD is an algorithm which was introduced in 1973 by G. Collins to implement with an acceptable complexity the [[Tarski–Seidenberg theorem]] on [[quantifier elimination]] over the real numbers.

This theorem concerns the formulas of the [[first-order logic]] whose [[atomic formula]]s are polynomial equalities or inequalities between polynomials with real coefficients. These formulas are thus the formulas which may be constructed from the atomic formulas by the logical operators ''and'' (∧), ''or'' (∨), ''not'' (¬), ''for all'' (∀) and ''exists'' (∃). Tarski's theorem asserts that, from such a formula, one may compute an equivalent formula without quantifier (∀, ∃).

The complexity of CAD is doubly exponential in the number of variables. This means that CAD allows, in theory, to solve every problem of real algebraic geometry which may be expressed by such a formula, that is almost every problem concerning explicitly given varieties and semi-algebraic sets.

While Gröbner basis computation has doubly exponential complexity only in rare cases, CAD has almost always this high complexity. This implies that, unless if most polynomials appearing in the input are linear, it may not solve problems with more than four variables.

Since 1973, most of the research on this subject is devoted either to improving CAD or finding alternative algorithms in special cases of general interest.

As an example of the state of art, there are efficient algorithms to find at least a point in every connected component of a semi-algebraic set, and thus to test if a semi-algebraic set is empty. On the other hand, CAD is yet, in practice, the best algorithm to count the number of connected components.

=== Asymptotic complexity vs. practical efficiency ===
The basic general algorithms of computational geometry have a double exponential worst case [[Computational complexity theory|complexity]]. More precisely, if ''d'' is the maximal degree of the input polynomials and ''n'' the number of variables, their complexity is at most <math>d^{2^{c n}}</math> for some constant ''c'', and, for some inputs, the complexity is at least <math>d^{2^{c' n}}</math> for another constant ''c''′.

During the last 20 years of the 20th century, various algorithms have been introduced to solve specific subproblems with a better complexity. Most of these algorithms have a complexity <math>d^{O(n^2)}</math>.<ref>{{Cite web |title=Complexity of Algorithms |url=https://www.cs.sfu.ca/~ggbaker/zju/math/complexity.html |access-date=2022-07-12 |website=www.cs.sfu.ca}}</ref>

Among these algorithms which solve a sub problem of the problems solved by Gröbner bases, one may cite ''testing if an affine variety is empty'' and ''solving nonhomogeneous polynomial systems which have a finite number of solutions.'' Such algorithms are rarely implemented because, on most entries [[Faugère's F4 and F5 algorithms]] have a better practical efficiency and probably a similar or better complexity (''probably'' because the evaluation of the complexity of Gröbner basis algorithms on a particular class of entries is a difficult task which has been done only in a few special cases).

The main algorithms of real algebraic geometry which solve a problem solved by CAD are related to the topology of semi-algebraic sets. One may cite ''counting the number of connected components'', ''testing if two points are in the same components'' or ''computing a [[Whitney stratification]] of a real algebraic set''. They have a complexity of
<math>d^{O(n^2)}</math>, but the constant involved by ''O'' notation is so high that using them to solve any nontrivial problem effectively solved by CAD, is impossible even if one could use all the existing computing power in the world. Therefore, these algorithms have never been implemented and this is an active research area to search for algorithms with have together a good asymptotic complexity and a good practical efficiency.