## 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 language | English |
---|---|

Title of host publication | ISSAC 2017 - Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation |

Number of pages | 8 |

Volume | Part F129312 |

Publisher | Association for Computing Machinery |

Publication date | 2017 |

Pages | 253-260 |

ISBN (Electronic) | 9781450350648 |

DOIs | |

Publication status | Published - 2017 |

Event | 42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017 - University of Kaiserslautern, Kaiserslautern, Germany Duration: 25 Jul 2017 → 28 Jul 2017 Conference number: 42 |

### Conference

Conference | 42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017 |
---|---|

Number | 42 |

Location | University of Kaiserslautern |

Country | Germany |

City | Kaiserslautern |

Period | 25/07/2017 → 28/07/2017 |

Sponsor | Association for Computing Machinery |