Review your favorite Linux distribution.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org Theoretical reduction of O(n^3) to O(n) in certain cases
 User Name Remember Me? Password
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 06-23-2010, 12:28 PM #1 Travis86 Member   Registered: Dec 2002 Location: The land of GMT -6 Distribution: OS X, PS2 Linux, Ubuntu, IRIX 6.5 Posts: 399 Rep: 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?
06-23-2010, 12:44 PM   #2
easuter
Member

Registered: Dec 2005
Location: Portugal
Distribution: Slackware64 13.0, Slackware64 13.1
Posts: 538

Rep:
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

06-23-2010, 06:30 PM   #3
Sergei Steshenko
Senior Member

Registered: May 2005
Posts: 4,481

Rep:
Quote:
 Originally Posted by Travis86 ... 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.

 Thread Tools Search this Thread Search this Thread: Advanced Search

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post yaplej Programming 5 04-29-2010 06:33 PM gnirtS Linux - Server 4 12-29-2007 12:23 AM nathanhillinbl Linux - Security 5 05-04-2007 02:43 AM justsimran Linux - General 1 03-08-2007 02:24 PM jgr220 Linux - Security 3 03-29-2003 06:40 AM

All times are GMT -5. The time now is 09:17 PM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -
 Advertisement
 My LQ
 Write for LQ LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
 Syndicate Latest Threads   LQ News Twitter: @linuxquestions identi.ca: @linuxquestions Facebook: linuxquestions Google+: linuxquestions