LSP matrix decomposition revisited - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

LSP matrix decomposition revisited

Résumé

In this paper, we study the problem of computing an LSP-decompositionof a matrix over a field. This decomposition is an extension to arbitrarymatrices of the well-known LUP-decomposition of full rowrankmatrices. We present three different ways of computing an LSP decomposition,that are both rank-sensitive and based on matrix multiplication.In each case, for an m by n input matrix of unknown rankr, the cost we obtain is in O(mnr!−2) for ! > 2. When r is small, thisimproves the O(nm!−1) complexity bound of Ibarra, Moran and Hui. Cet article considère le problème du calcul d’une décomposition LSPd’une matrice à coefficients dans un corps. Cette décomposition est uneextension aux matrices de rang quelconque de la décomposition LUP,classique pour les matrices de rang plein en lignes. On présente troisfaçons de calculer une décomposition LSP en fonction du rang et via leproduit de matrices. Dans chaque cas, le coût obtenu pour une matricem× n de rang r (inconnu a priori) est en O(mnr!−2) avec ! > 2. Pourr petit, cela améliore la borne de complexité en O(nm!−1) d’Ibarra,Moran et Hui.
Cet article considère le problème du calcul d’une décomposition LSPd’une matrice à coefficients dans un corps. Cette décomposition est uneextension aux matrices de rang quelconque de la décomposition LUP,classique pour les matrices de rang plein en lignes. On présente troisfaçons de calculer une décomposition LSP en fonction du rang et via leproduit de matrices. Dans chaque cas, le coût obtenu pour une matricem× n de rang r (inconnu a priori) est en O(mnr!−2) avec ! > 2. Pourr petit, cela améliore la borne de complexité en O(nm!−1) d’Ibarra,Moran et Hui.
Fichier principal
Vignette du fichier
RR2006-28.pdf (289.5 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02102348 , version 1

Citer

Claude-Pierre Jeannerod. LSP matrix decomposition revisited. [Research Report] Laboratoire de l'informatique du parallélisme. 2006, 2+15p. ⟨hal-02102348⟩
57 Consultations
155 Téléchargements

Partager

Gmail Facebook X LinkedIn More