Skip to main content    

An official website of the United States government

Here’s how you know

**Official websites use .gov**              A **.gov** website belongs to an official government organization in the United States.            

**Secure .gov websites use HTTPS**              A **lock** (  LockA locked padlock) or **https://** means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.            

https://www.nist.gov/mathematics-statistics/nbs-discovers-one-centurys-top-10-algorithms

            -  Topics  -  All Topics 
-  Advanced communications 
-  Artificial intelligence 
-  Bioscience 
-  Buildings and construction 
-  Chemistry 
-  Climate 
-  Cybersecurity 
-  Electronics 
-  Energy 
-  Environment 
-  Fire 
-  Forensic science 
-  Health 
-  Information technology 
-  Infrastructure 
-  Manufacturing 
-  Materials 
-  Mathematics and statistics 
-  Metrology 
-  Nanotechnology 
-  Neutron research 
-  Performance excellence 
-  Physics 
-  Public safety 
-  Resilience 
-  Standards 
-  Transportation 
 
            -  Publications 
            -  Labs & Major Programs  -  Laboratories    -  Communications Technology Laboratory 
  -  Engineering Laboratory 
  -  Information Technology Laboratory 
  -  Material Measurement Laboratory 
  -  Physical Measurement Laboratory 
-  User Facilities    -  NIST Center for Neutron Research 
  -  CNST NanoFab 
-  Research Test Beds 
-  Research Projects 
-  Tools & Instruments 
-  Major Programs    -  Baldrige Performance Excellence Program 
  -  CHIPS for America Initiative 
  -  Manufacturing Extension Partnership (MEP) 
  -  Office of Advanced Manufacturing 
  -  Special Programs Office 
  -  Technology Partnerships Office 
 
            -  Services & Resources  -  Standards and Measurements    -  Calibration Services 
  -  Laboratory Accreditation (NVLAP) 
  -  Quality System 
  -  Standard Reference Materials (SRMs) 
  -  Standards.gov 
  -  Time Services 
  -  Office of Weights and Measures 
-  Software 
-  Data    -  Chemistry WebBook 
  -  National Vulnerability Database 
  -  Physical Reference Data 
  -  Standard Reference Data (SRD) 
-  Storefront 
-  License & Patents 
-  Computer Security Resource Center (CSRC) 
-  NIST Research Library 
 
            -  News & Events  -  News 
-  Events 
-  Blogs 
-  Feature Stories 
-  Awards 
-  Video Gallery 
-  Image Gallery 
-  Media Contacts 
 
            -  About NIST  -  About Us    -  Leadership 
  -  Organization Structure 
  -  Budget & Planning 
-  Contact Us 
-  Visit 
-  Careers    -  Student programs 
-  Work with NIST 
-  History    -  NIST Digital Archives 
  -  NIST Museum 
  -  NIST and the Nobel 
-  Educational Resources 
 

## Mathematics & Statistics

# NBS Discovers One of the Century’s Top 10 Algorithms

## Share

Facebook

Linkedin

Twitter

Email

## **Date: 1952**

*In 1952 NBS researchers published an algorithm for solving systems of linear equations which would only come to prominence two decades later as a standard method for solving very large sparse systems on supercomputers. It’s impact has been so great that in 1999 one magazine listed it as one of the Top 10 Algorithms of the Century.*

The advent of electronic computers in the middle of the 20th century stimulated a flurry of activity in developing numerical algorithms that could be applied to computational problems much more difficult than those solved in the past, especially algorithms for the solution of linear systems and matrix eigenvalue problems. Such problems arise in nearly all application areas, such as modeling of fluid flows, reservoir engineering, mechanical engineering, semiconductor device analysis, nuclear reaction models, and electric circuit simulation. These matrices can be huge, with millions of unknown quantities to be determined.

 At this time, there were two commonly used types of algorithms for solving linear systems. The first, like Gauss elimination, modified a tableau of matrix entries in a systematic way in order to compute the solution. These methods were finite, but required a rather large amount of computational effort with work growing as the cube of the number of unknowns. The second type of algorithm used “relaxation techniques” to develop a sequence of approximations converging to the solution. Although convergence was often slow, these algorithms could be terminated, often with a reasonably accurate solution estimate, whenever the human “computers” ran out of time. The ideal algorithm would be one that had finite termination but, if stopped early, would give a useful approximate solution. 

Magnus Hestenes of the NBS Institute for Numerical Analysis and Eduard Stiefel, a visitor from ETH Zurich,  succeeded in developing an algorithm with exactly these characteristics, the method of conjugate gradients [2]. The algorithm garnered considerable early attention but went into eclipse in the 1960s as naive implementations were unsuccessful on some of the ever-larger problems that were being attempted. In the early 1970s there was renewed attention to the algorithm, and since then it has been an intense topic of research. Today it is the standard algorithm for solving linear systems involving large, sparse, symmetric (or Hermitian) matrices.

Today the conjugate gradient method and its many variants are classified under the term Krylov Subspace Iteration, and this paper describes the first of these methods to solve linear systems. In 1999,*Computing in Science and Engineering*, a publication of the IEEE Computer Society and the American Institute of Physics, named Krylov Subspace Iteration as one of the Top 10 Algorithms of the Century [3], citing in particular the pioneering work of Hestenes and Stiefel, along with Cornelius Lanczos, another NBS/INA researcher. 

Credit:

*Credit: By Pleyer Photo / ETH Zürich - ETH-Bibliothek Zürich, Bildarchiv, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=8098325*

### References

                  - D. P. O’Leary. Methods of Conjugate Gradients for Solving Linear Systems. In*A Century of Excellence in Measurements, Standards, and Technology* (D. R. Lide, ed.), NIST Special Publication 958, 2001.
                  - Magnus R. Hestenes and Eduard Stiefel, Methods of Conjugate Gradients for Solving Linear Systems, Journal of Research of the National Bureau of Standards 49****(1952), 409-436.
                  - Top 10 Algorithms of the Century, Computing in Science and Engineering 2 (1), (2000).

Information technologyMathematics and statistics

### HEADQUARTERS

301-975-2000

Webmaster | Contact Us | Our Other Offices

TwitterFacebookLinkedInInstagramYouTubeGiphyRSS FeedMailing List

Feedback

            -  Site Privacy 
            -  Accessibility 
            -  Privacy Program 
            -  Copyrights 
            -  Vulnerability Disclosure 
            -  No Fear Act Policy 
            -  FOIA 
            -  Environmental Policy 
            -  Scientific Integrity 
            -  Information Quality Standards 
            -  Commerce.gov 
            -  Science.gov 
            -  USA.gov 
            -  Vote.gov