Computing rational forms of integer matrices
type: Item
instance of: scholarly article
title: Computing rational forms of integer matrices
zbMATH Open document ID: 1016.65025
author: Arne Storjohann
author: Mark Giesbrecht
published in: Journal of Symbolic Computation
publication date: 2003-03-23T00:00:00Z
review text: A new Las Vegas type algorithm is presented for finding the Frobenius rational form of any \(n\times n\) integer matrix. The expected number of word operations is \(O(n^4(\log n+\log \|A\|)+ n^3(\log n+\log \|A\|)^2)\), where \(\|A\|=\max |A_{ij} |\). Las Vegas algorithms are also introduced to compute a transformation matrix to the Frobenius form, and to compute the rational Jordan form of an integer matrix.
reviewed by: F. Szidarovszky
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A21
Mathematics Subject Classification ID: 15B36
zbMATH DE Number: 1886749
zbMATH Keywords: Las Vegas type algorithm
zbMATH Keywords: Frobenius rational form
zbMATH Keywords: integer matrix
zbMATH Keywords: rational Jordan form
MaRDI profile type: Publication
full work available at URL: jsco.2002.0554
OpenAlex ID: W2078168416
cites work: Factor Refinement
cites work: Q3254327
cites work: Nearly Optimal Algorithms for Canonical Matrix Forms
cites work: Q3359644
cites work: Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
cites work: Parallel algorithms for matrix normal forms
cites work: Solving systems of linear equations over polynomials
cites work: Q3935355
cites work: Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients
cites work: Q3773973
cites work: On p-adic computation of the rational form of a matrix
cites work: An Inequality About Factors of Polynomials
cites work: Approximate formulas for some functions of prime numbers
cites work: Generalized subresultants for computing the Smith normal form of polynomial matrices
cites work: Modern computer algebra
DOI: 10.1006/JSCO.2002.0554
description: scientific article; zbMATH DE number 1886749