What are the most fundamental classes of mathematical algorithms? [closed]

Question

Mathematical means either useful for Mathematics or based on Mathematics.

I guess one has to include the following items:

(1) Euclid and LLL

(2) Newton and variations based on the existence of attracting fixpoints for maps.

(3) Algorithms for linear algebra and, in particular, FFT

(4) Simplex algorithm and other algorithms using convexity properties

(5) Quadrature formula (integration, differential equations etc.)

(6) Factorization (integers, polynomials etc.) and primality proving

(7) Algorithms for computations with Groebner bases.

(8) Sorting and searching

(9) WZ and similar algorithms yielding automated proofs

This list is surely a strict subset of a satisfying answer. Which important (classes of) algorithms are missing? (I guess there must be also be something in probability and perhaps in geometry.)

Let me also specify that I would like the list to contain general-purpose algorithms, not algorithms for specific tasks, like encryption, error-correction, computations of class numbers for number fields etc. I guess, algorithms for elliptic curves are on the boundary and perhaps already slightly outside the list (many of them are however used for integer-factorization and are thus implicitely contained in item (6) of the previous list).

A last question: Are we missing important fundamental algorithms? (This is of course tricky, since we are probably not aware of their potential usefulness). By this I do not mean a algorithm for factorizing integers in polynomial time or an (impossible) algorithm deciding the existence of solutions for arbitrary Diophantine equations but algorithms useful for a large class of problems for which we have presently only case by case tricks.ge

Answer 1

In 100 Digits Challenge: an Extended Review (March 2005) Jon Borwein lists "the 20th century's Top Ten" algorithms:

(1) 1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an effcient way to stumble toward answers to problems that are too complicated to solve exactly.

(2) 1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making.

(3) 1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation.

(4) 1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra.

(5) 1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code.

(6) 1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical.

(7) 1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases.

(8) 1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components.

(9) 1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers.

(10) 1987: Fast Multipole Method. A breakthrough in dealing with the complexity of $n$-body calculations, applied in problems ranging from celestial mechanics to protein folding.

Please refer to the original paper for many examples illustrating Jon's point.

Answer 2

All algorithms are based on mathematics, so if you want the word "mathematical" in your subject to be meaningful you need to be more specific.

Borwein's list in another answer is very heavily numerical. Here's a more combinatorial list, drawn from the topics I would typically cover in an undergraduate introductory algorithms class:

• integer arithmetic (including the elementary algorithms for addition, multiplication, etc but also faster divide-and-conquer multiplication, the equivalence in complexity between multiplication and division, modular exponentiation, and gcds; maybe also matrix multiplication and RSA cryptography)
• sorting (both comparison-based and integer sorting), searching sorted lists, and median finding
• pattern matching in strings
• dynamic programming (longest common subsequence, knapsack and subset sum problems, etc)
• graph algorithms (breadth first search, depth first search, topological ordering, minimum spanning trees, and shortest paths)
• computational geometry (nearest neighbors and convex hulls)

Answer 3

An important class of algorithms which both make use of many fundamental algorithms already appearing in your list and contain significant ideas not reflected yet in your list are algorithms for computation with semialgebraic sets (i.e., algorithms in real algebraic geometry). These algorithms have a very different* flavour than their `counterparts' over algebraically closed fields such as Buchberger's algorithm and related techniques used for Groebner basis computation, Wu's method and other techniques in elimination theory, etc.

Quantifier elimination (effective semialgebraic projection) has always been a central concern in algorithmic real algebraic geometry, so there is perhaps some feeling that these algorithms should be placed under your bullet point (9). But, the wealth of techniques developed in the context of real quantifier elimination are independently interesting and useful outside of the goal of automated proof.

Important algorithms include those which compute:

• Cylindrical Algebraic Decompositions (Collins et al),
• Signed subresultants (Collins et al),
• Betti numbers and Euler-Poincar\'e Characteristic (Basu, Basu-Pollack-Roy),
• Connected component sampling (Basu-Pollack-Roy),
• Roadmaps and Connectedness (Canny, Grigor'ev-Vorobjov, Heintz-Roy-Solerno, Gournay-Risler),
• Positivstellensatz witnesses via Semidefinite programming (Parrilo, Choi, Harrison, Lam, Powers, Woermann et al) [perhaps this is partially covered by your bullet point (4)].

In a certain sense, the properties Collins exploited in defining cylindrical algebraic decompositions have been generalised to what are now called `o-minimal structures,' which has led to a rich and very active research area at the intersection of model theory and semialgebraic and subanalytic geometry (see L. van den Dries' ``Tame Topology and O-minimal Structures'').

(* Though it should be mentioned that fundamental algorithms in real algebraic geometry often make use of fundamental algorithms in classical algebraic geometry. )

Answer 4

What about algorithms coming from graph theory? This seems to be a rich source with lots of real world applications too. To mention just a few

• Minimum weight spanning tree
• Maximum weight matchings
• Colouring algorithms
• Minor-testing

Answer 5

The top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006, which are presented in this article and this subsequent book are the following:

• C4.5,
• k-Means,
• SVM or support vector machines;
• Apriori,
• EM or Expectation-Maximization,
• PageRank,
• AdaBoost or adaptive boosting,
• kNN or k nearest neighbors,
• Naive Bayes,
• CART or classification an regression trees.

See here for further discussions and viewpoints on the importance of more recent algorithms in data mining.

Answer 6

I'm surprised this list doesn't include interior point methods, which (unlike the simplex method) demonstrate that a large class of nonlinear optimization problems (namely, convex SDPs) can be solved in polynomial time.

Answer 7

Two different revolutionary data compressing Ziv and Lempel algorithms: LZ77 and LZ78 (or ZL77 and ZL78, perhaps depending on the selection of a natural language?).