Software Engineering and Complexity in Effective Algebraic Geometry
arXiv:1110.3030
Abstract
We introduce the notion of a robust parameterized arithmetic circuit for the evaluation of algebraic families of multivariate polynomials. Based on this notion, we present a computation model, adapted to Scientific Computing, which captures all known branching parsimonious symbolic algorithms in effective Algebraic Geometry. We justify this model by arguments from Software Engineering. Finally we exhibit a class of simple elimination problems of effective Algebraic Geometry which require exponential time to be solved by branching parsimonious algorithms of our computation model.
70 pages. arXiv admin note: substantial text overlap with arXiv:1201.4344