Back to Search
Start Over
Efficient algorithms for order basis computation
- Source :
-
Journal of Symbolic Computation . Jul2012, Vol. 47 Issue 7, p793-819. 27p. - Publication Year :
- 2012
-
Abstract
- 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]
Details
- Language :
- English
- ISSN :
- 07477171
- Volume :
- 47
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Journal of Symbolic Computation
- Publication Type :
- Academic Journal
- Accession number :
- 73962181
- Full Text :
- https://doi.org/10.1016/j.jsc.2011.12.009