Geek asks and answers

Alternatives to the Gaussian elimination algorithm and capture algorithm

Gaussian elimination algorithm in transformation and subjugation has complexity O (n 3 ). Is there any method that gives more efficient complexity of this algorithm?

+3
source share
2 answers

There are algorithms for inverting a matrix with better asymptotic complexity, for example, the Strassen algorithm with complexity O (n 2.807 ) and Coppersmith-Winograd with complexity O (n 2.376 ).

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

+3
source

, :

: , .

: , O (n).

0

More articles:


All Articles