Travis86 
06232010 11:28 AM 
Theoretical reduction of O(n^3) to O(n) in certain cases
An arbitrary matrix can be solved using GaussJordan elimination with O(n^3) complexity. A tridiagonal matrix (i.e. a special type of matrix) can be solved using GaussJordan with O(n) complexity. That is, a for an arbitrary matrix, GaussJordan is a cumbersome algorithm, but for a tridiagonal matrix, the algorithm can be expressed as a loop and a simple formula.
If I were writing, for example, a compiler or some optimization program, is there a way to test the problem to see if it has become less complex, so I can express the algorithm more simply?
