Efficient algorithms for order basis computation

Abstract: In this paper, we present two algorithms for the computation of a shifted order basis of an matrix of power series over a field with . For a given order and balanced shift the first algorithm determines an order basis with a cost of field operations in , where is the exponent of matrix multiplication. Here an input shift is balanced when . This extends the earlier work of Storjohann which only determines a subset of an order basis that is within a specified degree bound using field operations for . 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 field operations in the case that the shift is unbalanced but satisfies the condition . 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. [Copyright &y& Elsevier]