Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants
| Autor: | Seung Gyu Hyun, Vincent Neiger, Éric Schost |
|---|---|
| Přispěvatelé: | Cheriton School of Computer Science [Waterloo] (CS), University of Waterloo [Waterloo], Mathématiques & Sécurité de l'information (XLIM-MATHIS), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2019 |
| Předmět: |
Computer Science - Symbolic Computation
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] FOS: Computer and information sciences Polynomial Algebraic algorithms 010102 general mathematics Linear system Univariate 010103 numerical & computational mathematics Bivariate analysis Symbolic Computation (cs.SC) 16. Peace & justice 01 natural sciences Polynomial matrix Prime (order theory) Resultant Implementation Polynomial matrices ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Multiplication 0101 mathematics Algorithm Decoding methods Mathematics |
| Zdroj: | ISSAC |
| DOI: | 10.48550/arxiv.1905.04356 |
| Popis: | Complexity bounds for many problems on matrices with univariate polynomial entries have been improved in the last few years. Still, for most related algorithms, efficient implementations are not available, which leaves open the question of the practical impact of these algorithms, e.g. on applications such as decoding some error-correcting codes and solving polynomial systems or structured linear systems. In this paper, we discuss implementation aspects for most fundamental operations: multiplication, truncated inversion, approximants, interpolants, kernels, linear system solving, determinant, and basis reduction. We focus on prime fields with a word-size modulus, relying on Shoup's C++ library NTL. Combining these new tools to implement variants of Villard's algorithm for the resultant of generic bivariate polynomials (ISSAC 2018), we get better performance than the state of the art for large parameters. Comment: ISSAC 2019, 8 pages on 2 columns |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|