Efficient algorithms for order basis computation

AbstractIn this paper, we present two algorithms for the computation of a shifted order basis of an m×n matrix of power series over a field K with m≤n. For a given order σ and balanced shift s→ the first algorithm determines an order basis with a cost of O∼(nω⌈mσ/n⌉) field operations in K, where ω is the exponent of matrix multiplication. Here an input shift is balanced when max(s→)−min(s→)∈O(mσ/n). This extends the earlier work of Storjohann which only determines a subset of an order basis that is within a specified degree bound δ using O∼(nωδ) field operations for δ≥⌈mσ/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∼(nω⌈mσ/n⌉) field operations in the case that the shift is unbalanced but satisfies the condition ∑i=1n(max(s→)−s→i)≤mσ. 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