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

Details:

   
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
ISSN1009-2757
URL http://link.springer.com/article/10.1007%2Fs11432-008-0032-2
LanguageEnglish
JournalSci. China, Ser. F
Volume51
Number4
Pages368--380
PublisherSpringer, Heidelberg; Science in China Press, Beijing
Year2008
Edition0
Translation No
Refereed No
Webmaster