LSP matrix decomposition revisited

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102348
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:23:36 AM
Last modification on : Friday, April 19, 2019 - 1:38:15 AM

File

RR2006-28.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102348, version 1

Collections

Citation

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

Share

Metrics

Record views

5

Files downloads

8