Slashdot Mirror
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."
Huh?
Good gravy, now I understand why my non-tech wife just stares blankly at me when I'm describing my plain old IT job.
Nuke Gay Whales for Jesus.
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.
Multigrid is theoretically O(s), so I don't immediately see how this is such a huge leap. Of course the actual complexity also depends on the problem and the implementation. Maybe their method.is applicaple to a wider variety of problems.
Also, the "iterated sparsifying" sounds a lot like algebraic multigrid.
Though the result sounds genuinely interesting, I'm not sure the comparison to Gaussian elimination is fair. The summary gives the O(s^3) asymptotic run time of Gaussian elimination for dense matrices, but there are much better alternatives for a sparse matrix, which is what the paper applies to. For example, if your matrix has the sparsity pattern of a planar graph, it has been known for 30 years that you can do Gaussian elimination in O(n^1.5). This result, however, seems to have the potential to be more widely applicable while producing a better asymptotic bound. So, sounds like great work, but not quite as amazing as the hype in the summary.
Who knew that when I got up to check my daily's (Incl /.) that I'd end up with scrambled brains for breakfast.
Nobodies Prefect
Tidbits for Techs Technology Blog
Take a Mt. McKinley at the paper? Or a K2?
Spell checkers are not a replacement for actually reading what you've written.
"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.
He who knows best knows how little he knows. - Thomas Jefferson
I mean the article "In Florida, a Cell Phone Network With No Need For a Spectrum License"...
What is that?! Not news for nerds... Possibly news for techies.
Comparing the solver's complexity to Gaussian-Elimination isn't useful. No one in their right mind uses direct solvers on large linear systems.
Anyway, if the system is symmetric and dominant diagonal, SOR is the standard choice in iterative solvers.
Only works for sparse matrices.
Yawn...
I agree with a previous poster who said it is unfair to compare this algorithm to Gaussian Elimination. Frankly, it seems to me that the poster has taken enough numerical analysis to know that GE is O(n^3), but is not familiar with the much wider body of research into efficient methods for solving structured linear systems.
Symmetric diagonally dominant linear systems are among the best conditioned systems you could possibly construct, which means that it is a rare case that you would ever use GE. Instead, you would use an iterative method, such as conjugate gradients or a stationary method like the Chebyshev method discussed in the paper. While it does seem that they are proposing a novel way to construct an efficient iterative method, the truth is that once you've entered the realm of iterative methods it's not likely there is going to be a single approach that works best in every instance. Even the paper's author agree that this is a "conceptually simple and possibly practical iterative solver." They rightly recognize that what works well on paper may not always prove useful in practice. So I think we should take the authors' own advice and wait for further research into this approach.
...how do they work?
If I had had Gilbert Strang as an instructor for linear algebra instead of who I did have, maybe I would understand what the article is talking about. Having watched those videos I repeatedly said to myself "oh thats what we were doing!" Are covariance matrices SDDs? If so could this be used to speed up principle component analysis?
refactor the law, its bloated, confusing and unmaintainable.
Who else read the title and was excited thinking there was an astonishing speed-up in SSD systems?
... in the world who make a career out of discovering and trying to use this stuff.
On a lighter note:
The basic concepts behind linear algebra are quite simple and I don't understand why it is not taught sooner than to junior/senior level math/physics majors.
Having studied both the theory and application (albeit only in undergrad courses) of linear algebra in college, I have to wonder why these concepts are not taught to grade school students in place of normal algebra. In my observations as a student and tutor it seems that most prominent source of anxiety for math students is dealing with the concept that the letter x or y or whateverhaveyou represents a number. Having done guass-jordan elimination until my knuckles bled (unfortunately, quite literally. gotta love college), I can imagine a grade-school aged child having far less trouble applying simple arithmetic row operations than most seem to have with basic algebra. Then again, I'm not a PhD educational psychologist, my mother is.
Is this particular kind of funky advanced math used for anything in crypto or information security and does this new speedup help crack that?
props to eldavojohn too - most of the stuff he posts is interesting, and the summaries are usually good too.
This could be interesting for predictive control of the power grid based on a real time model. Current (no pun intended) technology can't do a real time simulation, or must make some crippling simplification assumptions, or is based on some proprietary algorithms (which may be junk, but we can't validate them). Problems arising from variability of wind energy sources or effects of faults on system stability could be handled much more easily.
Also, maybe someone can incorporate this into SPICE so I can run simulations of circuits of more than moderate complexity without dying of old age waiting for them to complete.
Have gnu, will travel.
Just to give people an idea of how useful this is, here are a couple examples of real-world problems that this may help with:
Aerodynamics simulations
Weather and ocean models
Electric and magnetic field models
Earthquake and geophysics models
It may also be useful for modeling wave processes (light, sound, etc) depending on how they're handled. As a general rule, any time you use a computer to solve problems involving electricity and magnetism or the pressures and stresses on solid or fluid materials, you're going to be encountering linear symmetric diagonally-dominant matrices.
In many applications, approximate solutions are faster and more useful than the exact solution described here, but it's still a big deal.
Please send this to the IPCC....oh wait, this would probably makes things MORE accurate....
SSD - symmetric diagonally dominant, mean the diagonal element is more the sum of abs all the rest in the row. That is a very strong condition, which happen in very specific applications. Never met them in the computer vision and image processing for example.
Of course, if it can do that....
Seastead this.
I don't suppose one of you hardware/math geeks could explain to the hordes of lowly IT/storage/server guys what this actually means to us, pragmatically?
I can't even tell at which 'level' this speed-up would occur. Software support/implementation for SSDs? SSD controllers? What are the practical implications?
~/ssh slashdot.org ssh: connect to host slashdot.org port 22: too many beers
"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." - by GrifterCC (673360) on Friday October 22, @10:12AM (#33984898)
Per my subject-line above: Linear Algebra (matrix math really, with all of its 1:1 mappings & "wave of the hand left to bottom" (iirc) processing order (You have to SEE this last one to get what I mean here as to how you match/map & proceed thru matrices for multiplication for instance)) &/or Discrete Math (Graph Theory is covered here, & it's only a PART of this course (hardest course I felt I ever took in collegiate academia in fact, bar-none)) both cover a LARGE chunk of what's involved above!
(Additionally? Well, you don't have to be a "math major" to have taken them in collegiate academia either - they're both typically "std. fare" for Comp. Sci. majors generally also!)
APK
Can someone please explain how s*[log(s)]^2 is a billion times faster than s^3 if s = 1 000 000?
The nice thing about this is that things like electrical circuit simulations, FEA matrices, etc. tend to be SDD. This may speed things up a bit.
That is all.
Better in the sense that the results that can be produced for a given sized grid can be obtained more quickly. Hence, it is possible to dramatically increase the density of sampled points (finer mesh grid) that would yield more localize accuracy and hence potentially more accurate results. Generally speaking the more better data can be included, the more likely the result will make an accurate prediction given the boundary conditions of the model.
If I had known this was going to end up a first post and modded to 5, I would have created an account rather than AC'ed it.
Will this help seti@home increase the speed with which its clients can process the collected radio signals? I thought I recalled that it used gaussian something or another.
the real question is whether I have the intelligence to sufficiently understand it. I've been trying to better my understanding of linear algebra for a number of years new, but it doesn't come easily. It is at least comforting that I can begin to read research papers such as this and understand some of it.
Those who have more substantial knowledge and who make an effort to build ladders to help scale the wall of understanding, like Gilbert Strang, Arnold, Shilov, Gantmacher, and others, are really due serious appreciation.
SSD - symmetric diagonally dominant
No, SSD is Solid State Drive, which is certainly a more common term to see on Slashdot than SDD. I had to read the summary a couple of times before I realized it was talking about mathematical arrays rather than persistent memory arrays. Then it made a lot more sense! :)
Can this be seen as an alternative to the simplex method? Solving problems where Ax=b, x>=0, etc....? This is what I'm taking a grad class in now, so its of some interest...
This is a good paper. Good algorithm. But way too much hype in the summary.
take a "peek" at the paper, perhaps?
Could Donald Knuth explain this category of math? Or is this research (solving SDD linear systems) too current and beyond his reach?
I'm not trying to be "Funny", just curious.