Abstract

Myself, Steve Linton and Jon Thackray have been working for nearly 10 years on a fairly major overhaul of matrix multiplication and Gaussian elimination over finite fields of order (mainly) up to 1,000 or so, aiming to make good use of modern processors – specifically the ubiquitous x86-64 from Intel and AMD . With clock speeds approaching a plateau we now need to use multiple cores, utilize the various levels of cache to reduce memory bandwidth demands, use the vector registers and avoid unpredictable branches, but by doing all of these, speed improvements in excess of a factor of 100 are readily obtained over the methods of a couple of decades ago.
This talk will explain some of the changes in technique that are needed to achieve this – both algorithmic and technological – that seem quite radical at the moment, but which I expect to become more mainstream in future.