Popov form computation for matrices of Ore polynomials

Mohamed Khochtali, Johan Rosenkilde Né Nielsen, Arne Storjohann

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

269 Downloads (Pure)

Abstract

Let F[∂; s, d] be a ring of Ore polynomials over a field. We give a new deterministic algorithm for computing the Popov form P of a non-singular matrix A ∈ F[∂; s, d]n×n. Our main focus is to ensure controlled growth in the size of coefficients from F in the case F = k(z), and even k = Q. Our algorithms are based on constructing from A a linear system over F and performing a structured fraction-free Gaussian elimination. The algorithm is output sensitive, with a cost that depends on the orthogonality defect of the input matrix: the sum of the row degrees in A minus the sum of the row degrees in P. The resulting bit-complexity for the differential and shift polynomial case over ℚ(z) improves upon the previous best.

Original languageEnglish
Title of host publicationISSAC 2017 - Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation
Number of pages8
VolumePart F129312
PublisherAssociation for Computing Machinery
Publication date2017
Pages253-260
ISBN (Electronic)9781450350648
DOIs
Publication statusPublished - 2017
Event42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017 - University of Kaiserslautern, Kaiserslautern, Germany
Duration: 25 Jul 201728 Jul 2017
Conference number: 42

Conference

Conference42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017
Number42
LocationUniversity of Kaiserslautern
CountryGermany
CityKaiserslautern
Period25/07/201728/07/2017
SponsorAssociation for Computing Machinery

Fingerprint Dive into the research topics of 'Popov form computation for matrices of Ore polynomials'. Together they form a unique fingerprint.

Cite this