High Performance Algorithm Engineering for Large-scale Problems


Algorithm engineering refers to the process required to transform a pencil-and-paper algorithm into a robust, efficient, well tested, and easily usable implementation. Thus it encompasses a number of topics, from modeling cache behavior to the principles of good software engineering; its main focus, however, is experimentation. In that sense, it may be viewed as a recent outgrowth of Experimental Algorithmics [14], which is specifically devoted to the development of methods, tools, and practices for assessing and refining algorithms through experimentation. The ACM Journal of Experimental Algorithmics (JEA), at URL www.jea.acm.org, is devoted to this area. High-performance algorithm engineering [2] focuses on one of the many facets of algorithm engineering: speed. The high‐performance aspect does not immediately imply parallelism; in fact, in any highly parallel task, most of the impact of high‐performance…

Encyclopedia of Algorithms - 2008 Edition