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

DOI10.1016/J.JSC.2011.09.006zbMATH Open1268.68172OpenAlexW2067539682MaRDI QIDQ412209FDOQ412209

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

derandomizationpolynomial matriceslinear system solvingrow reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15)

Cites Work

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

Cited In (9)

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

   Recommendations

• On approximate linearized triangular decompositions 👍 👎
• Randomized numerical linear algebra: Foundations and algorithms 👍 👎
• Title not available (Why is that?) 👍 👎
• Randomized algorithms in numerical linear algebra 👍 👎
• A randomized algorithm for the decomposition of matrices 👍 👎
• An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms 👍 👎
• Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations 👍 👎
• Direct fail-proof triangularization algorithms for \(AX+XB=C\) with error- free and parallel implementations 👍 👎
• Randomization and the parallel solution of linear algebra problems 👍 👎
• Fast randomized algorithms for the structure of matrix algebras over finite fields (extended abstract) 👍 👎

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

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