A geometric algorithm for winding number computation with complexity analysis
type: Item
instance of: scholarly article
title: A geometric algorithm for winding number computation with complexity analysis
zbMATH Open document ID: 1262.65057
author: Juan Carlos Díaz Martín
author: Juan-Luis García Zapata
published in: Journal of Complexity
publication date: 2012-05-30T00:00:00Z
review text: Winding number computation is used in several root-finding algorithms. Many methods to compute the winding number of plane curves have been proposed, often with the aim of counting the number of roots of polynomials (or, more generally, zeros of analytic functions) inside some region by using the principle of argument. In this paper, the authors propose another method, which is not based on numerical integration, but on discrete geometry using discretization of the curve to obtain an array to which the method of twist counting of Henrici can be reliably applied. They give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, they provide a modification of the algorithm that detects the proximity to a singular case of the curve. If this proximity is such that the number of operations required grows over certain threshold, set by the user, the modified algorithm returns without winding number computation, but with information about the distance to singular case. When the method is applied to polynomials, this information refers to the localization of the roots placed near the curve.
reviewed by: Jinrong Jiang
Mathematics Subject Classification ID: 65H05
Mathematics Subject Classification ID: 65E05
Mathematics Subject Classification ID: 65H04
Mathematics Subject Classification ID: 30C15
zbMATH DE Number: 6039456
zbMATH Keywords: complex analysis
zbMATH Keywords: winding number
zbMATH Keywords: contour integration
zbMATH Keywords: discrete geometry
zbMATH Keywords: complexity bound
zbMATH Keywords: root-finding algorithm
zbMATH Keywords: roots of polynomials
zbMATH Keywords: zeros of analytic functions
zbMATH Keywords: method of twist counting of Henrici
MaRDI profile type: Publication
full work available at URL: j.jco.2012.02.001
OpenAlex ID: W2090705063
cites work: Q4387224
cites work: Q4314299
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: Computational Complexity of Two-Dimensional Regions
cites work: Q4194438
cites work: On condition numbers and the distance to the nearest ill-posed problem
cites work: Q4039888
cites work: Q3935355
cites work: Q5614773
cites work: A reliable algorithm for computing the topological degree of a mapping in \(\mathbb R^{2}\)
cites work: A derivative-free algorithm for computing zeros of analytic functions
cites work: Solving a Polynomial Equation: Some History and Recent Progress
cites work: On the worst-case arithmetic complexity of approximating zeros of polynomials
cites work: A globally convergent zero finding method.
cites work: A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
cites work: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
cites work: A reliable argument principle algorithm to find the number of zeros of an analytic function in a bounded domain
DOI: 10.1016/J.JCO.2012.02.001
description: scientific article; zbMATH DE number 6039456