Veni, Divisi, Vici
Catherine C. McGeoch · American Mathematical Monthly · 1995
How do you invent a new algorithm for a computational problem? The first source of inspiration is humankind, of course: to develop a sorting algorithm, think about how you would sort a deck of playing cards, or a stack of 200 student papers, and try to write that process down formally. But introspection is not enough. The greatest algorithmic discoveries represent surprising departures from the usual way of doing things. One of the early landmark events in computer science was Volker Strassen's 1968 discovery that two n x n matrices could be multiplied using fewer than n3 scalar multiplications. His algorithm uses 7n'°g276n2 scalar arithmetic operations where log27 is about 2.808. Strassen's algorithm is an example of the divide-and-conquer paradigm: to solve a problem efficiently, divide it into independent subproblems, recursively solve the subproblems, and recombine the subproblem solutions. Computer scientists have come to recognize about a half-dozen algorithm paradigms, which can guide the search for new algorithms much in the way that Polya's heuristic strategies (Analogy, Decomposition, Generalization, Induction, etc.) can guide the search for new mathematical results [3]. This column will present Strassen's method and a general technique for analyzing divide-and-conquer algorithms.