History of mathematicians
In this document we give some information of mathematicians which
work or names are used in the Krylov subspace solvers and
preconditioners part of
the course Numerical challenges in parallel scientific computing
July 18th - August 26th organised as the
CEMRACS 2016 Summer
The course is based on the following books:
Matrix Computations (third edition)
Gene H. Golub and
Charles F. Van Loan
Johns Hopkins University Press, Baltimore, 1996
Templates for the Solution of
Linear Systems: Building Blocks for Iterative Methods
Richard Barrett, Michael Berry, Tony F. Chan, James Demmel,
June Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo,
Charles Romine, and Henk Van der Vorst
SIAM, Philadelphia, 1994
The pdf-file of this book can be obtained in the following way:
Click on the templates/templates.pdf link at the
templates index page.
In order to be able to measure distances with respect to vectors
and matrices we have defined normed spaces. Most of the spaces used
in this course are Banach spaces
Stefan Banach (1892-1945) .
For the vector norms different choices are made. An important class
of norms are the so-called Hölder norms
Otto Ludwig Hölder (1859-1937).
For the special choice p=2 we get the Euclid norm
Euclid ( 325 b.c.- 265 b.c. ).
With respect to matrix norms we consider norms derived from
vector norms. Furthermore we mention the Frobenius norm
George Ferdinand Frobenius (1849-1917).
Furthemore we use spaces where an inner product is
defined. Most of these spaces are Hilbert spaces
David Hilbert (1862-1943). Using the Hölder inequality we show
that the Euclid norm satisfies the Cauchy-Schwarz inequality
Augustin-Louis Cauchy (1789-1857) and
Karl Hermann Amandus Schwarz (1843-1921).
Direct methods to solve linear systems
We start our description of direct methods for solving linear systems
with the Gauss elimination method
Carl Friedrich Gauss (1777-1855). Thereafter we discuss the Choleski
method for symmetric positive definite matrices. Furthermore we show that much
work and memory can be saved in the case of band matrices.
In general it is difficult to get a good analysis of rounding errors
due to floating point arithmetic done by computers. To motivate the
study of rounding errors we note that several
disasters are originated by rounding errors. Recent examples are:
Patriot Missile Failure and the
Explosion of the Ariane 5.
for non-linear equations
The Newton_Raphson method is an iterative method to solve nonlinear
equations. The method is defined by
Isaac Newton (1643-1727)
Joseph Raphson (1648-1715).
for linear equations
The standard iterative methods, which are used are the Gauss-Jacobi
and the Gauss-Seidel method.
Carl Friedrich Gauss (1777-1855)
is a very famous mathematician working on abstract and applied mathematics.
Carl Gustav Jacob Jacobi (1804-1851)
is well known for instance for the Jacobian the determinant of the
matrix of partial derivatives. He has also done work on iterative
methods leading to the Gauss-Jacobi method.
Another iterative method is the Chebyshev method. This method is based
on orthogonal polynomials bearing the name of
Pafnuty Lvovich Chebyshev (1821-1894).
The Gauss-Jacobi and Gauss-Seidel method use a very simple polynomial
to approximate the solution. In the Chebyshev method an optimal
polynomial is used.
Nowadays the most popular iterative methods are the preconditioned
Krylov methods (
Aleksei Nikolaevich Krylov ( 1863- 1945)
a second link).
For symmetric matrices the resulting method is known as the conjugate
gradient method. For non symmetric matrices different generalizations
exists for instance Bi-CG, CGS, Bi-CGSTAB, GCR, GMRES, GMRESR etc.
In the GCR, GMRES and GMRESR method a orthogonal basis for the
Krylov subspace is used. This basis is constructed from an
arbitrary basis using the Gram-Schmidt method (
Jorgen Pedersen Gram (1850-1916) and
Erhard Schmidt (1876-1959))
Classical papers of Numerical Analysis
Lloyd N. Trefethen teaches in 1993 a course with the title
Classical papers of Numerical Analysis. In this course classical papers
are given and discussed. The selected papers are famous and have a large
influence on current day scientific computing. The papers include:
the Fast Fourier Transform by Cooley & Tukey (1965),
the conjugate gradient iteration by Hestenes & Stiefel (1952),
interior point methods for linear programming by Karmarkar (1984) etc.
educational page of Kees Vuik