Computing Matrix Canonical Forms of Ore Polynomials

Computer Algebra;Symbolic Computation;Linear Algebra;Popov Form;Hermite Form;Fast Algorithms

Khochtali, Mohamed

University of Waterloo

关键词: Computer Algebra;    Symbolic Computation;    Linear Algebra;    Popov Form;    Hermite Form;    Fast Algorithms;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/11831/3/Khochtali_Mohamed.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We present algorithms to compute canonical forms of matrices of Ore polynomials while controlling intermediate expression swell. Given a square non-singular input matrix of Ore polynomials, we give an extension of the algorithm by Labhalla et al. 1992, to compute the Hermite form. We also give a new fraction-free algorithm to compute the Popov form, accompanied by an implementation and experimental results that compare it to the best known algorithms in the literature. Ouralgorithm is output-sensitive, with a cost that depends on the orthogonality defect of the input matrix: the sum of the row degrees in the input matrix minus the sum of the row degrees in the Popov form. We also use the recent advances in polynomial matrix computations, including fast inversion and rank profile computation, to describe an algorithm that computes the transformation matrixcorresponding to the Popov form.