Astonishing Speedup In Solving Linear SDD Systems

eldavojohn writes "A new paper (PDF) out of Carnegie Mellon University shows how to solve symmetric diagonally dominant linear systems much faster than before. The technique employs graph theory, randomized algorithms, and linear algebra to achieve an astonishing advantage over current methods to solve such systems. From the article: 'The result is a significant decrease in computer run times. The Gaussian elimination algorithm runs in time proportional to s^3, where s is the size of the SDD system as measured by the number of terms in the system, even when s is not much bigger the number of variables. The new algorithm, by comparison, has a run time of s*[log(s)]^2. That means, if s = 1 million, that the new algorithm run time would be about a billion times faster than Gaussian elimination.' Developers out there who maintain matrix packages and linear algebra tools might want to take a peak at the paper. Anyone who has modeled real-world systems will be able to tell you that speedups in linear algebra algorithms have a weighty effect on efficiency in simulations — especially as one approaches the theoretical limits of optimality. This research is currently being presented at the IEEE Symposium on Foundations of Computer Science."

Comments

May I be the first to say

[Anonymous Coward]

Huh?

Re:May I be the first to say

[Gilmoure]

Tonight's the night I shall be talking about of flu the subject of word association football. This is a technique out a living much used in the practice makes perfect of psychoanalysister and brother and one that has occupied piper the majority rule of my attention squad by the right number one two three four the last five years to the memory. It is quite remarkable baker charlie how much the miller's son this so-called while you were out word association immigrants' problems influences the manner from heaven in which we sleekit cowering timrous beasties all-American Speke, the famous explorer. And the really well that is surprising partner in crime is that a lot and his wife of the lions' feeding time we may be c d e effectively quite unaware of the fact or fiction section of the Watford Public Library that we are even doing it is a far, far better thing that I do now then, now then, what's going onward christian Barnard the famous hearty part of the lettuce now praise famous mental homes for loonies like me. So on the button, my contention causing all the headaches, is that unless we take into account of Monte Cristo in our thinking George the Fifth this phenomenon the other hand we shall not be able satisFact or Fiction section of the Watford Public Library againily to understand to attention when I'm talking to you and stop laughing, about human nature, man's psychological make-up some story the wife'll believe and hence the very meaning of life itselfish bastard, I'll kick him in the Ball's Pond Road.

Wow?

[JargonScott]

Good gravy, now I understand why my non-tech wife just stares blankly at me when I'm describing my plain old IT job.

Re:Wow?

[Anonymous Coward]

She could also be autistic or wishing she were blind AND deaf.

WTF, Over?

[toygeek]

Who knew that when I got up to check my daily's (Incl /.) that I'd end up with scrambled brains for breakfast.

Take a "peak"?

[jcwren]

Take a Mt. McKinley at the paper? Or a K2?

Spell checkers are not a replacement for actually reading what you've written.

2,000 year-old problem for developers

[digitaldc]

"Solving these linear systems can be time consuming on even the fastest computers and is an enduring computational problem that mathematicians have sweated for 2,000 years."

I know what you mean. I remember Pythagoras, Euclid and Aristotle writing about sweating over their laptops while trying to smooth-out their proofs and algorthims.

Re:2,000 year-old problem for developers

[Anonymous Coward]

Archimedes too.. he used to move the sand grains of his finite state machine with a stick to perform such calculations :)

Re:A Perfect Slashdot Article

[jdgeorge]

Or Khan Academy. Out of curiosity, I watched all of Khan's math topics that weren't over my head. Next, I'm on to Addition 2!

Re:Sounds like multigrid

[DriedClexler]

I know an O(s) algorithm for solving linear systems, but it only works on diagonal matrices ...

Re:Sounds like multigrid

[Anonymous Coward]

I know an O(s) algorithm for solving any matrix, but it won't fit in the margin of this page.