Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitlePrimary decomposition of zero-dimensional ideals over finite fields.
Author(s) Shuhong Gao, Dongming Wang, Mingsheng Wang
TypeArticle in Journal
AbstractA new algorithm is presented for computing primary decomposition of zero-dimensional ideals over finite fields. Like Berlekamp's algorithm for univariate polynomials, the new method is based on the invariant subspace of the Frobenius map acting on the quotient algebra. The dimension of the invariant subspace equals the number of primary components, and a basis of the invariant subspace yields a complete decomposition. Unlike previous approaches for decomposing multivariate polynomial systems, the new method does not need primality testing nor any generic projection, instead it reduces the general decomposition problem directly to root finding of univariate polynomials over the ground field. Also, it is shown how Gröbner basis structure can be used to get partial primary decomposition without any root finding.
ISSN0025-5718; 1088-6842/e
URL http://www.ams.org/journals/mcom/2009-78-265/S0025-5718-08-02115-7/home.html
JournalMath. Comput.
PublisherAmerican Mathematical Society (AMS), Providence, RI
Translation No
Refereed No