Kronecker's and Newton's Approaches to Solving: A First Comparison

These pages are a first attempt to compare the efficiency of symbolic and numerical analysis procedures that solve systems of multivariate polynomial equations. In particular, we compare Kronecker's solution (from the symbolic approach) with approximate zero theory (introduced by S. Smale as a...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2001-03, Vol.17 (1), p.212-303
Main Authors: Castro, D., Pardo, L.M., Hägele, K., Morais, J.E.
Format: Article
Language:English
Subjects:
approximate zero
degree of algebraic varieties
height of diophantine varieties
Kronecker's solution
Newton operator
straight-line programs
Turing machine complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:These pages are a first attempt to compare the efficiency of symbolic and numerical analysis procedures that solve systems of multivariate polynomial equations. In particular, we compare Kronecker's solution (from the symbolic approach) with approximate zero theory (introduced by S. Smale as a foundation of numerical analysis). For this purpose we show upper and lower bounds of the bit length of approximate zeros. We also introduce efficient procedures that transform local Kronecker solutions into approximate zeros and conversely. As an application of our study we exhibit an efficient procedure to compute splitting field and Lagrange resolvent of univariate polynomial equations. We remark that this procedure is obtained by a convenient combination of both approaches (numeric and symbolic) to multivariate polynomial solving.
ISSN:0885-064X
1090-2708
DOI:10.1006/jcom.2000.0572