Consider Ax = b solved "directly" which is Gaussian elimination where one succesively removes
-
x1 from Equation 2 to N,
-
x2 from Equations 3 to N etc.
|
|
Then this has memory requirement of order N2 and computational complexity of order N3
|
|
This is modified somewhat when you consider matrices A with a lot of zeroes and try hard to exploit these zeros i.e. avoid doing calculations which are irrelevant as adding or multiplying by zero
|
|
Of course this cannot be done by testing on matrix element being zero as modern computers do floating point arithmetic faster than or at least as fast as test!
|
|
Rather one arranges loops to not include zero elements -- if possible!
|
