Putting Newton into Practice: A Solver for Polynomial Equations over Semirings

Autor:	Michał Terepeta, Michael Luttenberger, Maximilian Schlund
Rok vydání:	2013
Předmět:	Algebra Polynomial Computer science Computation Kleene star Ascending chain condition Solver System of linear equations Algorithm computer Semiring Datalog computer.programming_language
Zdroj:	Logic for Programming, Artificial Intelligence, and Reasoning ISBN: 9783642452208 LPAR
DOI:	10.1007/978-3-642-45221-5_48
Popis:	We present the first implementation of Newton’s method for solving systems of equations over ω-continuous semirings (based on [5,11]). For instance, such equation systems arise naturally in the analysis of interprocedural programs or the provenance computation for Datalog. Our implementation provides an attractive alternative for computing their exact least solution in some cases where the ascending chain condition is not met and hence, standard fixed-point iteration needs to be combined with some over-approximation (e.g., widening techniques) to terminate. We present a generic C++ library along with the main algorithms and analyze their complexity. Furthermore, we describe our implementation of the counting semiring based on semilinear sets. Finally, we discuss motivating examples as well as performance benchmarks.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::84d62e4de79440a32579c23646261072 https://doi.org/10.1007/978-3-642-45221-5_48 Zobrazit plný text záznamu