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

DOI10.1016/j.jsc.2011.09.006zbMath1268.68172OpenAlexW2067539682MaRDI 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 matricesderandomizationlinear system solvingrow reduction

Mathematics Subject Classification ID

Related Items (8)

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

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

This page was built for publication: Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x]\)