Multilinear Algebra and Chess Endgames
Lewis Stiller · 1997
This article has three chief aims: (1) To show the wide utility of multilinear algebraic formalism for high-performance computing. (2) To describe an application of this formalism in the analysis of chess endgames, and results obtained thereby that would have been impossible to compute using earlier techniques, including a win requiring a record 243 moves. (3) To contribute to the study of the history of chess endgames, by focusing on the work of Friedrich Amelung (in particular his apparently lost analysis of certain six-piece endgames) and that of Theodor Molien, one of the founders of modern group representation theory and the first person to have systematically numerically analyzed a pawnless endgame. 1. Introduction Parallel and vector architectures can achieve high peak bandwidth, but it can be difficult for the programmer to design algorithms that exploit this bandwidth efficiently. Application performance can depend heavily on unique architecture features that complicate the design of portable code [Szymanski et al. 1994; Stone 1993]. The work reported here is part of a project to explore the extent to which the techniques of multilinear algebra can be used to simplify the design of highperformance parallel and vector algorithms [Johnson et al. 1991]. The approach is this: • Define a set of fixed, structured matrices that encode architectural primitives of the machine, in the sense that left-multiplication of a vector by this matrix is efficient on the target architecture. • Formulate the application problem as a matrix multiplication. • Factor the matrix corresponding to the application in terms of the fixed matrices using addition, tensor product, and matrix multiplication as combining operators. • Generate code from the matrix factorization.