High-order lifting and integrality certification

DOI10.1016/S0747-7171(03)00097-XzbMath1059.15020MaRDI QIDQ1878491

Arne Storjohann

Publication date: 20 August 2004

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

zbMATH Keywords

linear systemdeterminantpolynomial matrixSmith canonical formLas Vegas probabilistic algorithmintegrality certification

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Linear equations (linear algebraic aspects) (15A06) Canonical forms, reductions, classification (15A21)

Related Items (23)

Resolving sequences of operators for linear ordinary differential and difference systems of arbitrary order ⋮ The shifted number system for fast linear algebra on integer matrices ⋮ Certified dense linear system solving ⋮ Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix ⋮ Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source ⋮ An algorithm to recognize regular singular Mahler systems ⋮ Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x\)] ⋮ High-order lifting for polynomial Sylvester matrices ⋮ Algorithms for simultaneous Hermite-Padé approximations ⋮ Deterministic computation of the characteristic polynomial in the time of matrix multiplication ⋮ Processor efficient parallel matching ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ A deterministic algorithm for inverting a polynomial matrix ⋮ Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation ⋮ Improved algorithms for computing determinants and resultants ⋮ Essentially optimal computation of the inverse of generic polynomial matrices ⋮ Power decoding Reed-Solomon codes up to the Johnson radius ⋮ Block-Krylov techniques in the context of sparse-FGLM algorithms ⋮ Fast computation of approximant bases in canonical form ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Maximum weight bipartite matching in matrix multiplication time ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Certified dense linear system solving
• Rational solutions of singular linear systems
• Asymptotically Fast Triangularization of Matrices over Rings
• Fast construction of irreducible polynomials over finite fields

This page was built for publication: High-order lifting and integrality certification