## Speedy Solutions for Linear Systems

October 25, 2010

The PhysOrg.com site has a report from Carnegie-Mellon University [CMU] on a new algorithm, developed by CMU computer scientists, that promises a dramatic speed increase in solving a common class of large linear equation systems.

Computer scientists at Carnegie Mellon University have devised an innovative and elegantly concise algorithm that can efficiently solve systems of linear equations that are critical to such important computer applications as image processing, logistics and scheduling problems, and recommendation systems.

(The original CMU press release, which has a few more Web links, is here.)

You probably learned to solve simple linear systems in school.  For example, if we consider the following system, which has two equations in two unknowns,

2 x + y = 10

x  +  3 y = 15

a little manipulation will give us the answer x=3, y=4.  Small systems like this are easy, but real applications may in some cases have thousands or even millions of equations and variables.

One of the best general-purpose algorithms for solving linear systems is Gaussian elimination; its running time is O(n3). That is, for a problem with ‘n’ equations, the running time is proportional to n3 as n gets large.  Although the new algorithm is specialized, for a class of systems called symmetric diagonally dominant [SDD], it is much faster, with a running time O(n [log(n)]2).   This is an important result, since SDD systems turn up in many different application areas.  For example, the movie recommendation system used by Netflix uses an SDD system, as do many applications in image processing and engineering.  There are other algorithms that are faster than Gaussian elimination, but none as fast as this one.

The team’s approach to solving SDD systems is to first solve a simplified system that can be done rapidly and serve as a “preconditioner” to guide iterative steps to an ultimate solution. To construct the preconditioner, the team uses new ideas from spectral graph theory, such as spanning tree and random sampling.

The paper is being presented at the annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), Oct. 23-36 in Las Vegas, and can be downloaded here [PDF].

## More on Ubuntu 10.10

October 25, 2010

Back on October 10, I posted a note about the release of Ubuntu Linux 10.10, code named “Maverick Meerkat”.   Ars Technica now has a fairly lengthy review of the new release.  The review is primarily descriptive (rather than being a comparison to other systems such as OS X or Windows).  It gives a fairly comprehensive overview of what’s in the new release; it will probably be especially helpful to current Ubuntu users who are looking to update their systems, but there is useful information for the person new to Linux, also.

One component of the new release that is discussed in the review is the Unity desktop interface for netbooks.  This may be of special interest now: Mark Shuttleworth, CEO of Canonical Ltd, the corporate sponsor of the Ubuntu distribution, has announced plans to use Unity as the default interface for all versions of the distribution, beginning with the 11.04 release next spring.

## Speedy New LSE Trading System

October 25, 2010

A little over a year ago, I wrote about the London Stock Exchange’s [LSE]  plan to dump its existing trading system, TradElect, which is based on Microsoft’s Windows and .NET framework, and replace it with a new system based on Linux.  That new system, called Millenium Exchange, is now in its final phase of testing, and is scheduled to go live on November 1.   The LSE decided on the change because of performance and reliability problems with the TradElect system.

The new system has already been put to use in the LSE’s Turquoise electronic “dark pool” trading environment; according to an article in ComputerWorld UK, the new system has set a new speed record for processing trades.

The London Stock Exchange has said its new Linux-based system is delivering world record networking speed, with 126 microsecond trading times.

David Lester, CEO of Turquoise, said that alongside the 126 microsecond average latency, 99 percent of orders would be processed within 210 microseconds, and only 0.1 percent will take longer than 400 microseconds.

Trading speed has become a major competitive issue between the various stock exchanges, because of the rise of automated electronic trading systems.   (Whether these systems are an entirely good thing is another matter.)  With the old system, the LSE had been criticized for sluggish performance and questionable reliability.  At least on the dimension of speed, the new system appears to give the LSE a leg up on its rivals.

Switching to a new system like this is, of course, a complex undertaking.  The LSE has already held one “dress rehearsal” test of the system with its ~300 member firms.   Two more tests of this type are planned before the scheduled live date, November 1; the LSE says that the cut-over might be delayed by a fortnight if member firms experience problems.  Unofficial reports say that the core Millenium system worked just fine in the tests.