Month: November 1998

One week after DeepMind revealed an algorithm for multiplying numbers more efficiently, researchers have an even better way to carry out the task.

Multiplying numbers is a common computational problem

A pair of researchers have found a more efficient way to multiply grids of numbers, beating a record set just a week ago by the artificial intelligence firm DeepMind.

The company revealed on 5 October that its AI software had beaten a record that had stood for more than 50 years for the matrix multiplication problem – a common operation in all sorts of software where grids of numbers are multiplied by each other. DeepMind’s paper revealed a new method for multiplying two five-by-five matrices in just 96 multiplications, two fewer than the previous record.

Jakob Moosbauer and Manuel Kauers at Johannes Kepler University Linz in Austria were already working on a new approach to the problem prior to that announcement.

Their approach involves running potential multiplication algorithms through a process where multiple steps in the algorithm are tested to see if they can be combined.

“What we do is, we take an existing algorithm and apply a sequence of transformations that at some point can lead to an improvement. Our technique works for any known algorithm, and if we are lucky, then [the results] need one multiplication less than before,” says Moosbauer.

After DeepMind published its breakthrough, Moosbauer and Kauers used their approach to improve on DeepMind’s method, slicing off another step to set a new record of 95 multiplications. They have published the proof in a pre-print paper, but haven’t yet released details of the approach they used to find improvements on previous methods.

“We wanted to publish now to be the first one out there, because if we can find it in such a short amount of time, there’s quite some risk that we get outdone by someone else again,” says Moosbauer.

The latest paper is entirely focused on five-by-five matrix multiplication, but the method is expected to bring results for other sizes. The researchers say that they will publish details of their technique soon.

Moosbauer says that DeepMind’s approach brought fresh impetus to an area of mathematics that hadn’t been receiving much attention. He hopes that other teams are also now working in a similar vein.

Matrix multiplication is a fundamental computing task used in virtually all software to some extent, but particularly in graphics, AI and scientific simulations. Even a small improvement in the efficiency of these algorithms could bring large performance gains, or significant energy savings.

DeepMind claimed to have seen a boost in computation speed of between 10 and 20 per cent on certain hardware such as an Nvidia V100 graphics processing unit and a Google tensor processing unit v2. But it said that there was no guarantee that similar gains would be seen on everyday tasks on common hardware. Moosbauer says he is sceptical about gains in common software, but that for large and specialised research tasks there could be an improvement.

DeepMind declined a request for an interview about the latest paper, but its researcher Alhussein Fawzi said in a statement: “We’ve been overwhelmed by the incredible reaction to the paper. Our hope was that this work would open up the field of algorithmic discovery to new ideas and approaches. It’s fantastic to see others exploring ideas in this space as well as building on our work so quickly.”

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Matthew Sparkes*

How can you ensure you use the fewest bags when loading your shopping? A dash of maths will help, says Peter Rowlett.

You have heaped your shopping on the supermarket conveyor belt and a friendly member of the checkout staff is scanning it through. Items are coming thick and fast and you would like to get them in as few bags as possible. What is your strategy?

This is an example of an optimisation problem, from an area of maths called operational research. One important question is, what are you trying to optimise? Are you thinking about the weight of the items, or how much space they will take up? Do you guess how many bags you might need and start filling that many, or put everything in one until you need to start another?

We design algorithms to solve packing problems when they come up at a larger scale than your weekly shop, like making better use of warehouse space or fitting boxes into delivery vans. Similar algorithms are used for cutting raw materials with minimal waste and storing data on servers.

Bag-packing algorithms generally involve placing items into a single bag until you get to one that won’t fit because you have hit a maximum weight or size. When necessary, you open a second bag, and each time you reach an item that won’t fit in an existing bag, you start a new one.

If you are filling multiple bags at once, it is likely you will come across an item that could fit in more than one bag. Which do you choose? There is no clear best answer, but different algorithms give different ways to make this decision. We are looking for rules that can be applied without detailed thought. You might have more subtle requirements, like putting two items in the same bag because they go in the same cupboard at home, but here we want the kind of simple rule a computer program can mindlessly apply to get the most efficient outcomes, using the fewest bags, every time.

One algorithm we could employ is called first fit. For each new item, you look through the bags in the order you opened them, placing the item in the first one it fits in. An advantage is that this is quick to implement, but it can overlook options and end up using more bags than needed.

An alternative that often uses fewer bags overall is called worst fit. When faced with a choice, you look through the currently open bags for the one with the most space and place the item there.

These algorithms work more effectively if you handle the objects in decreasing order – packing the largest or heaviest first will usually need fewer bags.

So now you are armed with a secret weapon for packing: the worst-fit decreasing algorithm. The next time you are in the checkout line, load your bulkiest shopping onto the conveyor belt first, and always put items in the bag with the most space available – it might just help you use fewer bags overall.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Peter Rowlett*