Improved algorithms for computing determinants and resultants

DOI10.1016/j.jco.2004.03.003zbMath1101.68981OpenAlexW2108888104MaRDI QIDQ1763424

Ioannis Z. Emiris, Pan, Victor Y.

Publication date: 22 February 2005

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2004.03.003

zbMATH Keywords

Computer algebraRandomized algorithmsBit complexityMatrix determinantPolynomial system solvingStructured matrix

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Randomized algorithms (68W20)

Related Items

Bezout matrices, subresultant polynomials and parameters, Schur aggregation for linear systems and determinants, The shifted number system for fast linear algebra on integer matrices, Computing polynomial univariate representations of zero-dimensional ideals by Gröbner basis, Bernstein-Bezoutian matrices and curve implicitization, Randomized preprocessing versus pivoting, Additive preconditioning and aggregation in matrix computations, Counting solutions of a polynomial system locally and exactly, Sparse difference resultant, Elimination theory in differential and difference algebra, Multilinear polynomial systems: root isolation and bit complexity, Improved algorithms for computing determinants and resultants, Matrix formulæ for resultants and discriminants of bivariate tensor-product polynomials, Rational formulas for traces in zero-dimensional algebras, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Sparse differential resultant for Laurent differential polynomials

Uses Software

• MultRoot
• ISOLATE
• na10

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The guaranteed convergence of Laguerre-like method
• A supplementary bibliography: on roots of polynomials
• Numerical computation of polynomial zeros by means of Aberth's method
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Generalised characteristic polynomials
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Implicit representation of rational parametric surfaces
• Parametrization of Newton's iteration for computations with structured matrices and applications
• Multipolynomial resultant algorithms
• Safe convergence of simultaneous methods for polynomial zeros
• Sign determination in residue number systems
• Computing the isolated roots by matrix methods
• Solving zero-dimensional systems through the rational univariate representation
• A bibliography on roots of polynomials
• Efficient isolation of polynomial's real roots.
• Symbolic and numeric methods for exploiting structure in constructing resultant matrices
• Improved algorithms for computing determinants and resultants
• PRIMES is in P
• High-order lifting and integrality certification
• The theory of Smale's point estimation and its applications
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• The shifted number system for fast linear algebra on integer matrices
• On the computational power of pushdown automata
• Macaulay style formulas for sparse resultants
• Polynomial root finding using iterated Eigenvalue computation
• Efficient Algorithms for MultiPolynomial Resultant
• On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
• Solving sparse linear equations over finite fields
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
• Solving a Polynomial Equation: Some History and Recent Progress
• A Complete Implementation for Computing General Dimensional Convex Hulls
• A subdivision-based algorithm for the sparse resultant
• Certification of numerical computation of the sign of the determinant of a matrix
• Point estimation of simultaneous methods for solving polynomial equations: A survey