トップ|php

20世紀を変えた10のアルゴリズム

1946年 モンテカルロ法

Monte Carlo method
John von Neumann;Stan Ulam;and Nick Metropolis

1947年 George Dantzig

simplex method for linear programming
RAND Corporation

1950年 クリロフ部分空間反復法

Krylov subspace iteration methods

1951年 行列の分解アプローチ

decompositional approach to matrix computations

1957年 Fortranの開発

Fortran optimizing compiler

1959-61年 QR法

QR algorithm
J.G.F. Francis

1962年 クイックソート

Quicksort
Tony Hoare

1965年 フーリエ変換

fast Fourier transform
James Cooley

1977年 整数関係探索

integer relation detection algorithm
Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer relation detection algorithm. The problem is an old one: Given a bunch of real numbers, say x1, x2, . . . , xn, are there integers a1, a2, . . . , an (not all 0) for which a1x1 + a2x2 + . . . + anxn = 0? For n = 2, the venerable Euclidean algorithm does the job, computing terms in the continued-fraction expansion of x1/x2. If x1/x2 is rational, the expansion terminates and, with proper unraveling, gives the “smallest” integers a1 and a2. If the Euclidean algorithm doesn’t terminate or if you simply get tired of computing it then the unraveling procedure at least provides lower bounds on the size of the smallest integer relation. Ferguson and Forcade’s generalization, although much more difficult to implement (and to understand), is also more powerful. Their detection algorithm, for example, has been used to find the precise coefficients of the polynomials satisfied by the third and fourth bifurcation points, B3 = 3.544090 and B4 = 3.564407, of the logistic map. (The latter polynomial is of degree 120; its largest coefficient is 25730.) It has also proved useful in simplifying calculations with Feynman diagrams in quantum field theory.

1987年 多体シミュレーションのための高速算法

fast multipole algorithm(FMA)
参考:http://www-unix.mcs.anl.gov/~csverma/top10.pdf

参考:http://slashdot.jp/askslashdot/comments.pl?sid=383961&threshold=-1&commentsort=3&mode=thread&cid=1268118