Computing curve intersection by means of simultaneous iterations
type: Item
instance of: scholarly article
title: Computing curve intersection by means of simultaneous iterations
zbMATH Open document ID: 1111.65019
author: Ana Marco
author: Dario A. Bini
published in: Numerical Algorithms
publication date: 2007-01-30T00:00:00Z
review text: A new algorithm is proposed for computing the intersection of two plane curves given in rational parametric form [the general solution steps are described by \textit{J. Hoschek} and \textit{D. Lasser}, Fundamentals of computer aided geometric design (1993; Zbl 0788.68002)]. This approach avoids symbolic manipulations and is completely numerical. It relies on the Ehrlich-Aberth iteration complemented with some computational tools like the properties of Sylvester and Bézout matrices, a stopping criterion based on the concept of pseudo-zero, an inclusion result and the choice of initial approximations based on the Newton polygon. The algorithm is implemented as a Fortran 95 module. From the numerical experiments performed with a wide set of test problems it shows a better robustness and stability with respect to the Manocha-Demmel approach based on eigenvalue computation. In fact, the algorithm provides better approximations in terms of the relative error and performs successfully in many critical cases where the eigenvalue computation fails.
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 5119759
zbMATH Keywords: curve intersection
zbMATH Keywords: structured matrices
zbMATH Keywords: numerical algorithms
zbMATH Keywords: Sylvester resultant
zbMATH Keywords: Ehrlich-Aberth iteration
zbMATH Keywords: Sylvester and Bézout matrices
zbMATH Keywords: Newton polygon
zbMATH Keywords: numerical experiments
reviewed by: Vladimir Yu. Rovenskij
describes a project that uses: na10
describes a project that uses: mctoolbox
describes a project that uses: na20
MaRDI profile type: Publication
full work available at URL: s11075-006-9048-0
OpenAlex ID: W2064384667
cites work: Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
cites work: Numerical computation of polynomial zeros by means of Aberth's method
cites work: Design, analysis, and implementation of a multiprecision polynomial rootfinder
cites work: Bernstein-Bézoutian matrices
cites work: The Ehrlich--Aberth Method for the Nonsymmetric Tridiagonal Eigenvalue Problem
cites work: Q4314299
cites work: An application of fast factorization algorithms in computer aided geometric design
cites work: Fast computation of determinants of Bézout matrices and application to curve implicitization
cites work: Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
cites work: Vector elimination: A technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves
cites work: Initial approximations in Durand-Kerner's root finding method
cites work: Q4072022
cites work: Accuracy and Stability of Numerical Algorithms
cites work: Q4278198
cites work: Q3222981
cites work: Algorithms for intersecting parametric and algebraic curves I
cites work: Using polynomial interpolation for implicitizing algebraic curves
cites work: Root Neighborhoods of a Polynomial
cites work: Improperly parametrized rational curves
DOI: 10.1007/S11075-006-9048-0
Recommended article: Computing curve intersection by homotopy methods
Recommended article: Q3134267
Recommended article: Computing the Geometric Intersection Number of Curves
Recommended article: A unified algorithm for finding the intersection curve of surfaces
Recommended article: Intersection points of planar curves can be computed
Recommended article: Algorithm for algebraic curve intersection
Recommended article: Computing the convex hull of line intersections
Recommended article: Computer Algebra in Scientific Computing
Recommended article: Computing intersections between non-compatible curves and finite elements
description: scientific article; zbMATH DE number 5119759