HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix

George Labahn 1 Vincent Neiger 1, 2, 3 Wei Zhou 1
1 Symbolic Computation Group
SCG - Symbolic Computation Group
3 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Given a nonsingular $n \times n$ matrix of univariate polynomials over a field $\mathbb{K}$, we give fast and deterministic algorithms to compute its determinant and its Hermite normal form. Our algorithms use $\widetilde{\mathcal{O}}(n^\omega \lceil s \rceil)$ operations in $\mathbb{K}$, where $s$ is bounded from above by both the average of the degrees of the rows and that of the columns of the matrix and $\omega$ is the exponent of matrix multiplication. The soft-$O$ notation indicates that logarithmic factors in the big-$O$ are omitted while the ceiling function indicates that the cost is $\widetilde{\mathcal{O}}(n^\omega)$ when $s = o(1)$. Our algorithms are based on a fast and deterministic triangularization method for computing the diagonal entries of the Hermite form of a nonsingular matrix.
Document type :
Journal articles
Complete list of metadata

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/hal-01345627
Contributor : Vincent Neiger Connect in order to contact the contributor
Submitted on : Wednesday, March 29, 2017 - 11:28:02 PM
Last modification on : Monday, May 16, 2022 - 4:58:02 PM

File

determinant_hermite_polmat.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

George Labahn, Vincent Neiger, Wei Zhou. Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix. Journal of Complexity, Elsevier, 2017, ⟨10.1016/j.jco.2017.03.003⟩. ⟨hal-01345627v2⟩

Share

Metrics

Record views

198

Files downloads

469