Triangular x-basis decompositions and derandomization of linear algebra algorithms over K[x]
DOI10.1016/J.JSC.2011.09.006zbMATH Open1268.68172OpenAlexW2067539682MaRDI QIDQ412209FDOQ412209
Authors: Somit Gupta, Soumojit Sarkar, Arne Storjohann, 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
Recommendations
- On approximate linearized triangular decompositions
- Randomized numerical linear algebra: Foundations and algorithms
- scientific article; zbMATH DE number 4030822
- 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)
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15)
Cites Work
- Fast projection methods for minimal design problems in linear system theory
- Exact solution of linear equations using p-adic expansions
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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 (Zm)s
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Normalization of row reduced matrices
- Recursiveness in matrix rational interpolation problems
- Parallel algorithms for matrix normal forms
Cited In (12)
- 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
- Triangular decomposition of matrices in a domain
- High-order lifting and integrality certification
- A deterministic algorithm for inverting a polynomial matrix
- Power decoding Reed-Solomon codes up to the Johnson radius
- Deterministic reduction of integer nonsingular linear system solving to matrix multiplication
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)
