posuchmex
Oct21-11, 02:25 AM
Hello, I tried to figure out what is the maximum count of arithmetic operation (*,:,+,-) need for gauss elimination and gauss-jordan elimination, but can not get it right.
what I get from wikipedia is
Gaussian elimination to solve a system of n equations for n unknowns requires n(n+1) / 2 divisions, (2n3 + 3n2 − 5n)/6 multiplications, and (2n3 + 3n2 − 5n)/6 subtractions,[4] for a total of approximately 2n3 / 3 operations. Thus it has arithmetic complexity of O(n3). However, the intermediate entries can grow exponentially large, so it has exponential bit complexity.
but I dont understand how to get to this result.
Thanks for any help.
what I get from wikipedia is
Gaussian elimination to solve a system of n equations for n unknowns requires n(n+1) / 2 divisions, (2n3 + 3n2 − 5n)/6 multiplications, and (2n3 + 3n2 − 5n)/6 subtractions,[4] for a total of approximately 2n3 / 3 operations. Thus it has arithmetic complexity of O(n3). However, the intermediate entries can grow exponentially large, so it has exponential bit complexity.
but I dont understand how to get to this result.
Thanks for any help.