Ricordo un'accesa discussione su questo ng riguardo a un'affermazione
che avevo fatto e cioè che la riduzione di Gauss non fosse ottima.
Avevo citato una pubblicazione dal titolo "Gaussian Elimination is not
Optimal" che proponeva un metodo per calcolare il prodotto di due
matrici in tempo inferiore a 4.7 n^(2.8).
Durante il mio studio della fattorizzazione (sparsa) LU (per
un'efficiente implementazione del simplesso) ho letto che, in effetti,
la riduzione di Gauss (per matrici quadrate) effettua più o meno le
stesse operazioni del prodotto di matrici. In particolare, se A = LU, allora
u_{ij} = a_{ij} - Sum_{k=1}^{j-1} l_{ik}u_{kj}
l_{ij} = u_{ij}/u_{jj}
da cui si può ottenere la fattorizzazione LU partendo da A.
Utilizzando il metodo di Strasse (o altri nuovi metodi) si può ottenere
una fattorizzazione LU in o(n^3), battendo quindi l'algoritmo di Gauss.
Non so se il risultato si possa generalizzare a matrici rettangolari
qualsiasi. Purtroppo non ho tempo per approfondire e indagare oltre.

Kiuhnm