Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x]\)

DOI10.1016/j.jsc.2011.09.006zbMath1268.68172MaRDI QIDQ412209

Arne Storjohann, Somit Gupta, Soumojit Sarkar, Johnny Valeriote

Publication date: 4 May 2012

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2011.09.006

zbMATH Keywords

polynomial matrices; derandomization; linear system solving; row reduction

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

15A15: Determinants, permanents, traces, other special matrix functions

Related Items

Power decoding Reed-Solomon codes up to the Johnson radius, Verification protocols with sub-linear communication for polynomial matrix operations, A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix, Algorithms for simultaneous Hermite-Padé approximations, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, A deterministic algorithm for inverting a polynomial matrix, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, Computing minimal interpolation bases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A local construction of the Smith normal form of a matrix polynomial
• Recursiveness in matrix rational interpolation problems
• Parallel algorithms for matrix normal forms
• Fast projection methods for minimal design problems in linear system theory
• Exact solution of linear equations using p-adic expansions
• On lattice reduction for polynomial matrices
• High-order lifting and integrality certification
• Generalized subresultants for computing the Smith normal form of polynomial matrices
• The shifted number system for fast linear algebra on integer matrices
• Normal forms for general polynomial matrices
• Certified dense linear system solving
• Rational solutions of singular linear systems
• Spans in the module (Z_m)^s
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Asymptotically Fast Triangularization of Matrices over Rings
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Normalization of row reduced matrices
• Asymptotically fast polynomial matrix algorithms for multivariable systems
• Elementary Divisors and Modules