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

Research output: Contribution to journal › Article › peer-review

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–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.

Original language	English
Pages (from-to)	1265-1292
Number of pages	28
Journal	Foundations of Computational Mathematics
Volume	17
Issue number	5
DOIs	https://doi.org/10.1007/s10208-016-9319-7
Publication status	Published - 1 Oct 2017
Externally published	Yes

Keywords

Complexity
Derandomization
Homotopy continuation
Polynomial system
Smale’s 17th problem

Access to Document

10.1007/s10208-016-9319-7

Cite this

@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–Shub–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",

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this