Table of Contents
SIAM


A JOURNEY THROUGH THE HISTORY
OF NUMERICAL LINEAR ALGEBRA

Claude BREZINSKI, Gérard MEURANT
and Michela REDIVO-ZAGLIA

SIAM
2022
ISBN 978-1-611977-22-6
xx + 792 pages



This volume describes the history of numerical methods proposed for solving linear algebra problems, from antiquity to the present day. The authors focus on methods for linear systems of equations and eigenvalue problems and describe the interplay between numerical methods and the computing tools available at the time. The second part of the book consists of 78 biographies of important contributors to the field.

  • Table of Contents (PDF) [download]

    Table of Contents

    0/ Introduction [TOC]

    

    1/ Matrices and their properties  [TOC]
    

    1.1 The birth of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
1.2 Matrix rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Ill-conditioning and condition numbers. . . . . . . . . . . . . . . . . . . . . 16
1.5 The Schur complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24
1.6 Matrix mechanics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7 Lifetimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    

    2/ Elimination methods for linear systems  [TOC]
    

    2.1 Antiquity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Ancient China . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Ancient Greece . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39
2.4 Ancient India . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5 Ancient Persia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42
2.6 The Middle Ages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7 The 16th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45
2.8 The 17th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48
2.9 The 18th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52
2.10 The 19th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.11 The 20th and 21st centuries . . . . . . . . . . . . . . . . . . . . . . . . . .67
2.12 Lifetimes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

    

    3/Determinants  [TOC]
    

    3.1 The 17th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .99
3.2 The 18th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.3 The 19th century. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .108
3.4 The 20th century . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.5 Lifetimes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

    

    4/ Matrix factorizations and canonical forms  [TOC]
    

    4.1 LU factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.2 QR factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.3 Singular value factorization . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.4 Polar factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142
4.5 CS factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.6 Jordan canonical form . . . . . . . . . . . . . . . . . . . . . . . . . . . . .146
4.7 Frobenius canonical form . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.8 Schur factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .151
4.9 Spectral factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.10 WZ factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152
4.11 Lifetimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

    

    5/ Iterative methods for linear systems  [TOC]
    

    5.1 Classical methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155
5.2 Alternating direction methods . . . . . . . . . . . . . . . . . . . . . . . . .178
5.3 Semi-iterative methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.4 Projection methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.5 Asynchronous methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.6 The Institute for Numerical Analysis . . . . . . . . . . . . . . . . . . . . . 197
5.7 CG, Lanczos, and other methods . . . . . . . . . . . . . . . . . . . . . . . . 201
5.8 Krylov methods for nonsymmetric linear systems . . . . . . . . . . . . . . . . 217
5.9 The method of moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . .246
5.10 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
5.11 Domain decomposition methods . . . . . . . . . . . . . . . . . . . . . . . . .265
5.12 Multigrid and multilevel methods . . . . . . . . . . . . . . . . . . . . . . .268
5.13 Lifetimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

    

    6/ Eigenvalues and eigenvectors  [TOC]
    

    6.1 The early years . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .275
6.2 The Rayleigh quotient . . . . . . . . . . . . . . . . . . . . . . . . . . . . .281
6.3 Localization of eigenvalues and the field of values . . . . . . . . . . . . . . 285
6.4 Where does the name “eigenvalue” come from? . . . . . . . . . . . . . . . . . .288
6.5 Using the characteristic polynomial . . . . . . . . . . . . . . . . . . . . . .289
6.6 The power and inverse iterations . . . . . . . . . . . . . . . . . . . . . . . 293
6.7 Morris’ escalator method . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
6.8 The methods of Lanczos and Arnoldi . . . . . . . . . . . . . . . . . . . . . . 297
6.9 The methods of Givens and Householder . . . . . . . . . . . . . . . . . . . . .308
6.10 The qd and LR algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .308
6.11 The QR algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .311
6.12 Tridiagonal matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . .315
6.13 The Jacobi-Davidson method . . . . . . . . . . . . . . . . . . . . . . . . . .316
6.14 Other methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
6.15 Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
6.16 Lifetimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

    

    7/Computing machines  [TOC]
    

    7.1 The beginnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
7.2 Logarithms and slide rules . . . . . . . . . . . . . . . . . . . . . . . . . . 324
7.3 Mechanical calculators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
7.4 Electric calculators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
7.5 The beginning of automatic computers. . . . . . . . . . . . . . . . . . . . . .330
7.6 Tabulating machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .332
7.7 The early digital computers . . . . . . . . . . . . . . . . . . . . . . . . . .334
7.8 The 1940s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335
7.9 The 1950s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .338
7.10 The 1960s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
7.11 The 1970s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
7.12 The 1980s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
7.13 The 1990s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
7.14 The 2000s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
7.15 The rise of microprocessors . . . . . . . . . . . . . . . . . . . . . . . . . 343
7.16 Parallel computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345

    

    8/ Software for numerical linear algebra   [TOC]
    

    8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
8.2 Programming languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . .358
8.3 The Handbook for Automatic Computing . . . . . . . . . . . . . . . . . . . . . 361
8.4 BLAS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .364
8.5 EISPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .367
8.6 LINPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .367
8.7 LAPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
8.8 Other libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .370
8.9 Commercial libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
8.10 Libraries for parallel computers . . . . . . . . . . . . . . . . . . . . . . .375
8.11 Netlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .379
8.12 MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .379

    

    9/Miscellaneous topics  [TOC]
    

    9.1 Tridiagonal matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
9.2 Fast solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
9.3 Hankel and Toeplitz matrices . . . . . . . . . . . . . . . . . . . . . . . . . 385
9.4 Functions of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . .387
9.5 Ill-posed problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
9.6 Matrix equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394

    

    10/ Lives and works  [TOC]
    

    10.1 Alexander C. Aitken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
10.2 Mieczysław Altman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
10.3 Charles Babbage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
10.4 Tadeusz Banachiewicz . . . . . . . . . . . . . . . . . . . . . . . . . . . . .410
10.5 Friedrich L. Bauer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .413
10.6 Eugenio Beltrami . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .414
10.7 Augustin-Louis Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
10.8 Arthur Cayley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
10.9 Lamberto Cesari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
10.10 Françoise Chatelin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
10.11 Pafnuty L. Chebyshev . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
10.12 André L. Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .435
10.13 Gianfranco Cimmino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
10.14 Gabriel Cramer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
10.15 Seymour R.Cray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
10.16 Prescott D. Crout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .445
10.17 Myrick H. Doolittle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .446
10.18 Paul S. Dwyer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .449
10.19 Leonhard Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
10.20 Radii P. Fedorenko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
10.21 Roger Fletcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
10.22 George E. Forsythe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
10.23 Leslie Fox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
10.24 Ferdinand G. Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
10.25 Noel Gastinel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .464
10.26 Johann C.F. Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .466
10.27 Hilda Geiringer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .471
10.28 Semyon A. Gerschgorin . . . . . . . . . . . . . . . . . . . . . . . . . . . .473
10.29 Wallace Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
10.30 Gene H. Golub . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .476
10.31 William R. Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . .478
10.32 Richard J. Hanson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .481
10.33 Emilie V. Haynsworth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
10.34 Peter Henrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .484
10.35 Karl Hessenberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .485
10.36 Magnus R. Hestenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
10.37 Alston S. Householder . . . . . . . . . . . . . . . . . . . . . . . . . . . .488
10.38 Carl G.J. Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
10.39 Camille Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
10.40 Stefan Kaczmarz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .496
10.41 Leopold Kronecker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .498
10.42 Alexei N. Krylov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
10.43 Vera Kublanovskaya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
10.44 Joseph-Louis Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . .508
10.45 Edmond Laguerre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .511
10.46 Cornelius Lanczos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .515
10.47 Pierre-Simon Laplace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
10.48 Charles L. Lawson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .523
10.49 Adrien-Marie Legendre . . . . . . . . . . . . . . . . . . . . . . . . . . . .525
10.50 Gottfried W. von Leibniz . . . . . . . . . . . . . . . . . . . . . . . . . . 528
10.51 Ada Lovelace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
10.52 John von Neumann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
10.53 Isaac Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
10.54 Willgodt T. Odhner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
10.55 Alexander M. Ostrowski . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
10.56 Oskar Perron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
10.57 Lewis F. Richardson . . . . . . . . . . . . . . . . . . . . . . . . . . . . .546
10.58 Reuben L. Rosenberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . .548
10.59 Heinz Rutishauser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .550
10.60 Issai Schur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .552
10.61 Hermann Schwarz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .554
10.62 Franz Schweins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
10.63 Philipp von Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
10.64 Richard V. Southwell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
10.65 Philip B. Stein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .563
10.66 Eduard L. Stiefel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .565
10.67 James J. Sylvester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
10.68 Olga Taussky-Todd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .574
10.69 Charles-Xavier Thomas de Colmar . . . . . . . . . . . . . . . . . . . . . . .576
10.70 John Todd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .578
10.71 Otto Toeplitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .581
10.72 Alan M. Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
10.73 Alexandre-Théophile Vandermonde . . . . . . . . . . . . . . . . . . . . . . .589
10.74 Richard S. Varga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
10.75 Karl Weierstrass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
10.76 James H. Wilkinson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
10.77 David M. Young . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
10.78 Konrad Zuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .602

    

    References  [TOC]
    
There are 3344 references.