Slashdot Mirror

← Back to Stories (view on slashdot.org)

Astonishing Speedup In Solving Linear SDD Systems

Posted by kdawson on from the want-to-see-it-again? dept.

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."

6 of 157 comments (clear)

  1. A Perfect Slashdot Article by GrifterCC · · Score: 5, Insightful

    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.

    1. Re:A Perfect Slashdot Article by jgagnon · · Score: 2, Insightful

      I was thinking something similar. I'm a fairly smart guy and this went way over my head. I love math and the problems it can solve when used creatively. I've just never had the energy to pursue it to a level these (and other) researchers have.

      I feel myself chanting "I'm not worthy."

      --
      Remember to maintain your supply of /facepalm oil to prevent chafing.
    2. Re:A Perfect Slashdot Article by Peach+Rings · · Score: 4, Insightful

      Why do you need to go to college? Here, watch Linear Algebra and Algorithms.

      Also there is no remotely advanced math dropped in TFA, though the actual paper of course is cutting edge research.

    3. Re:A Perfect Slashdot Article by ceoyoyo · · Score: 5, Insightful

      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.

  2. This is exactly what I want from Slashdot, too by G3ckoG33k · · Score: 2, Insightful

    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.

  3. Applications by goodmanj · · Score: 2, Insightful

    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.