Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
Article dans une revue

Fast computation of approximant bases in canonical form

Claude-Pierre Jeannerod 1, 2 Vincent Neiger 3 Gilles Villard 1, 2 
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this article, we design fast algorithms for the computation of approximant bases in shifted Popov normal form. We first recall the algorithm known as PM-Basis, which will be our second fundamental engine after polynomial matrix multiplication: most other fast approximant basis algorithms basically aim at efficiently reducing the input instance to instances for which PM-Basis is fast. Such reductions usually involve partial linearization techniques due to Storjohann, which have the effect of balancing the degrees and dimensions in the manipulated matrices. Following these ideas, Zhou and Labahn gave two algorithms which are faster than PM-Basis for important cases including Hermite-Padé approximation, yet only for shifts whose values are concentrated around the minimum or the maximum value. The three mentioned algorithms were designed for balanced orders and compute approximant bases that are generally not normalized. Here, we show how they can be modified to return the shifted Popov basis without impact on their cost bound; besides, we extend Zhou and Labahn's algorithms to arbitrary orders. Furthermore, we give an algorithm which handles arbitrary shifts with one extra logarithmic factor in the cost bound compared to the above algorithms. To the best of our knowledge, this improves upon previously known algorithms for arbitrary shifts, including for particular cases such as Hermite-Padé approximation. This algorithm is based on a recent divide and conquer approach which reduces the general case to the case where information on the output degree is available. As outlined above, we solve the latter case via partial linearizations and PM-Basis.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
Contributeur : Vincent Neiger Connectez-vous pour contacter le contributeur
Soumis le : samedi 6 avril 2019 - 16:13:06
Dernière modification le : mardi 25 octobre 2022 - 16:16:56


Fichiers produits par l'(les) auteur(s)



Claude-Pierre Jeannerod, Vincent Neiger, Gilles Villard. Fast computation of approximant bases in canonical form. Journal of Symbolic Computation, 2020, 98, pp.192-224. ⟨10.1016/j.jsc.2019.07.011⟩. ⟨hal-01683632v2⟩



Consultations de la notice


Téléchargements de fichiers