Straight-line computation of the polynomial matrix inverse - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2002

Straight-line computation of the polynomial matrix inverse

(1) , (1)
1

Résumé

We present an inversion algorithm for nonsingular n x n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and requires O~(n^3d) field operations for a generic input. The ``soft Oh'' notation O~ indicates some missing log(nd) factors. The polynomial matrix inverse can thus be computed by a straight-line program whose size is - asymptotically and up to logarithmic factors - the size of its output.
On présente un algorithme pour inverser les matrices n×n dont les coefficients sont des polynômes de degré d sur un corps commutatif abstrait K.Cet algorithme est déterministe et nécessite O ̃(n3d) opérations sur K dans le cas générique. (La notation O contient les facteurs logarithmiques.) L’inverse d’une matrice polynomiale peut donc être calculé par un programme “straight-line” de longueur égale - asymptotiquement et aux facteurs logarithmiques prés - à la taille de sa sortie
Fichier principal
Vignette du fichier
RR2002-47.pdf (170.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101970 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101970 , version 1

Citer

Claude-Pierre Jeannerod, Gilles Villard. Straight-line computation of the polynomial matrix inverse. [Research Report] LIP RR-2002-47, Laboratoire de l'informatique du parallélisme. 2002, 2+10p. ⟨hal-02101970⟩
32 Consultations
146 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More