This video has amused and fascinated many because it displays a fundamental ignorance of a basic rule of the – universe – a consequence of the second law of thermodynamics – that one cannot extract more information out of a picture than went into it at the time of creation:

But, according to the “Communications of the ACM” (subscription required), researchers at Carnegie Mellon University may have developed better ways to extract the information that *is* in an image.

That seems to be one of the consequences of new algorithms they have developed to deliver faster solutions to certain classes of linear systems (linear equations with many – perhaps billions – of variables).

To quote a small bit of the article (my emphasis added):

*The researchers say the algorithm, which applies to a class of problems known as symmetric and diagonally dominant (SDD) systems, not only has practical potential, but also is so fast it might soon be possible for a desktop PC to solve systems with one billion variables in just seconds. “The main point of the new algorithm is that it is guaranteed to work and to work quickly,” says Gary L. Miller, a professor of computer science at CMU and a member of the three-person team that developed the*

*new algorithm.*

*SDD systems, characterized by system matrices in which each diagonal element is larger than the sum of the absolute values of all the other elements in the corresponding row, are used for a wide range of purposes, from online recommendation systems to industrial **simulations, materials modeling, and image processing. Algorithms used for this type of linear system fall into two broad classes: direct solvers, such as Gaussian elimination, and iterative solvers. In contrast to direct solvers, which compute exact solutions, iterative solvers produce a series of approximate solutions. Direct methods are*

*usually memory-hungry, a limitation that makes iterative solvers, such as the*

*kind developed by the CMU team, more effective for the large data sets generated by today’s applications.*

The article also has some real world examples of how the algorithm is being used to improve medical software.

Cannot immediately point you to a good book on this, though Amazon have an expensive DVD.

###### Related articles

- FOCS 2011 Accepted Papers (with pdf files) (kintali.wordpress.com)
- Projects are systems (herdingcats.typepad.com)
- Alan Turing and linear algebra (micromath.wordpress.com)
- Google offers peek behind its search results (news.cnet.com)
- Understanding and Writing Linear Equations, Inequalites, and Systems (scienceray.com)
- Fastest Javascript Sudoku Solver (attractivechaos.github.com)