Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleEfficient algorithms for order basis computation
Author(s) George Labahn, Wei Zhou
TypeArticle in Journal
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 = 1^n ( 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.
KeywordsOrder basis, Module basis, Padé approximation
URL http://www.sciencedirect.com/science/article/pii/S074771711100201X
JournalJournal of Symbolic Computation
Pages793 - 819
NoteInternational Symposium on Symbolic and Algebraic Computation (ISSAC 2009)
Translation No
Refereed No