Name
Abstract | ||
|---|---|---|
Given a polynomial p(z) of degree n with m bit integer coefficients and an integer /z, the problem of determining all its roots with error less than 2 -~ is considered. It is shown that this problem is in the class NC if p (z) has all real roots. Some very interesting properties of a Sturm sequence of a polynomial with distinct real roots are proved and used in the design of a fast parallel algorithm for this problem. Using Newton identities and a novel numerical integration scheme for evaluating a con- tour integral to high precision, this algorithm deter- mines good approximations to the linear factors of |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1137/0217069 | SIAM J. Comput. |
Keywords | DocType | Volume |
fast parallel algorithm,real root,parallel algorithm,newton method,iteration method,numerical integration,contour integration,polynomial,parallel algorithms | Journal | 17 |
Issue | ISSN | ISBN |
6 | 0097-5397 | 0-89791-193-8 |
Citations | PageRank | References |
28 | 3.07 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Ben-Or | 1 | 2008 | 420.97 |
| Ephraim Feig | 2 | 126 | 19.36 |
| Dexter C. Kozen | 3 | 5108 | 912.56 |
| Prasoon Tiwari | 4 | 592 | 96.81 |