Hermite form computation of matrices of differential polynomials

Symbolic Computation;Differential Algebra;Computer Science

Kim, Myung Sub

University of Waterloo

关键词: Symbolic Computation;    Differential Algebra;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4626/1/Kim_MyungSub.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Given a matrix A in F(t)[D;delta]^{nimes n} over the ring of differential polynomials, we first prove the existence of the Hermite form H of A over this ring. Then we determine degree bounds on U and H such that UA=H. Finally, based on the degree bounds on U and H, we compute the Hermite form H of A by reducing the problem to solving a linear system of equations over F(t). The algorithm requires a polynomial number of operations in F in terms of the input sizes: n, deg_{D} A, and deg_{t} A.When F=Q it requires time polynomial in the bit-length of the rational coefficients as well.