4 ms·

IEEE Guest Editors' Introduction: The Top Algorithms

7 points by kumarski 13y ago

bediger4000 13y ago
With each of these algorithms or approaches, there is a person or group receiving credit for inventing or discovering the method. Of course, the reality is that there is generally a culmination of ideas that leads to a method. Wait, whaaaat?!? As our intellectual property law trends more towards giving a single entity credit for any given invention, we have the IEEE saying that algorithms are essentially just a product of their times?
signa11 13y ago
just wanted to add wikipedia references to those articles here for faster lookups: 01. Metropolis Algorithm for Monte Carlo: http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_alg... 02. Simplex Method for Linear Programming: http://en.wikipedia.org/wiki/Simplex_algorithm http://en.wikipedia.org/wiki/Simplex_algorithm 03. Krylov Subspace Iteration Methods: http://en.wikipedia.org/wiki/Krylov_subspace http://en.wikipedia.org/wiki/Krylov_subspace 04. The Decompositional Approach to Matrix Computations: http://dl.acm.org/citation.cfm?id=615766 http://dl.acm.org/citation.cfm?id=615766 05. The Fortran Optimizing Compiler : http://www.ibiblio.org/pub/languages/fortran/ch1-1.html http://www.ibiblio.org/pub/languages/fortran/ch1-1.html (just the starting page) 06. QR Algorithm for Computing Eigenvalues : http://en.wikipedia.org/wiki/QR_algorithm http://en.wikipedia.org/wiki/QR_algorithm 07. Quicksort Algorithm for Sorting : http://en.wikipedia.org/wiki/Quicksort http://en.wikipedia.org/wiki/Quicksort 08. Fast Fourier Transform : http://en.wikipedia.org/wiki/Fast_Fourier_transform http://en.wikipedia.org/wiki/Fast_Fourier_transform 09. Integer Relation Detection : http://en.wikipedia.org/wiki/Integer_relation_algorithm http://en.wikipedia.org/wiki/Integer_relation_algorithm 10. Fast Multipole Method : http://en.wikipedia.org/wiki/Fast_multipole_method http://en.wikipedia.org/wiki/Fast_multipole_method have fun !
DonGateley 13y ago
The article is a little short on attributions. John Cocke and Fran Allen are responsible for the optimizing Fortran compiler and their technical report at IBM detailing and justifying the transformations is still excellent reading. John subsequently invented Risc architecture and supervised the construction of the first machine because his work with the compiler had led him to the conclusion that, for compilers, existing instruction sets were all wrong. It ultimately became the Power PC architecture. John also won the Turing award for his many contributions to computer science which didn't exist as a field until long after he began. Or when I began for that matter. :-) Cooley and Tukey invented the fast Fourier transform although I've read that Gauss had preceded them with little notice. When I was in school it was still called the Cooley-Tukey algorithm and considered a bit of a miracle. FFT rolled off the tongue a bit easier and supplanted the name. At that time the term Digital Signal Processing also remained in the future.

7 points by kumarski 13y ago

With each of these algorithms or approaches, there is a person or group receiving credit for inventing or discovering the method. Of course, the reality is that there is generally a culmination of ideas that leads to a method. Wait, whaaaat?!? As our intellectual property law trends more towards giving a single entity credit for any given invention, we have the IEEE saying that algorithms are essentially just a product of their times?

signa11 13y ago

just wanted to add wikipedia references to those articles here for faster lookups: 01. Metropolis Algorithm for Monte Carlo: http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_alg... 02. Simplex Method for Linear Programming: http://en.wikipedia.org/wiki/Simplex_algorithm http://en.wikipedia.org/wiki/Simplex_algorithm 03. Krylov Subspace Iteration Methods: http://en.wikipedia.org/wiki/Krylov_subspace http://en.wikipedia.org/wiki/Krylov_subspace 04. The Decompositional Approach to Matrix Computations: http://dl.acm.org/citation.cfm?id=615766 http://dl.acm.org/citation.cfm?id=615766 05. The Fortran Optimizing Compiler : http://www.ibiblio.org/pub/languages/fortran/ch1-1.html http://www.ibiblio.org/pub/languages/fortran/ch1-1.html (just the starting page) 06. QR Algorithm for Computing Eigenvalues : http://en.wikipedia.org/wiki/QR_algorithm http://en.wikipedia.org/wiki/QR_algorithm 07. Quicksort Algorithm for Sorting : http://en.wikipedia.org/wiki/Quicksort http://en.wikipedia.org/wiki/Quicksort 08. Fast Fourier Transform : http://en.wikipedia.org/wiki/Fast_Fourier_transform http://en.wikipedia.org/wiki/Fast_Fourier_transform 09. Integer Relation Detection : http://en.wikipedia.org/wiki/Integer_relation_algorithm http://en.wikipedia.org/wiki/Integer_relation_algorithm 10. Fast Multipole Method : http://en.wikipedia.org/wiki/Fast_multipole_method http://en.wikipedia.org/wiki/Fast_multipole_method have fun !

DonGateley 13y ago

The article is a little short on attributions. John Cocke and Fran Allen are responsible for the optimizing Fortran compiler and their technical report at IBM detailing and justifying the transformations is still excellent reading. John subsequently invented Risc architecture and supervised the construction of the first machine because his work with the compiler had led him to the conclusion that, for compilers, existing instruction sets were all wrong. It ultimately became the Power PC architecture. John also won the Turing award for his many contributions to computer science which didn't exist as a field until long after he began. Or when I began for that matter. :-) Cooley and Tukey invented the fast Fourier transform although I've read that Gauss had preceded them with little notice. When I was in school it was still called the Cooley-Tukey algorithm and considered a bit of a miracle. FFT rolled off the tongue a bit easier and supplanted the name. At that time the term Digital Signal Processing also remained in the future.