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


TitleFast computation of Gr\"obner basis of homogeneous ideals of $mathbbF[x, y]$.
Author(s) PeiZhong Lu, Yan Zou
TypeArticle in Journal
AbstractThis paper provides a fast algorithm for Gröbner bases of homogenous ideals of 𝔽[x, y] over a finite field 𝔽. We show that only the S-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Gröbner base of the homogenous ideal. It reduces dramatically the number of unnecessary S-polynomials that are processed. We also show that the computational complexity of our new algorithm is O(N 2), where N is the maximum degree of the input generating polynomials. The new algorithm can be used to solve a problem of blind recognition of convolutional codes. This problem is a new generalization of the important problem of synthesis of a linear recurring sequence.
Keywordshomogenous ideal, Gröbner basis, sequence synthesis
URL http://link.springer.com/article/10.1007%2Fs11432-008-0032-2
JournalSci. China, Ser. F
PublisherSpringer, Heidelberg; Science in China Press, Beijing
Translation No
Refereed No