LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Theoretical reduction of O(n^3) to O(n) in certain cases (https://www.linuxquestions.org/questions/programming-9/theoretical-reduction-of-o-n%5E3-to-o-n-in-certain-cases-815938/)

 Travis86 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?

 easuter 06-23-2010 12:44 PM

Quote:
 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?
The most straight-forward approach would probably be to traverse all the matrix elements that belong to each "triangle" to determine if they are all zero. For large matrices I imagine that this operation would definitely pay off if they do in fact turn out to be tridiagonal, however since I have never done this myself I'm afraid this assumption is just conjecture.
But I would like to hear about the results if you do program this ;)

 Sergei Steshenko 06-23-2010 06:30 PM

Quote:
 Originally Posted by Travis86 (Post 4012758) ... 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?
The (kind of) problems you've described has known beforehand loop limits, so the loops can be unrolled statically. Counting lines in the unrolled loop is a pretty good measure of complexity, though, strictly saying, you should also count arithmetic operations.

 All times are GMT -5. The time now is 08:31 AM.