TY - GEN

T1 - Analytic root clustering

T2 - 9th Conference on Computability in Europe - The Nature of Computation: Logic, Algorithms, Applications, CiE 2013

AU - Yap, Chee

AU - Sagraloff, Michael

AU - Sharma, Vikram

PY - 2013

Y1 - 2013

N2 - A challenge to current theories of computing in the continua is the proper treatment of the zero test. Such tests are critical for extracting geometric information. Zero tests are expensive and may be uncomputable. So we seek geometric algorithms based on a weak form of such tests, called soft zero tests. Typically, algorithms with such tests can only determine the geometry for "nice" (e.g., non-degenerate, non-singular, smooth, Morse, etc) inputs. Algorithms that avoid such niceness assumptions are said to be complete. Can we design complete algorithms with soft zero tests? We address the basic problem of determining the geometry of the roots of a complex analytic function f. We assume effective box functions for f and its higher derivatives are provided. The problem is formalized as the root clustering problem, and we provide a complete (δ,∈)-exact algorithm based on soft zero tests.

AB - A challenge to current theories of computing in the continua is the proper treatment of the zero test. Such tests are critical for extracting geometric information. Zero tests are expensive and may be uncomputable. So we seek geometric algorithms based on a weak form of such tests, called soft zero tests. Typically, algorithms with such tests can only determine the geometry for "nice" (e.g., non-degenerate, non-singular, smooth, Morse, etc) inputs. Algorithms that avoid such niceness assumptions are said to be complete. Can we design complete algorithms with soft zero tests? We address the basic problem of determining the geometry of the roots of a complex analytic function f. We assume effective box functions for f and its higher derivatives are provided. The problem is formalized as the root clustering problem, and we provide a complete (δ,∈)-exact algorithm based on soft zero tests.

UR - http://www.scopus.com/inward/record.url?scp=84880397975&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880397975&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39053-1_51

DO - 10.1007/978-3-642-39053-1_51

M3 - Conference contribution

AN - SCOPUS:84880397975

SN - 9783642390524

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 434

EP - 444

BT - The Nature of Computation

Y2 - 1 July 2013 through 5 July 2013

ER -