Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

closed as too broad by Steven Landsburg, Chris Godsil, Ricardo Andrade, Lucia, S. Carnahan Oct 5 at 3:53

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

7  
Community wiki at the very least. –  Loop Space Jun 9 '10 at 8:24
2  
Roland, but why do you wish to collect those important algorithms? (You do not indicate your motivation! :-) ) –  Wadim Zudilin Jun 9 '10 at 10:56
4  
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". –  S. Carnahan Jun 9 '10 at 12:43
1  
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. –  Charles Stewart Jun 9 '10 at 13:00

7 Answers 7

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.

share|improve this answer
    
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. –  Roland Bacher Jun 9 '10 at 9:37
    
Strange to ignore totally the area of cryptography. The emphasis is obviously on "scientific computing". –  Charles Matthews Jun 9 '10 at 10:05
    
Integer Relation Detection (1977) precedes LLL (1982, not included). How queer! :-) –  Robin Chapman Jun 9 '10 at 10:13
1  
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. –  Roland Bacher Jun 9 '10 at 12:13
1  
Wadim: Greedy algorithm! –  Victor Protsak Jun 9 '10 at 18:44

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)
share|improve this answer
    
"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 –  Bruce Arnold Jun 16 '10 at 16:13

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

share|improve this answer
    
Fixed (should have been Vorobjov, and updated Poincar\'e with correct accent). Thank you! –  Grant Olney Passmore Jun 9 '10 at 13:45
    
No problems! Is there a simple place where the collection of these algorithms is described? –  Wadim Zudilin Jun 9 '10 at 13:49
    
Thankfully, yes! The monumental tome `Algorithms in Real Algebraic Geometry' by Basu-Pollack-Roy is invaluable. A review is here ( math.tamu.edu/~rojas/bpr.pdf ) and with the 2nd edition, they've made it freely available online ( perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.html ). I refer to it daily! –  Grant Olney Passmore Jun 9 '10 at 14:05

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
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
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.' –  Grant Olney Passmore Jun 9 '10 at 14:37

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

share|improve this answer

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