LinuxQuestions.org
Go Job Hunting at the LQ Job Marketplace
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
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

Reply
 
Search this Thread
Old 06-23-2010, 11:28 AM   #1
Travis86
Member
 
Registered: Dec 2002
Location: The land of GMT -6
Distribution: OS X, PS2 Linux, Ubuntu, IRIX 6.5
Posts: 399

Rep: Reputation: 31
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?
 
Old 06-23-2010, 11:44 AM   #2
easuter
Member
 
Registered: Dec 2005
Location: Portugal
Distribution: Slackware64 13.0, Slackware64 13.1
Posts: 538

Rep: Reputation: 62
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
 
Old 06-23-2010, 05:30 PM   #3
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

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


Reply


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


Similar Threads
Thread Thread Starter Forum Replies Last Post
Block based data reduction yaplej Programming 5 04-29-2010 05:33 PM
SMTP Spam reduction restrictions gnirtS Linux - Server 4 12-28-2007 11:23 PM
Theoretical Future?? nathanhillinbl Linux - Security 5 05-04-2007 01:43 AM
online extension/reduction LVM? justsimran Linux - General 1 03-08-2007 01:24 PM
Theoretical Question jgr220 Linux - Security 3 03-29-2003 05:40 AM


All times are GMT -5. The time now is 10:50 AM.

Main Menu
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.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration