2005/08/25 by Claude-Pierre Jeannerod, Jeannerod, Claude-Pierre, Gilles Villard +1
Computer Science · Mathematics · #Advanced Differential Equations and Dynamical Systems #Computational Complexity (cs.CC) #F.2.1 #FOS: Computer and information sciences #I.1 #Matrix Theory and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.CC #cs.SC
paper · pdf · doi:10.48550/arxiv.cs/0508113
arxiv created 2005/08/25 · openalex publication_date 2005/08/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. 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.