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

Given a nonsingular n×n matrix of univariate polynomials over a field K, we give fast and deterministic algorithms to compute its determinant and its Hermite normal form. Our algorithms use O˜(nω⌈s⌉) operations in K, where s is bounded from above by both the average of the degrees of the rows and th...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2017-10, Vol.42, p.44-71
Main Authors: Labahn, George, Neiger, Vincent, Zhou, Wei
Format: Article
Language:English
Subjects:
Computer Science
Determinant
Hermite normal form
Polynomial matrix
Symbolic Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a nonsingular n×n matrix of univariate polynomials over a field K, we give fast and deterministic algorithms to compute its determinant and its Hermite normal form. Our algorithms use O˜(nω⌈s⌉) operations in 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 ω 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 O˜(nω) 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.
ISSN:0885-064X
1090-2708
DOI:10.1016/j.jco.2017.03.003