Fast computation of Gröbner basis of homogenous ideals of $$
\mathbb{F}
$$[ x,y] |
| |
基金项目: | Supported by the National Natural Science Foundation of China (Grant No. 60673082), Special Funds of Authors of Excellent Doctoral Dissertation in Chian (Grant No. 200084) |
| |
摘 要: | This paper provides a fast algorithm for Grobnerbases of homogenous ideals of Fx, y] over a finite field F. We show that only the 8-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Grobner base of the homogenous ideal. It reduces dramatically the number of unnecessary 5-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.
|
关 键 词: | 快速计算 Grobner原理 序列合成 Berlekamp-Massey算法 |
收稿时间: | 4 September 2007 |
修稿时间: | 14 December 2007 |
本文献已被 维普 SpringerLink 等数据库收录! |