New codes for the Berlekamp-Massey-Sakata algorithm (Q5941621)

It is known that the key concept for generalizing the Berlekamp-Massey algorithm is the existence of an order function which is a map from a ring to the nonnegative integers that determines a filtration of the ring with one-dimensional quotients. In this paper, it is shown that an order function determines a unique valuation on the function field, which has a residue field equal to the base field. Further, 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 helps to define order functions on general surfaces and higher-dimensional varieties.