Fast computation of generic bivariate resultants |
| |
| Institution: | Niko Muskhelishvili Institute of Computational Mathematics, Georgian Technical University, Georgia;Department of Mathematics, Çankaya University, Ankara, Turkey |
| |
| 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 Gröbner basis for the ideal generated by the two polynomials. |
| |
| Keywords: | Complexity Algorithm Computer algebra Resultant Elimination Multipoint evaluation |
| 本文献已被 ScienceDirect 等数据库收录！ |
