|
|
|
| An Improved Algorithm for Real Root Isolation of Univariate Polynomials |
| LIU Dong1，FENG Yong1，ZHANG Caihuan2，ZHAO Xianghui1 |
(1.Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu 610041, China；
2.Department of Mathematics, Luoyang Normal University, Luoyang 471022, Henan，China) |
|
|
|
|
Abstract An improved algorithm for real root isolation of univariate polynomials was proposed mainly based on bisection method and a kind of specially designed efficient interval Newton operator. Its structure is similar to Trealroot, a function in Maple package Discoverer, however, it is more efficient than Trealroot for sparse polynomials with large degrees and few terms. Generally speaking, performing Taylor shift is very costly, so Trealroot uses many techniques to decrease the number of Taylor shifts. Different from Trealroot, the proposed algorithm performs a specially designed efficient exact interval Newton operator to rule out intervals not containing real zeros quickly and avoids completely Taylor shifts. The algorithm is super efficient for sparse polynomials. The polynomial is sparser, and the algorithm is more efficient. A large number of polynomials generated randomly by Maple were tested, compared with Trealroot and realroot (a function in Maple), and the result was reported.
|
|
Received: 18 January 2010
Published: 30 November 2010
|
|
|
|
|
|
| [1] |
DONG Zhen-Hua-a, b , DONG Xiao-Ju-a, b . Representing Bounded Petri Nets by Process Calculi[J]. J. Shanghai Jiaotong Univ.(Sci.) , 2011, 45(07): 980-984. |
| [2] |
MAI Jiaji,CHEN Feng
. Uncertain Milk RunBased Cross Docking Scheduling:Model and Algorithms
[J]. J. Shanghai Jiaotong Univ.(Sci.) , 2011, 45(02): 159-0163. |
| [3] |
BAI Jie1,YANG Genke1,PAN Changchun1,SUN Kai2
. A Revised Scatter Search Algorithm for Path Planning of Multiple UAVs
[J]. J. Shanghai Jiaotong Univ.(Sci.) , 2011, 45(02): 173-0178. |
| [4] |
JIANG Guishana,JIANG Zhibinb,LIU Shujunb
. Improved Guided Local Searchbased Algorithm for Period Vehicle Routing Problem
[J]. J. Shanghai Jiaotong Univ.(Sci.) , 2010, 44(09): 1171-1175. |
|
|
|
|
