Estimation of the Greatest Common Divisor of many polynomials using hybrid computations performed by the ERES method
✍ Scribed by Dimitrios Christou; Marilena Mitrouli
- Publisher
- John Wiley and Sons
- Year
- 2005
- Weight
- 146 KB
- Volume
- 2
- Category
- Article
- ISSN
- 1611-8170
No coin nor oath required. For personal study only.
✦ Synopsis
The computation of the Greatest Common Divisor (GCD) of a set of more than two polynomials is a non-generic problem. There are cases where iterative methods of computing the GCD of many polynomials, based on the Euclidean algorithm, fail to produce accurate results, when they are implemented in a software programming environment. This phenomenon is very strong especially when floating-point data are being used. The ERES method is an iterative matrix based method, which successfully evaluates an approximate GCD, by performing row transformations and shifting on a matrix, formed directly from the coefficients of the given polynomials. ERES deals with any kind of real data. However, due to its iterative nature, it is extremely sensitive when performing floating-point operations. It succeeds in producing results with minimal error, if we combine both floating-point and symbolic operations. In the present paper we study the behavior of the ERES method using floating-point and exact symbolic arithmetic. The conclusions derived from our study are useful for any other algorithm involving extended matrix operations.