Vi anser att problemet med att hitta exakta summor av kvadrater (SOS) nedbrytningar för vissa klasser av icke-negativa multivariat polynomials, förlitar sig på semidefinite programmering (SDP) lösare. Vi börjar med att tillhandahålla en hybrid numerisk-symbolisk algoritm beräkning exakt rationell SOS nedbrytningar för polynom ligger i det inre av SOS konen. Den beräknar en ungefärlig SOS nedbrytning för en perturbering av ingångspolynom med en godtycklig-precision SDP lösare. En exakt SOS nedbrytning erhålls tack vare perturbation termer. Vi bevisar att bit komplexitet uppskattningar på produktionsstorlek och körtid är både polynom i graden av inmatning polynom och helt enkelt exponentiellt i antalet variabler. Därefter tillämpar vi denna algoritm för att beräkna exakta Polya och Putinar's representationer respektive för positiva bestämda former och positiva polynomials över grundläggande kompakta semi-algebraic uppsättningar. Vi jämför också implementeringen av våra algoritmer med befintliga metoder i datoralgebra inklusive cylindrisk algebraisk nedbrytning och kritisk punktmetod.
Detta perturbation/kompensationssystem är huvudingrediensen i den hybrida numeriska-symboliska algoritmen från REF, utformad för att beräkna exakt rationella SOS nedbrytningar för polynom ligger i det inre av SOS konen.
On Exact Polya and Putinar's Representations
{'venue': "ISSAC '18", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}