efficient computation of order bases
In this paper we give an efficient algorithm for computation of order basis of a matrix of power series. For a problem with an m x n input matrix over a field K , m ? n , and order ?, our algorithm uses O (MM( n , ? O ~( n ? ? m ?/ n ?) field operations in B.K , where the soft- O notation O ~ is Big O with log factors omitted and MM( n,d ) denotes the cost of multiplying two polynomial matrices with dimension n and degree d . The algorithm extends earlier work of Storjohann, whose method can be used to find a subset of an order basis that is within a specified degree bound ? using O ~(MM( n,? )) field operations for ??? m ?/ n ?.
order basis complexity