Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Alternatives for Gaussian elimination transform and conquer algorithm

Gaussian elimination algorithm in transform and conquer has O(n3) complexity. Is there any technique that give more efficient complexity of this algorithm?

like image 765
ana Avatar asked Nov 30 '25 14:11

ana


1 Answers

There are algorithms for matrix inversion with better asymptotic complexity, e.g., the Strassen algorithm with complexity O(n2.807) and the Coppersmith–Winograd algorithm with complexity O(n2.376).

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

like image 173
Roland Avatar answered Dec 03 '25 14:12

Roland



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!