Title | **Efficient algorithms for order basis computation** |

Author(s) | George Labahn, Wei Zhou |

Type | Article in Journal |

Abstract | In 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. |

Keywords | Order basis, Module basis, Padé approximation |

ISSN | 0747-7171 |

URL |
http://www.sciencedirect.com/science/article/pii/S074771711100201X |

Language | English |

Journal | Journal of Symbolic Computation |

Volume | 47 |

Number | 7 |

Pages | 793 - 819 |

Year | 2012 |

Note | International Symposium on Symbolic and Algebraic Computation (ISSAC 2009) |

Edition | 0 |

Translation |
No |

Refereed |
No |