Nearly Optimal Algorithms for Canonical Matrix Forms

DOI10.1137/S0097539793252687MaRDI QIDQ4857589zbMATH OpenFDO

Authors Mark Giesbrecht

Publication date 2 June 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

complexitymatrix multiplicationFrobenius canonical formmatrix poweringrational Jordan formprocessor-efficient parallel algorithmsevaluating polynomials at matricesLas-Vegas-type probabilistic algorithm

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Canonical forms, reductions, classification (15A21)

Recommendations

• scientific article; zbMATH DE number 1256647
• Black box Frobenius decompositions over small fields
• scientific article; zbMATH DE number 1263430
• scientific article; zbMATH DE number 149364
• Computing rational forms of integer matrices

Cited in

(32)

• Computing the combinatorial canonical form of a layered mixed matrix
• The rational canonical form of a matrix
• Counting invariant subspaces and decompositions of additive polynomials
• A canonical form for positive definite matrices
• Constructive recognition of classical groups in odd characteristic.
• Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\)
• Large element orders and the characteristic of Lie-type simple groups.
• Density of normal elements
• On matrix perturbations with minimal leading Jordan structure.
• Fast maximum likelihood estimation of very large spatial autoregressive models: a characteristic polynomial approach.
• Efficient decomposition of associative algebras over finite fields
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Processor efficient parallel matching
• Efficient computation of a canonical form for a matrix with the generalized P-property
• Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
• The module isomorphism problem reconsidered.
• The Complexity of Diagonalization
• The shifted number system for fast linear algebra on integer matrices
• scientific article; zbMATH DE number 1574494 (Why is no real title available?)
• scientific article; zbMATH DE number 149364 (Why is no real title available?)
• Finding the radical of matrix algebras using Fitting decompositions
• Certified dense linear system solving
• Efficient decomposition of separable algebras.
• Dynamic normal forms and dynamic characteristic polynomial
• Complex matrix inversion via real matrix inversions
• Computing rational forms of integer matrices
• Subquadratic-time factoring of polynomials over finite fields
• A simple algorithm for computing canonical forms
• On the computation of minimal polynomials, cyclic vectors, and Frobenius forms
• Nearly optimal computations with structured matrices
• Treating the Exceptional Cases of the MeatAxe
• Computing minimal polynomials of matrices

This page was built for publication: Nearly Optimal Algorithms for Canonical Matrix Forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4857589)