The Power of Polynomials: Work in Progress

Paul Feautrier 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Every component in the program development chain uses a model to represent and reason about its source. The model must be as expressive as possible without compromising its efficiency and tractability. This paper proposes a slight extension to the polyhedral model by allowing polynomial constraints and relations. Recent mathematical results by Handelman and Schweighofer on the Positivstellensatz allow one to devise algorithms similar to familiar emptiness tests or the Farkas algorithm. This paper presents applications of these ideas to three use-cases: dependence tests, scheduling and transitive closure approximation. It then points to unsolved problems and future work.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01094787
Contributor : Paul Feautrier <>
Submitted on : Saturday, December 13, 2014 - 11:46:58 AM
Last modification on : Thursday, November 21, 2019 - 2:07:40 AM
Long-term archiving on: Saturday, March 14, 2015 - 10:16:10 AM

Files

powerPol-v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01094787, version 1

Collections

Citation

Paul Feautrier. The Power of Polynomials: Work in Progress. 5th International Workshop on Polyhedral Compilation Techniques (IMPACT'15), Jan 2015, Amsterdam, Netherlands. ⟨hal-01094787⟩

Share

Metrics

Record views

332

Files downloads

353