检索结果-内蒙古大学图书馆

Approximating complex polynomial zeros: Modified Weyl's quadtree construction and improved Newton's iteration

JOURNAL OF complexITY 2000年第1期16卷 213-264页

作者： Pan, VY CUNY Herbert H Lehman Coll Dept Math & Comp Sci Bronx NY 10468 USA

We propose a new algorithm fur the classical and still practically important problem of approximating zeros zi of an nth degree polynomial p(x) within error bound 2(-b) max(j) [z(j)]. The algorithm uses O((n(2) log n) log(bn)) arithmetic operations and comparisons for approximating all the n zeros and O((kn log n) log(bn)) for approximating the it zeros lying in a fixed domain (disc or square) and isolated from the other zeros. Unlike the previous fast algorithms of this kind, the new algorithm has its simple elementary description, is convenient for practical implementation, and allows the users to adapt the computational precision to the current level of approximation achieved in the process of computing and ultimately to the requirements to the output precision for each zero of p(x). The algorithm relies on our novel versions of Weyl's qundtree construction and Newton's iteration. (C) 2000 Academic Press.

关键词： complex polynomial zeros algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

Optimal and nearly optimal algorithms for approximating polynomial zeros

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1996年第12期31卷 97-138页

作者： Pan, VY Department of Mathematics and Computer Science Lehman College City University of New York Bronx NY 10468 U.S.A.

We substantially improve the known algorithms for approximating all the complex zeros of an n(th) degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schonhage [1], Pan [2], and Neff and Pelf [3]. In parallel (NC) implementation, we dramatically decrease the number of processors, versus the parallel algorithm of Neff [4], which was the only NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable a: has been scaled so as to confine the zeros of p(x) to the unit disc {x : \x\ less than or equal to 1}, our algorithms (which promise to be practically effective) approximate all the zeros of p(a) within the absolute error bound 2(-b), by using order of n arithmetic operations and order of (b + n)n(2) Boolean (bitwise) operations (in both cases up to within polylogarithmic factors). The algorithms allow their optimal (work preserving) NC parallelization, so that they can be implemented by using polylogarithmic time and the orders of n arithmetic processors or (b + n)n(2) Boolean processors. All the cited bounds on the computational complexity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in the Boolean case, under the additional (realistic) assumption that n = O(b)).

关键词： complex polynomial zeros approximation polynomial factorization parallel algorithms computational complexity sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving a polynomial equation: Some history and recent progress

引用

SIAM REVIEW 1997年第2期39卷 187-220页

作者： Pan, VY Dept. of Math. and Computer Science Lehman College City University of New York Bronx NY 10468 United States

The classical problem of solving an nth degree polynomial equation has substantially influenced the development of mathematics throughout the centuries and still has several important applications to the theory and practice of present-day computing. We briefly recall the history of the algorithmic approach to this problem and then review some successful solution algorithms. We end by outlining some algorithms of 1995 that solve this problem at a surprisingly low computational cost.

关键词： polynomial equation fundamental theorem of algebra complex polynomial zeros numerical approximation computer algebra Weyl's quadtree algorithm divide-and-conquer algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：