Computing Approximate GCRDs of Differential Polynomials

Ore;Differential;Operator;Approximate;GCD;GCRD;Computer Science

Haraldson, Joseph

University of Waterloo

关键词: Ore;    Differential;    Operator;    Approximate;    GCD;    GCRD;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/9685/3/haraldson_joseph.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We generalize the approximate greatest common divisor problem to the non-commutative, approximate Greatest Common Right Divisor (GCRD) problem of differential polynomials.Algorithms for performing arithmetic on approximate differential polynomials are presented along with certification results and the corresponding number of flops required. Under reasonable assumptions the approximate GCRD problem is well posed. In particular, we show that an approximate GCRDexists under these assumptions and provide counter examples when these assumptions are not satisfied. We introduce algorithms for computing nearby differential polynomials with a GCRD. These differential polynomials are improved through a post-refinement Newton iteration.It is shown that Newton iteration will converge to a unique, optimal solution when the residual is sufficiently small. Furthermore, if our computed solution is not optimal, it is shown that this solution is reasonably close to the optimal solution.