کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9501318 | 1338406 | 2005 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On solving univariate sparse polynomials in logarithmic time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
آنالیز ریاضی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m=3 we can approximate within ε all the roots of f in the interval [0,R] using just O(log(D)log(DlogRε)) arithmetic operations. In particular, we can count the number of roots in any bounded interval using just O(log2D) arithmetic operations. Our speed-ups are significant and near-optimal: The asymptotically sharpest previous complexity upper bounds for both problems were super-linear in D, while our algorithm has complexity close to the respective complexity lower bounds. We also discuss conditions under which our algorithms can be extended to general m, and a connection to a real analogue of Smale's 17th Problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 21, Issue 1, February 2005, Pages 87-110
Journal: Journal of Complexity - Volume 21, Issue 1, February 2005, Pages 87-110
نویسندگان
J.Maurice Rojas, Yinyu Ye,