Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Numerical Analysis → Numerical Linear Algebra ↓


Preconditioning Techniques


Preconditioning is a powerful technique used in numerical linear algebra to speed up the convergence of iterative solvers for solving linear systems of equations. It involves transforming a given system into a form that is more amenable to numerical computation. In many real-world applications, especially those involving large and sparse matrices, direct methods such as Gaussian elimination become prohibitively expensive in terms of computational resources and time. This is where iterative methods, aided by preconditioning, come into the picture.

What is preconditioning?

In simple terms, preconditioning is the process of applying transformations to a linear system, thereby creating another system that has the same solution, but is easier to solve by iterative methods. Mathematically, consider this system:

Ax = b

The idea is to find a matrix M, called the preconditioner, such that the modified system can be solved:

M -1 Ax = M -1 b

This speeds up convergence. The choice of M is important; it should be close to A and easy to invert.

Why use preconditioning?

Without preconditioning, iterative methods may converge very slowly or not converge at all. One important aspect that a preconditioner must address is the condition number of the matrix. The condition number of a matrix, in simple terms, measures how sensitive the solution of a system of linear equations is to changes in the coefficients or the right-hand side. A smaller condition number usually indicates faster convergence. Preconditioning helps to reduce the condition number.

Types of preconditioning

Left preconditioning

In left preconditioning, we multiply the system Ax = b from the left by M -1, resulting in:

M -1 Ax = M -1 b

The aim of this approach is to solve the coefficient matrix A directly and attempt to solve the transformed system efficiently.

Right preconditioning

In right preconditioning, we multiply the right side by the left side resulting in:

A(M -1 y) = b

We then solve for y = Mx. This method focuses on transforming the solution vector directly.

Partitioned preconditioning

Split preconditioning involves using two preconditioners, one on each side:

M 1 -1 AM 2 -1 z = M 1 -1 b

Here, we solve for z = M 2 x by applying more complicated transformations to increase efficiency.

Common preconditioners

1. Jacobi preconditioning

The Jacobi preconditioner uses the diagonal elements of A to create a preconditioner matrix M:

M = diag(A)

Here, diag(A) denotes the diagonal matrix formed from the diagonal elements of A. This approach is simple and easy to implement.

2. Gauss-Seidel preconditioning

The Gauss–Seidel preconditioner is similar but it also considers the lower triangular part of A:

M = (D + L)

Where D is the diagonal part and L is the lower triangular part of A.

3. Incomplete LU (ILU) preconditioning

ILU preconditioning uses an approximate LU factorization of the matrix A. Instead of computing the full LU factorization, ILU computes an approximation:

A ≈ LU

where L and U are lower and upper triangular matrices, respectively. ILU is particularly suitable for sparse matrices because it preserves sparsity.

4. Incomplete Cholesky preconditioning

Similar to ILU, the incomplete Cholesky factorization is used for symmetric positive definite matrices:

A ≈ LL T

The LL T M with L being a lower triangular matrix.

5. Additive Schwarz preconditioning

This method divides the original domain into overlapping subdomains, applies a preconditioner to each subdomain, and combines their effects additively. It is popular in parallel computing environments.

Visual depictions

A M M - 1A

In the illustration, the blue box represents the matrix A, the green box represents the preconditioner M, and the red box represents the preconditioned matrix M -1 A, which is easier and faster to solve.

Choosing a preconditioner

Choosing an effective preconditioner requires balancing the benefits of better convergence with the computational effort required to apply the preconditioner at each iteration. An ideal preconditioner should have the following properties:

  • Easier to compute and apply (won't require significant additional computational resources).
  • Effective in reducing the state number of the system.
  • Applicable to specific matrix properties (e.g., sparsity, homogeneity).

Practical considerations

When applying preconditioning techniques in practice, several factors must be considered. The effectiveness of a preconditioning method may depend on the size, structure of the matrix, and the specific problem domain. In some cases, custom or problem-specific preconditioning techniques can be developed to maximize efficiency.

Case studies and example applications

An example application might involve solving systems arising from finite element discretization in engineering simulations. Here, due to the nature of the discretization, the matrices can be large, sparse, and poorly conditioned. Applying an ILU preconditioner or a multigrid method can dramatically improve the performance of the solver.

Conclusion

Preconditioning is a crucial step in making iterative solvers feasible for large and complex systems of linear equations. It turns an otherwise difficult problem into a computationally tractable one. By using a suitable preconditioner such as Jacobi, Gauss-Seidel, ILU or Incomplete Cholesky, the efficiency in computations can be improved significantly. As research progresses, preconditioning techniques continue to evolve, providing more efficient solutions to real-world numerical problems.


Graduate → 6.2.4


U
username
0%
completed in Graduate

← Prev (6.2.3)
Sparse Matrices
Next (6.3) →
Numerical Integration and Differentiation

Comments 



Preconditioning Techniques

https://www.buddymath.com/g/6.2.4?bmal=en