Loading...
Please wait, while we are loading the content...
Similar Documents
Fast parallel algorithms for polynomial division over an arbitrary field of constants
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bini, Dario Pan, Victor Y. |
| Copyright Year | 1986 |
| Abstract | Abstract It is shown that the division of an m th-degree polynomial by an n th-degree polynomial can be performed over an arbitrary field of constants F involving O (log( m − n +1)loglog( m − n +1)) parallel steps and a polynomial in m number of processors. If the field F has more than 2+2( m − n +1)min{ n , m − n } distinct elements, then O (log( m − n +1)) parallel steps and the polynomial number of processors suffice. The values of the constants for these asymptotic bounds are also presented. The number of parallel steps can be reduced to O (log( m − n +1)) over an arbitrary field using polynomial circuits for the operations in the extended field of constants. These methods can be extended to the design of parallel algorithms of the same asymptotic complexity for the inversion of circulant matrices, even where the field of constants does not support FFT. The latter result does not follow from the recent methods by the authors and Eberly, which otherwise lead to similar results by different means. |
| File Format | PDF HTM / HTML |
| DOI | 10.1016/0898-1221(86)90015-5 |
| Alternate Webpage(s) | http://comet.lehman.cuny.edu/vpan/pdf/pan53.pdf |
| Alternate Webpage(s) | https://www.researchgate.net/profile/Dario_Bini/publication/250727103_Fast_parallel_algorithms_for_polynomial_division_over_an_arbitrary_field_of_constants/links/53f1ad9d0cf23733e815c755.pdf |
| Alternate Webpage(s) | https://doi.org/10.1016/0898-1221%2886%2990015-5 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
