New Codes for the Berlekamp–Massey–Sakata Algorithm

✍ Scribed by Michael E. O'Sullivan

• Book ID: 102572878
• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 401 KB
• Volume: 7
• Category: Article
• ISSN: 1071-5797
• DOI: 10.1006/ffta.2000.0283

✦ Synopsis

The key concept for generalizing the Berlekamp}Massey algorithm is the existence of an order function, a map from a ring to the nonnegative integers which determines a "ltration of the ring with one-dimensional quotients. In this article I show that an order function determines a unique valuation on the function "eld, which has a residue "eld equal to the base "eld. The geometry of these valuations for several monomial orderings on a polynomial ring is discussed, and an ordering is constructed which does not correspond to any monomial ordering. The geometric description allows us to de"ne order functions on general surfaces and higher dimensional varieties.