Software engineering and complexity in effective algebraic geometry (Q1931431)

The article is, in my opinion, best described by a collection of sentences in it: From the abstract: ``We present a circuit based computation model which captures all known symbolic elimination algorithms in effective algebraic geometry and exhibit a class of simple elimination problems which require exponential size circuits to be solved in this model. This implies that the known, circuit based elimination algorithms are already optimal.'' From the corpus of the article: ''We introduce and motivate a new computation model which is well-adapted to scientific computing in effective algebraic geometry and especially to elimination theory. This model is based on the symbolic manipulation of arithmetic circuits which evaluate rational functions.'' ''In Section 4 we use our computation model to show that already very elementary elimination problems require exponential time for their solution (see Theorem 10, Proposition 11 and Theorem 12).'' ''In particular, we exhibit in Section 4.3 a family of parameterized Boolean circuits whose (standard) arithmetizations represent an elimination problem which requires exponential time to be solved in our model (see Theorem 13).'' ''As a major outcome of this paper we exhibit in Section 4.5 an infinite family of parameter dependent elimination polynomials which require essentially division-free, robust parameterized arithmetic circuits of exponential size for their evaluation, whereas the circuit size of the corresponding input problems grows only polynomially. We observe that essentially division-free, robust parameterized arithmetic circuits for elimination polynomials capture the intuitive meaning of an algorithmic solution with few equations and branchings of the underlying elimination problem.'' ''Our computation model and complexity results are based on the concept of a geometrically robust constructible map. This concept was introduced in [\textit{N. Giménez} et al., J. Complexity 27, No. 2, 151--187 (2011; Zbl 1277.65008)] and we develop it further in Section 2, which is devoted to the algebraic geometric underpinning of the present paper.'' ''The final outcome of our considerations in Sections 4.1 and 4.7 is the following: neither mathematicians nor software engineers, nor a combination of them will ever produce a practically satisfactory, generalistic software for elimination tasks in algebraic geometry. This is a job for hackers which may find for particular elimination problems specific efficient solutions.''