||06-23-2010 12:28 PM
Theoretical reduction of O(n^3) to O(n) in certain cases
An arbitrary matrix can be solved using Gauss-Jordan elimination with O(n^3) complexity. A tridiagonal matrix (i.e. a special type of matrix) can be solved using Gauss-Jordan with O(n) complexity. That is, a for an arbitrary matrix, Gauss-Jordan 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?