Top 10 algorithms of 20th century

QR decomposition 

🔟 Top Algorithms – Importance, Simple Uses, Origins

---

1. Metropolis Algorithm (for Monte Carlo Simulation)

• 🧠 What it does: Randomly explores complex systems to simulate equilibrium states (like particle systems).

• 🔧 Simple use: Simulating gas molecules bouncing in a box.

• 💡 How it started: Developed in 1953 at Los Alamos by Metropolis et al. for studying atomic particles in thermodynamics. Introduced a clever accept/reject rule to simulate thermal systems.

---

2. Simplex Method (Linear Programming)

• 🧠 What it does: Finds the best solution under linear constraints (optimization).

• 🔧 Simple use: Maximize profits given constraints (like factory output).

• 💡 How it started: George Dantzig (1947) realized that linear programs could be solved by walking along the edges of a geometric shape (a polytope) to its optimal vertex.

---

3. Krylov Subspace Iteration Methods

• 🧠 What it does: Solves large linear systems or eigenvalue problems iteratively by building solutions from a subspace.

• 🔧 Simple use: Simulating airflow in aerodynamics using sparse matrix systems.

• 💡 How it started: Based on Krylov’s idea (1931) of using matrix powers to generate a subspace that captures the essence of the problem, later refined into practical iterative methods like GMRES and Lanczos.

---

4. Matrix Decomposition Methods (LU, QR, SVD...)

• 🧠 What it does: Breaks matrices into simpler pieces to solve systems efficiently and stably.

• 🔧 Simple use: Solving systems like Ax = b, or data compression using SVD.

• 💡 How it started: Grew from numerical analysis research—divide complex matrix tasks into smaller, structured problems. Think of it as factoring numbers, but for matrices.

---

5. Fortran Optimizing Compiler

• 🧠 What it does: Automatically optimizes code written in Fortran for faster performance.

• 🔧 Simple use: Making scientific code for weather models or physics simulations run faster.

• 💡 How it started: Built by John Backus and IBM in the 1950s to make high-level language code run as fast as hand-written assembly. Marked a turning point in compiler design.

---

6. QR Algorithm (Eigenvalue Computation)

• 🧠 What it does: Finds eigenvalues and eigenvectors of a matrix efficiently.

• 🔧 Simple use: Computing natural frequencies in structures (engineering).

• 💡 How it started: Independently developed by Francis and Kublanovskaya (1961). It uses QR decomposition repeatedly to diagonalize a matrix.

---

7. Quicksort

• 🧠 What it does: Sorts lists efficiently using divide-and-conquer.

• 🔧 Simple use: Sorting customer records, numbers, or search results.

• 💡 How it started: Invented by Tony Hoare in 1960 after learning Russian and working on machine translation. He devised Quicksort as an elegant recursive way to sort without extra memory.

---

8. Fast Fourier Transform (FFT)

• 🧠 What it does: Transforms data from time to frequency domain super fast.

• 🔧 Simple use: Audio filtering, image compression (like JPEG).

• 💡 How it started: Cooley and Tukey (1965) revived an old idea from Gauss by noticing symmetries in the Discrete Fourier Transform that could speed it up dramatically.

---

9. Integer Relation Detection (PSLQ Algorithm)

• 🧠 What it does: Detects if a real number is a combination of other real numbers with integer coefficients.

• 🔧 Simple use: Discovering hidden mathematical constants or relationships (e.g., formulas involving π or e).

• 💡 How it started: Developed by Ferguson and Bailey in the 1990s for experimental mathematics. It uses lattice-based methods to find integer combinations with very high precision.

---

10. Fast Multipole Method (FMM)

• 🧠 What it does: Speeds up simulations of forces between many particles (e.g., gravity).

• 🔧 Simple use: Simulating how stars in a galaxy move under mutual gravity.

• 💡 How it started: Greengard and Rokhlin (1987) realized that distant particle groups could be approximated, reducing complexity from O(n²) to O(n) or O(n log n) — a breakthrough for physics and N-body problems.

---

🧾 Summary Table

#	Algorithm	Core Use	Key Idea / Originator
1	Metropolis Algorithm	Simulate complex systems	Probabilistic sampling (Metropolis)
2	Simplex Method	Linear optimization	Walk along edges of a polytope
3	Krylov Subspace Methods	Large matrix systems	Iterative subspace solution
4	Matrix Decompositions	Linear algebra simplification	LU, QR, SVD breakdown
5	Fortran Compiler	Optimize scientific code	Auto code optimization (Backus)
6	QR Algorithm	Find eigenvalues	Iterative QR decomposition
7	Quicksort	Efficient sorting	Divide-and-conquer (Hoare)
8	Fast Fourier Transform	Frequency analysis	Recursive DFT (Cooley-Tukey)
9	Integer Relation Detection	Find math relationships	PSLQ algorithm
10	Fast Multipole Method	Particle simulation	Approximate distant effects