ub.xmlui.mirage2.page-structure.muninLogoub.xmlui.mirage2.page-structure.openResearchArchiveLogo
    • EnglishEnglish
    • norsknorsk
  • Velg spraaknorsk 
    • EnglishEnglish
    • norsknorsk
  • Administrasjon/UB
Vis innførsel 
  •   Hjem
  • Fakultet for naturvitenskap og teknologi
  • Institutt for matematikk og statistikk
  • Artikler, rapporter og annet (matematikk og statistikk)
  • Vis innførsel
  •   Hjem
  • Fakultet for naturvitenskap og teknologi
  • Institutt for matematikk og statistikk
  • Artikler, rapporter og annet (matematikk og statistikk)
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

Real Root Finding for Equivariant Semi-algebraic Systems

Permanent lenke
https://hdl.handle.net/10037/30805
Thumbnail
Åpne
article.pdf (429.2Kb)
(PDF)
Dato
2018
Type
Conference object
Konferansebidrag

Forfatter
Riener, Cordian; Safey el Din, Mohab
Sammendrag
Let R be a real closed field. We consider basic semi-algebraic sets defined by n-variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2d < n. Such a semi-algebraic set is invariant by the action of the symmetric group. We show that such a set is either empty or it contains a point with at most 2d−1 distinct coordinates. Combining this geometric result with efficient algorithms for real root finding (based on the critical point method), one can decide the emptiness of basic semi-algebraic sets defined by s polynomials of degree d in time (sn)O(d). This improves the state-of-the-art which is exponential in n. When the variables x1, ..., xn are quantified and the coefficients of the input system depend on parameters y1, ..., yt, one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time (sn)O(d).
Metadata
Vis full innførsel
Samlinger
  • Artikler, rapporter og annet (matematikk og statistikk) [357]

Bla

Bla i hele MuninEnheter og samlingerForfatterlisteTittelDatoBla i denne samlingenForfatterlisteTittelDato
Logg inn

Statistikk

Antall visninger
UiT

Munin bygger på DSpace

UiT Norges Arktiske Universitet
Universitetsbiblioteket
uit.no/ub - munin@ub.uit.no

Tilgjengelighetserklæring