PIMS-Shell Lunchbox Lecture

  • Date: 09/25/2008

Dr. Vassil Dimitrov, Schulich School of Engineering, University of Calgary


Calgary Place Tower (Shell)

On the Complexity of Some Easy and Not-So-Easy Problems

The multiplication of two integers is a fundamental computational problem, which, due to its obvious importance, has been a subject of a large amount of research concerning efficient impementations. The asymptotically fastest known algorithm is due to Schonhage and Strassen. While time forms a major part of the cost of computing, the resource of storage space should also be considered in an analysis of the computational complexity of a problem such as integer multiplication. Interestingly enough, there are many unknown things that have to be unveiled, despite the simplicity of this problem. For example, if one implements the multiplications as a succession of additions and binary shift operations, how many additions, on average, are required? What about the worst cases? If one can use not only additions, but additions and subtractions, would that make a considerable difference?Addressing all these issues is of obvious importance for people working in the area of signal and image processing, where designing special purpose hardware for computationally intensive problems requires extremely fast multipliers. Another possible application is in the field of compiler optimization. At the end of the talk some easy-to-pose but different-to-answer open problems will be considered.



Other Information: 
Calgary Place Tower I (330 5th Avenue SW), Room 1116 and 1118 The Pacific Institute for the Mathematical Sciences is grateful for the support of Shell Canada Limited, Alberta Advanced Education and Technology, and the University of Calgary for their support of this series of lectures.