A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time

Pierre Lairez

doi:10.1007/s10208-016-9319-7

A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time

Pierre Lairez

TU Berlin

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

28 Citations (Scopus)

Résumé

We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum–Shub–Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.

langue originale	Anglais
Pages (de - à)	1265-1292
Nombre de pages	28
journal	Foundations of Computational Mathematics
Volume	17
Numéro de publication	5
Les DOIs	https://doi.org/10.1007/s10208-016-9319-7
état	Publié - 1 oct. 2017
Modification externe	Oui

Accès au document

10.1007/s10208-016-9319-7

Contient cette citation

@article{40b58dcf5fa641ada617318215d4f95c,

title = "A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time",

abstract = "We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum{\textendash}Shub{\textendash}Smale model with square root. It rests upon a derandomization of an algorithm of Beltr{\'a}n and Pardo and gives a deterministic affirmative answer to Smale{\textquoteright}s 17th problem. The main idea is to make use of the randomness contained in the input itself.",

keywords = "Complexity, Derandomization, Homotopy continuation, Polynomial system, Smale{\textquoteright}s 17th problem",

author = "Pierre Lairez",

note = "Publisher Copyright: {\textcopyright} 2016, SFoCM.",

year = "2017",

month = oct,

day = "1",

doi = "10.1007/s10208-016-9319-7",

language = "English",

volume = "17",

pages = "1265--1292",

journal = "Foundations of Computational Mathematics",

issn = "1615-3375",

publisher = "Springer New York",

number = "5",

}

TY - JOUR

T1 - A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time

AU - Lairez, Pierre

PY - 2017/10/1

Y1 - 2017/10/1

N2 - We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum–Shub–Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.

AB - We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum–Shub–Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.

KW - Complexity

KW - Derandomization

KW - Homotopy continuation

KW - Polynomial system

KW - Smale’s 17th problem

U2 - 10.1007/s10208-016-9319-7

DO - 10.1007/s10208-016-9319-7

M3 - Article

AN - SCOPUS:84969820390

SN - 1615-3375

VL - 17

SP - 1265

EP - 1292

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

IS - 5

ER -

A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time

Résumé

Accès au document

Empreinte digitale

Contient cette citation