Back to Search
Start Over
Fast computation of generic bivariate resultants
- Source :
- Journal of Complexity, Journal of Complexity, Elsevier, 2021, ⟨10.1016/j.jco.2020.101499⟩
- Publication Year :
- 2021
- Publisher :
- HAL CCSD, 2021.
-
Abstract
- We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Grobner basis for the ideal generated by the two polynomials.
- Subjects :
- Statistics and Probability
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Control and Optimization
multipoint evaluation
General Mathematics
Computation
[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC]
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Field (mathematics)
010103 numerical & computational mathematics
0102 computer and information sciences
Bivariate analysis
01 natural sciences
Gröbner basis
elimination
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
Applied mathematics
Computer Science::Symbolic Computation
0101 mathematics
computer algebra
Computer Science::Databases
Mathematics
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
Numerical Analysis
Algebra and Number Theory
Ideal (set theory)
algorithm
Mathematics::Commutative Algebra
Applied Mathematics
Symbolic computation
Lexicographical order
Randomized algorithm
010201 computation theory & mathematics
complexity
resultant
Subjects
Details
- Language :
- English
- ISSN :
- 0885064X and 10902708
- Database :
- OpenAIRE
- Journal :
- Journal of Complexity, Journal of Complexity, Elsevier, 2021, ⟨10.1016/j.jco.2020.101499⟩
- Accession number :
- edsair.doi.dedup.....af16f477bc5f2b76c6ddcae556fde7c2
- Full Text :
- https://doi.org/10.1016/j.jco.2020.101499⟩