Efficient algorithms for order basis computation

In this paper, we present two algorithms for the computation of a shifted order basis of an m x n matrix of power series over a field K with m <= n. For a given order sigma and balanced shift s the first algorithm determines an order basis with a cost of O-similar to (n(omega) [m sigma / n]) field operations in K, where omega is the exponent of matrix multiplication. Here an input shift is balanced when max((s) over bar) - min((s) over bar) is an element of O(m sigma / n). This extends the earlier work of Storjohann which only determines a subset of an order basis that is within a specified degree bound delta using O-similar to(n(omega)delta) field operations for delta >= [m sigma / n]. While the first algorithm addresses the case when the column degrees of a complete order basis are unbalanced given a balanced input shift, it is not efficient in the case when an unbalanced shift results in the row degrees also becoming unbalanced. We present a second algorithm which balances the high degree rows and computes an order basis also using O-similar to(n(omega)[m sigma / n]) field operations in the case that the shift is unbalanced but satisfies the condition Sigma(n)(i=1)(max((s) over bar) - (s) over bar) <= m sigma. This condition essentially allows us to locate those high degree rows that need to be balanced. This extends the earlier work by the authors from ISSAC'09. (C) 2012 Elsevier Ltd. All rights reserved.