MODULAR COMPUTATION FOR MATRICES OF ORE POLYNOMIALS

Abstract

Computer Algebra 2006, pp. 43-66 (2007) No AccessMODULAR COMPUTATION FOR MATRICES OF ORE POLYNOMIALSHOWARD CHENG and GEORGE LABAHNHOWARD CHENGDepartment of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Canada and GEORGE LABAHNDavid R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canadahttps://doi.org/10.1142/9789812778857_0004Cited by:5 PreviousNext AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail Abstract: We give a modular algorithm to perform row reduction of a matrix of Ore polynomials with coefficients in ℤ[t]. Both the transformation matrix and the transformed matrix are computed. The algorithm can be used for finding the rank and left nullspace of such matrices. In the special case of shift polynomials, we obtain algorithms for computing a weak Popov form and for computing a greatest common right divisor (GCRD) and a least common left multiple (LCLM) of matrices of shift polynomials. Our algorithms improve on existing fraction-free algorithms and can be viewed as generalizations of the work of Li and Nemes on GCRDs and LCLMs of Ore polynomials. We define lucky homomorphisms, determine the appropriate normalization, as well as bound the number of homomorphic images required. Our algorithm is output-sensitive, such that the number of homomorphic images required depends on the size of the output. Furthermore, there is no need to verify the result by trial division or multiplication. When our algorithm is used to compute a GCRD and a LCLM of shift polynomials, we obtain a new output-sensitive modular algorithm. FiguresReferencesRelatedDetailsCited By 5Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrixGeorge Labahn, Vincent Neiger and Wei Zhou1 Oct 2017 | Journal of Complexity, Vol. 42A Practical Implementation of a Modular Algorithm for Ore Polynomial MatricesHoward Cheng and George Labahn1 October 2014Computing diagonal form and Jacobson normal form of a matrix using Gröbner basesViktor Levandovskyy and Kristina Schindelar1 May 2011 | Journal of Symbolic Computation, Vol. 46, No. 5Applying linear algebra routines to modular ore polynomial matrix algorithmsHoward Cheng and George Labahn24 Jun 2010 | ACM Communications in Computer Algebra, Vol. 43, No. 3/4ISSAC 2007 poster abstractsMark W. Giesbrecht, Ilias Kotsireas and Austin Lobo1 Mar 2007 | ACM Communications in Computer Algebra, Vol. 41, No. 1-2 Computer Algebra 2006Metrics History PDF download

Locations

• CiteSeer X (The Pennsylvania State University) - View - PDF