Designs and Their Codes, 1992. ,
Fast Algorithms for Manipulating Formal Power Series, J. ACM, vol.25, pp.581-595, 1978. ,
On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, vol.28, pp.693-701, 1991. ,
, Ideals, Varieties, and Algorithms, 2015.
Fast systematic encoding of multiplicity codes, J. Symb. Comput, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01512372
Size of Coefficients of Lexicographical Gröbner Bases: The Zero-Dimensional, Radical and Bivariate Case, Proceedings ISSAC 2009. 119-126, 2009. ,
A Probabilistic Remark on Algebraic Program Testing, Inf. Process. Lett, vol.7, issue.78, pp.90067-90071, 1978. ,
FLINT: Fast Library for Number Theory, 2015. ,
Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts, Proceedings ISSAC 2016, pp.295-302, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01265983
Linear Systems, 1980. ,
Fast Polynomial Factorization and Modular Composition, SIAM J. Comput, vol.40, pp.1767-1802, 2011. ,
Ideal bases and primary decomposition: case of two variables, J. Symb. Comput, vol.1, p.3, 1985. ,
Powers of tensors and fast matrix multiplication, Proceedings ISSAC 2014. ACM, pp.296-303, 2014. ,
Algebraic geometric codes on certain plane curves, Electronics and Communications in Japan (Part III: Fundamental Electronic Science, vol.76, pp.1-13, 1993. ,
Faster modular composition, 2020. ,
Computing Canonical Bases of Modules of Univariate Relations, Proceedings ISSAC 2017, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01457979
Fast Multipoint Evaluation of Bivariate Polynomials, Proceedings ESA 2004, 2004. ,
Simple Multivariate Polynomial Multiplication, J. Symb. Comput, vol.18, pp.183-186, 1994. ,
On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comput, vol.2, pp.60-66, 1973. ,
Some properties of the control systems with irreducible matrixtransfer functions, Seminar on Diff. Eq. and Dyn. Sys., II, pp.169-180, 1970. ,
Fast Probabilistic Algorithms for Verification of Polynomial Identities, J. ACM, vol.27, pp.701-717, 1980. ,
NTL: A Library for doing Number Theory, 2020. ,
On the complexity of multivariate polynomial division, Proceedings ACA 2015. 447-458, 2015. ,
Modular composition via factorization, J. Complexity, vol.48, pp.36-68, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-02350457
Fast multivariate multi-point evaluation revisited, J. Complexity, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-01848571
Multi-point evaluation in higher dimensions, Appl. Algebra Eng. Commun. Comput, vol.24, pp.37-52, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00477659
On computing the resultant of generic bivariate polynomials, Proceedings ISSAC 2018. 391-398, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01921369
On computing the resultant of generic bivariate polynomials, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01921369
Functional decomposition of polynomials: the tame case, J. Symb. Comput, vol.9, p.3, 1990. ,
, Modern Computer Algebra, 2013.
Let G = {b 0 , . . . , b s } ? K[x, y] be a minimal ? lex -Gröbner basis, sorted according to ? lex . Then (1) deg y b 0 < . . . < deg y b s ; and (2) LC y (b s ) | LC y (b s?1 ), Proceedings EUROSAM'79, pp.216-226, 1979. ,
, Since I is an ideal of K[x, y] and I ? =
,
, Clearly B ? I ? , and the elements of B all have different y-degree and so are K[x]-linearly independent. Also |B| = ? ? d 0 , so if B generates B generates I ? , so take some f ? I ? . Since f ? I the multivariate division algorithm using G and the order ? lex results in q 0
, Thus no term of q i b i is divisible by LT lex (b i+1 ) for any i < s. But by Corollary A.1 then LC y (b i+1 ) divides LC y (b i ), and so if deg y (q i b i ) ? deg y b i+1 then LT lex
There is an algorithm which inputs a ? lex -Gröbner basis G = [b 0 , . . . , b s ] ? K[x, y] with deg y b 0 = 0, and a polynomial f ? K[x, y], and outputs f rem G in timeÕ(|G |d x (deg y f )), where d x = max ,