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?

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.

A Perfect Slashdot Article

[GrifterCC]

I can tell it's truly News for Nerds because I can barely understand what it's saying and it drops causal references to advanced mathematics--the stuff I only wish I'd had the fortitude to study in college.

I'm serious. This is exactly what I want from Slashdot.

Re:A Perfect Slashdot Article

[ceoyoyo]

Mathematicians like it that way.

One of the math professors at Berkeley tells his students that math is messy - when you're working on a proof you start from one place, wander around for a while, then get to your destination.

Then you clean everything up and present it to the world as obvious.

Re:A Perfect Slashdot Article

[ObsessiveMathsFreak]

I can tell it's truly News for Nerds because I can barely understand what it's saying and it drops causal references to advanced mathematics--the stuff I only wish I'd had the fortitude to study in college.

You more than likely did study this in college. This involves linear algebra, specifically the inversion of matrices and/or solving linear system. Ax=b, where A is an mxn matrix, and x and b are nx1 and mx1 vectors respectively. What we'd like to do is solve for x using x=A^-1 b, where A^-1 is an inverse matrix of some kind. But getting the inverse is a notoriously difficult problem.

In fact, a large reason digital computers were invented at all was so that "large" matrices could be inverted. And by large, I mean 12x12 matrices (keep in mind this was the 1950s). Computer games, mp3 players, spreadsheets and the internet are all quite incidental byproducts of humanities quest to invert ever larger matrices, in less time. Though just about any half way sophisticated piece of software will invert a matrix at some point.

The reason for this is as follows: When human beings want to solve any difficult problem, they approximate it with a linear model and solve the associated linear system. Hence the ability to solve linear systems quickly and accurately is of fundamental importance. This goes double in the modern world as we increasingly rely on the ability of computers to handle ever larger linear system--that is, to invert ever larger matrices.

The biggest problem with matrices, say nxn matrices, is that the time taken for solving them by Gauss elimination goes up as 0(n^3). So while your desktop could probably invert a 1000x1000 matrix in a few seconds, it would take a year invert a million x million matrix, and would take around a million years to invert a billion x billion matrix. (Not that it could store either in memory). While Gauss elimination is a pretty poor algorithm efficiency-wise, this issues are unavoidable for general matrices.

However, most matrices we actually want to invert in practice are "sparse" or "diagonally dominant". The first property means that most of the elements are zero. So in a billion x billion matrix, instead of storing 10^18 numbers, you'd only have to store a few billion. Diagonally dominant means that largest entries are along the diagonal. Both of these mean you can take a lot of--often hueristic--shortcuts in your inversion algorithims to cut down on time.

These researchers claim O(s*log(s)^2) complexity for such systems. I suspect there are probably a lot of O(s^2*log(s)) system or the like anyway, but even still this is a nice improvement. I doubt it's as big a breakthrough--I suspect this is hyped anyway--but if it is an improvement you can kind of compare this to something like the Fast Fourier Transform speedup. Again, I doubt it's that large of an improvement.

I'll finish by mentioning that this all falls under the umbrella of Linear Algebra, which is an absolutely essential skill of higher mathematics, and computational mathematics. Any geeks who prides themselves on their mathematical ability, but doesn't know their linear algebra (linear systems, the four fundamental subspaces, eigenvectors/values, rotation/transformation matrices, etc) shouldn't be holding their skills in such high regard. If you don't know your LA, or have forgotten, one of the best places to start is to watch Gilbert Strang's online lecture series provided by MIT. These lectures are indispensable to anyone working with linear systems. After this, those who need in depth analysis of matrix algorithms should turn to something like "Matrix Algorithms" by G. W. Stewart which goes into more detail and shows the more canonical algorithms. A little knowledge of linear algebra goes a long way in mathematics.

...Or failing all that, you could just open up MATLAB... or Octave. I recommend the educational route first though.

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.