4
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Roland, but why do you wish to collect those important algorithms? (You do not indicate your motivation! :-) ) $\endgroup$ Jun 9, 2010 at 10:56
  • 5
    $\begingroup$ Sorry, I'm voting to close. The question as stated seems hopelessly broad, like asking for a list of important theorems. I strongly believe that the answer to your last question is "yes". $\endgroup$
    – S. Carnahan
    Jun 9, 2010 at 12:43
  • 1
    $\begingroup$ I think the intent of the question is a good one, but this is a bit of a Celestial Emporium of Benevolent Knowledge approach to categorisation. "Euclid" covers a pretty diverse bunch of things, if it covers any technique found in the Elements. $\endgroup$ Jun 9, 2010 at 13:00

7 Answers 7

6
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Interesting. (1), (9) and (10) should probably be added to my list. (3), (4), (6) and (8) are contained in point (3) and (7) is contained in (8). I am not sure about (5), it should at least be an arbitrary compiler and not necessary Fortran. $\endgroup$ Jun 9, 2010 at 9:37
  • $\begingroup$ Strange to ignore totally the area of cryptography. The emphasis is obviously on "scientific computing". $\endgroup$ Jun 9, 2010 at 10:05
  • $\begingroup$ Integer Relation Detection (1977) precedes LLL (1982, not included). How queer! :-) $\endgroup$ Jun 9, 2010 at 10:13
  • 1
    $\begingroup$ One argument for excluding cryptography: it should not exist in a perfect world! More convincingly, it is not really general purpose but adresses a concrete practical spaect of life. Including it, one has also to accept algorithms used at Wall-Street, algorithms useful for polls etc. $\endgroup$ Jun 9, 2010 at 12:13
  • 1
    $\begingroup$ Wadim: Greedy algorithm! $\endgroup$ Jun 9, 2010 at 18:44
4
$\begingroup$

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)
$\endgroup$
1
  • $\begingroup$ "All algorithms are based on mathematics..." This might be too narrow and poses the question how to define 'algorithm'. Algorithms might also be phenomenons which can be found in some "collective behavior of decentralized, self-organized systems, natural or artificial", for example in communication (see Wikipedia 'Swarm intelligence' [1]). Algorithms in this sense are not based on mathematics, only described by formal systems and sometimes also mimicked by mathematicians (bees algorithm). [1] en.wikipedia.org/wiki/Swarm_intelligence $\endgroup$ Jun 16, 2010 at 16:13
2
$\begingroup$

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. )

$\endgroup$
3
2
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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:

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Though I agree it'd be nice for IPMs to have a separate bullet, in his defense, bullet point 4 does say `and other algorithms using convexity properties.' $\endgroup$ Jun 9, 2010 at 14:37
0
$\begingroup$

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?).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.