Alternatives for Gaussian elimination transform and conquer algorithm

Gaussian elimination algorithm in transform and conquer has O(n³) c开发者_Go百科omplexity. Is there any technique that give more efficient complexity of this algorithm?

There are algorithms for matrix inversion with better asymptotic complexity, e.g., the Strassen algorithm with complexity O(n^2.807) and the Coppersmith–Winograd algorithm with complexity O(n^2.376).

(Note that the complexity of matrix multiplication and matrix inversion are the same)

It depends on which complexity you measure:

Number of multiplications: No, by changing the technique you can only worsen the complexity of Gaussian elimination.

Number of time steps: Yes, parallel implementation of the row operations reduces time complexity to O(n).