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.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...