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.


Should You Jettison Java?

October 24, 2010

As I mentioned in my most recent post about Apple’s update of Java for OS X, the company has indicated that java is “deprecated” in the Mac environment.  This has sparked renewed interest in whether the typical end-user machine should have Java installed at all.  Brian Krebs, in his Krebs on Security blog, has for some time recommended that users remove the software from their personal PCs unless they require it for a specific purpose.  More recently, Rob Pegoraro of the Washington Post has, in two recent posts, has looked at getting rid of Java, and suggests that most users have no real need for it.  I’ve now been asked by a few people what I think they should do.

Before I get to a recommendation, it might be useful to review what Java is about.  The Java language and environment was originally designed by Sun Microsystems.  The idea, clever and elegant, was to provide a development tool that allowed programmers to build applications that were “Write Once, Run Everywhere”.  To accomplish this, Java development generates executable code that is not directed at a real hardware platform (like an x86 PC), but at a Java virtual machine, an idealized environment.  That environment, which has certain built-in features for security (the so-called “sandbox”), is provided by the Java run-time system, which emulates the Java virtual machine on each real hardware platform.  (This was not an entirely new idea.  In his multi-volume classic, The Art of Computer Programming, Donald Knuth devised a hypothetical machine called MIX, which he used for pedagogical reasons.)  The design of Java was an attempt to provide a tool through which Web sites could serve small applications to all comers, in a platform-agnostic way.  There are typically two parts of a Java installation: the Java run-time environment [JRE], which implements the Java virtual machine; and a browser plug-in, which handles Java applets served from Web pages.

The case for getting rid of Java is fairly easy to summarize.  There is no question that Java has been a major target for the developers of malware distributed over the Internet; furthermore, there is considerable evidence that these attacks are becoming more and more common.  Java, like Adobe’s Flash and PDF Reader software, is an attractive target for the Bad Guys because it is widely installed across PC and Mac platforms.  And one of the few unquestioned truths of system security is that the only kind of software that never creates security problems is the kind that is not installed on the machine.

So why keep Java?  For some users, who work in enterprise environments, the answer is easy.  Many organizations, especially large ones, have built significant applications using Java.   These users need Java, and presumably their organizations can provide support and update reminders to keep the Java installations up to date.  If you fall into this category, and need Java, then, obviously, you should keep it.

For average users, the picture is a bit murkier.  There may be specific Web sites or applications that you use that require Java.  For example, the on-line crossword puzzles at the Washington Post site are implemented using a Java applet.  The on-line version of Secunia’s Software Inspector, a service the Danish security company  provides to check for missing security patches, also uses Java.  I’m sure there are many other sites that use Java.  If you use these sites, but not too frequently, you might consider installing Java, but disabling the browser plugin except when you need it. (Most attacks are mounted via the plugin.)  In Firefox, you can disable the plugin by selecting Tools / Add-Ons from the main menu, then select the PlugIns tab.  Highlight the Java entry, and then click the Disable button.   To enable the plugin, repeat the process, and click the button (now labeled Enable) again.

Another application that uses Java is the OpenOffice.org productivity suite.  Java is used to implement a number of features of that package, but it is possible to install OpenOffice without Java.  (The OpenOffice site has a list of features that require Java.)   In that case, the features that require Java will not be available, but the package’s other capabilities can still be used.  As I mentioned earlier, most attacks, at least currently, are directed via the browser plug-in, so just having the JRE installed, which is what OpenOffice uses, is probably a tolerable risk.

The really important point, though, is the same for Java as for any other package.  Install it only if you need it; and if you do, take care to keep it up to date.   As always, I will try to post notices here when updates are released.

Update Tuesday, 26 October, 11:15

In Google’s Chrome browser, you can temporarily disable the Java plug-in by typing about:plugins into the URL box.  The resulting page will show you all the plug-ins that are installed.  You can click the Disable link under the Java entry to temporarily turn it off.

So far, I have not been able to find an easy way to temporarily disable Java in the Opera browser.

Apple Updates Java for Mac

October 22, 2010

Last week, I posted a note here about a new release of Java, version 6 update 22, that addressed a bunch of security vulnerabilities, as well as some other miscellaneous bugs.   As I mentioned then, Apple provides its own version of Java for Mac OS X, and typically takes a while to incorporate new updates from Oracle (neé Sun).

Apple has now, with uncharacteristic speed, released two new versions of Java for Mac OS X, for both the 10.5 and 10.6 versions of the OS.   These updates bring the Mac version in line with the current Java version 6, update 22; the update for Mac OS X 10.5 also includes an update of Java version 5 to Update 26.   Further information is available from the links below.

Java for Mac OS X Version 10.5 Update 8

Release Notes

Security Advisory

Java for Mac OS X Version 10.6 Update 3

Release Notes

Security Advisory

You can get the new version using the built-in Software Update function, or you can download an installation package from the Support Downloads page.

Apple has apparently also indicated, on one of its sites for developers, that Java is “deprecated”, and may not be included with Mac OS X at some point.  The question of whether installing Java on end-user machines makes sense is a topic for another post; however, if you have Java installed, I recommend you get this update as soon as you reasonably can.

Monopole Images

October 21, 2010

One of the early posts I made here concerned the search for magnetic monopoles.  Ordinary magnets all have two poles, conventionally labeled North and South; unlike poles attract each other, like poles repel each other.  If you chop a magnet in two, each piece has two poles.  In the classical theory of electricity and magnetism, summarized in Maxwell’s Equations, it is possible to have a free positive or negative electric charge, but the existence of a free North or South pole is ruled out.

The physicist Paul Dirac proposed, in a 1931 paper [PDF here], that magnetic monopoles could exist, and that if they did, it would explain the quantization of electric charge.   Ever since, physicists have been looking for evidence to confirm the existence of such monopoles.  Last fall, the first detection of monopoles was reported, in a neutron-scattering experiment on a crystal of dysprosium titanate at temperatures of less than 2.0 K.

The PhysOrg.com site now has a report that a team of scientists, working at the Paul Scherrer Institute in Switzerland, have captured an image of emerging magnetic monopoles in a magnetic material.

“We have for the first time directly imaged emergent monopoles inside an artificially created magnetic nano-metamaterial consisting of tiny magnets with a size of a couple of hundred nanometers,” explains Professor Braun.

(Professor Hans-Benjamin Braun, from the School of Physics at University College, Dublin, was co-leader of the experimental team.)   The images were made using very high-energy X-rays from the Swiss Light Source at the Paul Scherrer Institute.  The results vindicate Dirac’s predictions about how monopoles emerge; they are attached to Dirac strings, which act to channel magnetic charge.   The research paper [abstract] has been published in the journal Nature Physics.

In addition to capturing these images, this work is noteworthy because, unlike the earlier experimenters, the researchers were able to produce the emergent monopoles at room temperature.  This might in time pave the way for the use of magnetic charge [= monopoles]  for information technology products, which at present use electric charge for data storage.  Using magnetic  charge might lead to significantly reduced power consumption and increased storage density.  Of course, there is a great deal more work to do before this shows up in real products, but it is another example of how quantum mechanics can make surprising and counter-intuitive predictions that turn out to be true.

The Economics of Information Security

October 21, 2010

Bruce Schneier, noted “security guru” and Chief Security Technology Officer of BT, will be the program chair for the 2011 Workshop on the Economics of Information Security (WEIS), to be held June 14-15 at George Mason University, in the Washington DC area.   The Workshop is

…  the leading forum for interdisciplinary scholarship on information security, combining expertise from the fields of economics, social science, business, law, policy and computer science.

Proposals for papers to be presented at the Workshop are invited:

We highlight two key areas of particular focus for this year’s workshop. First, we encourage submissions that consider the design and evaluation of policy solutions for improving information security. Second, given the importance of data-driven decision making, we encourage submissions with empirical components.

The “call for participation” page gives more details; submissions are due in February 2011.


%d bloggers like this: