Asymptotically fast polynomial matrix algorithms for multivariable systems

We present the asymtotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank; nullspace; determinant; generic inverse reduced form (Giorgi et al. 2003, Storjohann 2003, Jeannerod and Villard 2005, Storjohann and Villard 2005). We show that they essentially can be reduced to two computer algebra techniques, minimal basis computations and matrix fraction expansion/reconstruction, and to polynomial matrix multiplication. Such reductions eventually imply that all these problems can be solved in about the same amount of time as polynomial matrix multiplication. The algorithms are deterministic, or randomized with certified output in a Las Vegas fashion.

• Publication year

  2005

• Venue

  arXiv.org

• Publication date

  2005-08-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1080/00207170600726477arXiv cs/0508113
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A uniform approach for the fast computation of Matrix-type Pad'e approximants

  2007cited by this paper
• Normal forms for general polynomial matrices

  2006cited by this paper
• Computing the rank and a small nullspace basis of a polynomial matrix

  2005cited by this paper
• Polynomial evaluation and interpolation on special sets of points

  2005cited by this paper
• Essentially optimal computation of the inverse of generic polynomial matrices

  2005influential reference
• On the complexity of polynomial matrix computations

  2003cited by this paper
• High-order lifting and integrality certification

  2003cited by this paper
• Modern computer algebra

  2002cited by this paper
• Minimal Bases of Rational Vector Spaces and Their Importance in Algebraic Systems Theory

  2002influential reference
• On the complexity of computing determinants

  2001cited by this paper
• Analysis of algorithms

  2000cited by this paper
• ALGEBRAIC COMPLEXITY THEORY (Grundlehren der Mathematischen Wissenschaften 315)

  1999cited by this paper
• Minimal Degree Coprime Factorization of Rational Matrices

  1999cited by this paper
• Algebraic complexity theory

  1997cited by this paper
• The Analysis of Algorithms

  1995cited by this paper
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants

  1994cited by this paper
• On computing determinants of matrices without divisions

  1992cited by this paper
• On fast multiplication of polynomials over arbitrary algebras

  1991cited by this paper
• Algebraic Complexity Theory

  1991influential reference
• Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems

  1975influential reference
• Schnelle Berechnung von Kettenbruchentwicklungen

  1971influential reference

• An Empirically Fast Las Vegas Algorithm for Algebraic Shifting

  2025cites this paper
• Algorithms for computing norms and characteristic polynomials on general Drinfeld modules

  2023cites this paper
• Online order basis algorithm and its impact on the block Wiedemann algorithm

  2014cites this paper
• A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery

  2013cites this paper
• A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery

  2013cites this paper
• On the Algorithms of Guruswami-Sudan List Decoding over Finite Rings. (Sur l'algorithme de décodage en liste de Guruswami-Sudan sur les anneaux finis)

  2012cites this paper
• Computing minimal nullspace bases

  2012cites this paper
• Triangular x-basis decompositions and derandomization of linear algebra algorithms over K[x]

  2012cites this paper
• Méthodes algébriques pour la résolution d’équations différentielles matricielles d’ordre arbitraire

  2011cites this paper
• Recent progress in linear algebra and lattice basis reduction

  2011cites this paper
• Simple forms of higher-order linear differential systems and their applications in computing regular solutions

  2011cites this paper
• On parametric solution of fault detection problems

  2011cites this paper
• DOCTEUR DE L'UNIVERSITÉ DE LIMOGES

  2011cites this paper
• Algorithm to Compute Minimal Nullspace Basis of a Polynomial Matrix

  2010cites this paper
• Algorithms for regular solutions of higher-order linear differential systems

  2009cites this paper
• Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation

  2008cites this paper
• Some recent progress in exact linear algebra and related questions

  2007cites this paper
• Special issue on the use of computer algebra systems for computer aided control system design

  2006cites this paper
• Table of contents 1. Team 1

  2004cites this paper
• Project-team Arénaire Computer Arithmetic

  year unknowncites this paper