Lecture

Iterative Solvers: Theory and Comparison

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture explores the concept of solving linear systems iteratively, where a subroutine is repeatedly run to converge to a more accurate solution. The instructor discusses theoretical and practical criteria for comparing different solvers, emphasizing worst-case assumptions and measures of convergence. Various solvers such as Richardson iteration, Chebyshev, and CG are compared based on iteration count, convergence guarantees, and bit complexity. The lecture delves into the importance of adaptivity and cost in the Preconditioned Conjugate Gradient method, highlighting the nested nonlinear hierarchy of problems and the Stieltjes problem of moments. Additionally, the lecture touches on the interplay of infinite and finite dimensions, spectral information, and the impact of rounding errors in iterative solvers.

Official source

Related concepts (23)

Iterative method

In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones. A specific implementation with termination criteria for a given iterative method like gradient descent, hill climbing, Newton's method, or quasi-Newton methods like BFGS, is an algorithm of the iterative method.

Conjugate gradient method

In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems.

Preconditioner

In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing a condition number of the problem. The preconditioned problem is then usually solved by an iterative method. In linear algebra and numerical analysis, a preconditioner of a matrix is a matrix such that has a smaller condition number than .

Jacobi method

In numerical linear algebra, the Jacobi method (a.k.a. the Jacobi iteration method) is an iterative algorithm for determining the solutions of a strictly diagonally dominant system of linear equations. Each diagonal element is solved for, and an approximate value is plugged in. The process is then iterated until it converges. This algorithm is a stripped-down version of the Jacobi transformation method of matrix diagonalization. The method is named after Carl Gustav Jacob Jacobi.

Biconjugate gradient method

In mathematics, more specifically in numerical linear algebra, the biconjugate gradient method is an algorithm to solve systems of linear equations Unlike the conjugate gradient method, this algorithm does not require the matrix to be self-adjoint, but instead one needs to perform multiplications by the conjugate transpose A*. Choose initial guess , two other vectors and and a preconditioner for do In the above formulation, the computed and satisfy and thus are the respective residuals corresponding to and , as approximate solutions to the systems is the adjoint, and is the complex conjugate.

Related lectures (36)

Linear Systems: Convergence and Methods

Explores linear systems, convergence, and solving methods with a focus on CPU time and memory requirements.

LU Decomposition: Linear Systems Applications MOOC: Linear Algebra (Part 1)

Covers the LU decomposition method applied to linear systems, presenting the system in two steps.

Vectorization in Python: Efficient Computation with Numpy

Covers vectorization in Python using Numpy for efficient scientific computing, emphasizing the benefits of avoiding for loops and demonstrating practical applications.

Momentum Methods and Nonlinear Conjugate Gradients

The session explains how momentum accelerates gradient descent, presents the theory of nonlinear conjugate gradients on manifolds, compares several beta‑rule updates, discusses line‑search and preconditioner choices, and shows how to employ the Manopt library for Riemannian optimization without explicit Hessians.

Conjugate Gradient Method