Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleA concise proof of the Kronecker polynomial system solver from scratch
Author(s) Clémence Durvye, Gregoire Lecerf
TypeArticle in Journal
AbstractNowadays polynomial system solvers are involved in sophisticated computations in algebraic geometry as well as in practical engineering. The most popular algorithms are based on Gröbner bases, resultants, Macaulay matrices, or triangular decompositions. In all these algorithms, multivariate polynomials are expanded in a monomial basis, and the computations mainly reduce to linear algebra. The major drawback of these techniques is the exponential explosion of the size of the polynomials needed to represent highly positive dimensional solution sets. Alternatively, the “Kronecker solver” uses data structures to represent the input polynomials as the functions that compute their values at any given point. In this paper, we present the first self-contained and student friendly version of the Kronecker solver, with a substantially simplified proof of correctness. In addition, we enhance the solver in order to compute the multiplicities of the zeros without any extra cost.
KeywordsPolynomial system solving, Elimination theory, Algorithm, Complexity
ISSN0723-0869
URL http://www.sciencedirect.com/science/article/pii/S072308690700045X
LanguageEnglish
JournalExpositiones Mathematicae
Volume26
Number2
Pages101 - 139
Year2008
Edition0
Translation No
Refereed No
Webmaster