Iterative solution of linear systems in the 20th century

DOI10.1016/S0377-0427(00)00412-XzbMath0965.65051OpenAlexW1982064072MaRDI QIDQ1591173

Henk A. van der Vorst, Yousef Saad

Publication date: 19 December 2000

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-0427(00)00412-x

zbMATH Keywords

preconditioningRichardson methodparallel computationhistorical surveyiterative methodsmultigrid methodsprojection methodsKrylov subspace methodslinear algebraic equationsincomplete factorizationpolynomial accelerationsrelaxation-based methods

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) History of mathematics in the 20th century (01A60) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Parallel numerical computation (65Y05) History of numerical analysis (65-03)

Related Items (87)

Efficient and robust Schur complement approximations in the augmented Lagrangian preconditioner for the incompressible laminar flows ⋮ Block-preconditioners for the incompressible Navier-Stokes equations discretized by a finite volume method ⋮ A maximal projection solution of ill-posed linear system in a column subspace, better than the least squares solution ⋮ SSOR and ASSOR preconditioners for block-Broyden method ⋮ A projection method for semidefinite linear systems and its applications ⋮ High performance inverse preconditioning ⋮ Lanczos-type variants of the COCR method for complex nonsymmetric linear systems ⋮ GPBiCG(\(m,\ell\)): A hybrid of biCGSTAB and GPBiCG methods with efficiency and robustness ⋮ A three-dimensional finite volume method based on radial basis functions for the accurate computational modelling of nonlinear diffusion equations ⋮ Mixed constraint preconditioning in computational contact mechanics ⋮ A fine-grained block ILU scheme on regular structures for GPGPUs ⋮ An algorithm with \(m\)-step residual history for solving linear equations: data interpolation by a multi-shape-factors RBF ⋮ A Distributed Normalized Explicit Preconditioned Conjugate Gradient Method ⋮ Conditional Source-term Estimation using dynamic ensemble selection and parallel iterative solution ⋮ The minimal norm least squares Hermitian solution of the complex matrix equation \(AXB+CXD=E\) ⋮ An iterative method for solving general restricted linear equations ⋮ Conjugate gradient least squares algorithm for solving the generalized coupled Sylvester matrix equations ⋮ Finding the orthogonal projection of a point onto an affine subspace ⋮ A comparative study of iterative solutions to linear systems arising in quantum mechanics ⋮ A double optimal descent algorithm for iteratively solving ill-posed linear inverse problems ⋮ Regularized conjugate gradient method for skew-symmetric indefinite system of linear equations and applications ⋮ Delayed Gradient Methods for Symmetric and Positive Definite Linear Systems ⋮ Efficient solution for Galerkin-based polynomial chaos expansion systems ⋮ Discrete orthogonal polynomials reduced models based on shift-transformation and discrete Walsh functions ⋮ Adaptive rational interpolation: Arnoldi and Lanczos-like equations ⋮ Explicit approximate inverse preconditioning techniques ⋮ A New Approach to the Splitting Factor Preconditioner Applied to Linear Programming Problems ⋮ A finite iterative algorithm for solving the complex generalized coupled Sylvester matrix equations by using the linear operators ⋮ An optimal control theory for nonlinear optimization ⋮ Two stochastic algorithms for solving elastostatics problems governed by the Lamé equation ⋮ Reuben Louis Rosenberg (1909--1986) and the Stein-Rosenberg theorem ⋮ GMRES implementations and residual smoothing techniques for solving ill-posed linear systems ⋮ A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms ⋮ Structure and approximation properties of Laplacian-like matrices ⋮ A unified formulation for generalized oilfield development optimization ⋮ Comparison of linear solvers for equilibrium geochemistry computations ⋮ Preconditioning for sparse linear systems at the dawn of the 21st century: history, current developments, and future perspectives ⋮ The genesis and early developments of Aitken's process, Shanks' transformation, the \(\varepsilon\)-algorithm, and related fixed point methods ⋮ On the Meany inequality with applications to convergence analysis of several row-action iteration methods ⋮ Jacobian-free Newton-Krylov methods: a survey of approaches and applications. ⋮ On the GPGPU parallelization issues of finite element approximate inverse preconditioning ⋮ On the capabilities of the polynomial chaos expansion method within SFE analysis -- an overview ⋮ Block Jacobi Preconditioning for Solving Dynamic General Equilibrium Models ⋮ A variant of the IDR\((s)\) method with the quasi-minimal residual strategy ⋮ High-efficiency improved symmetric successive over-relaxation preconditioned conjugate gradient method for solving large-scale finite element linear equations ⋮ A SBS-BD based solver for domain decomposition in BE methods ⋮ Lanczos conjugate-gradient method and pseudoinverse computation on indefinite and singular systems ⋮ Effective preconditioning through minimum degree ordering interleaved with incomplete factorization ⋮ Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions ⋮ Asymmetric Hermitian and skew-Hermitian splitting methods for positive definite linear systems ⋮ High performance finite element approximate inverse preconditioning ⋮ Combining the Augmented Lagrangian Preconditioner with the Simple Schur Complement Approximation ⋮ An implicit wavelet sparse approximate inverse preconditioner using block finger pattern ⋮ Chronos: A General Purpose Classical AMG Solver for High Performance Computing ⋮ An Efficient Variant of the GMRES(m) Method Based on the Error Equations ⋮ Generalized shift-splitting iteration method for a class of two-by-two linear systems ⋮ A fast 3D dual boundary element method based on hierarchical matrices ⋮ Conjugate gradient (CG)-type method for the solution of Newton's equation within optimization frameworks ⋮ Solving PDEs in non-rectangular 3D regions using a collocation finite element method ⋮ Solving nonlinear equations with the Newton–Krylov method based on automatic differentiation ⋮ Numerical simulations of a transient injection flow at low Mach number regime ⋮ A problem-orientable numerical algorithm for modeling multi-dimensional radiative MHD flows in astrophysics-the hierarchical solution scenario ⋮ Alternating oblique projections for coupled linear systems ⋮ A performance study of normalized explicit finite element approximate inverse preconditioning on uniprocessor and multicomputer systems ⋮ Convergence analysis of Krylov subspace methods ⋮ Pre-symmetric approach and applications to indefinite non-symmetric problems ⋮ Wavelet preconditioned Newton-Krylov method for elastohydrodynamic lubrication of line contact problems ⋮ Performance analysis of preconditioners based on Broyden method ⋮ A Frisch-Newton algorithm for sparse quantile regression ⋮ On the \(ijk\) forms of the truncated LU decomposition ⋮ A generalized iterative method and comparison results using projection techniques for solving linear systems ⋮ Globally and superlinearly convergent inexact Newton-Krylov algorithms for solving nonsmooth equations ⋮ A parallel adaptive finite element method for the simulation of photon migration with the radiative‐transfer‐based model ⋮ A Dynamic Pattern Factored Sparse Approximate Inverse Preconditioner on Graphics Processing Units ⋮ Multi-level incomplete factorizations for the iterative solution of non-linear finite element problems ⋮ The conjugate gradient methods for solving the generalized periodic Sylvester matrix equations ⋮ A modification of minimal residual iterative method to solve linear systems ⋮ Revisiting the BE SBS algorithm and applying it to solve torsion problems in composite bars: robustness and efficiency study ⋮ PARALLEL ITERATIVE REGULARIZATION ALGORITHMS FOR LARGE OVERDETERMINED LINEAR SYSTEMS ⋮ Iterative methods for linear systems of equations: A brief historical journey ⋮ Planar conjugate gradient algorithm for large-scale unconstrained optimization. I: Theory ⋮ Polynomial Accelerated Solutions to a Large Gaussian Model for Imaging Biofilms: In Theory and Finite Precision ⋮ Preconditioners in computational geomechanics: A survey ⋮ The impact of high-performance computing in the solution of linear systems: Trends and problems ⋮ A framework of conjugate direction methods for symmetric linear systems in optimization ⋮ A hybrid multigrid method for convection-diffusion problems ⋮ Preconditioning techniques for large linear systems: A survey

Uses Software

• LSQR
• GpBiCg
• CGS
• Wesseling
• na1
• DRIC
• CRAIG

Cites Work

• Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration
• Projection methods for linear systems
• Padé-type approximation and general orthogonal polynomials
• Modified block-approximate factorization strategies
• Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. I, II
• On the real convergence rate of the conjugate gradient method
• A breakdown-free Lanczos type algorithm for solving linear systems
• Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems
• Direct methods for sparse matrices
• On the eigenvalue distribution of a class of preconditioning methods
• The rate of convergence of conjugate gradients
• A general incomplete block-matrix factorization method
• Large tridiagonal and block tridiagonal linear systems on vector and parallel computers
• A stable Richardson iteration method for complex linear systems
• Algebraic multilevel preconditioning methods. I
• Preconditioning techniques for nonsymmetric and indefinite linear systems
• A projection method for solving nonsymmetric linear systems on multiprocessors
• Parallel conjugate gradient-like algorithms for solving sparse nonsymmetric linear systems on a vector multiprocessor
• Approximating the inverse of a matrix for use in iterative algorithms on vector processors
• Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations
• Computational methods of linear algebra
• Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods
• Iterative solution methods for certain sparse linear systems with a non- symmetric matrix arising from PDE-problems
• Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems
• QMR: A quasi-minimal residual method for non-Hermitian linear systems
• A comparison of some GMRES-like methods
• Avoiding breakdown and near-breakdown in Lanczos type algorithms
• Towards a cost-effective ILU preconditioner with high level fill
• Contraction en norme vectorielle: Convergence d'itérations chaotiques pour des équations non linéaires de point fixe à plusieurs variables
• The Tchebychev iteration for nonsymmetric linear systems
• Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method
• The effect of ordering on preconditioned conjugate gradients
• Iterative solution of large sparse systems of equations. Transl. from the German
• An analysis of the composite step biconjugate gradient method
• ICCG and related methods for 3D problems on vector computers
• BiCGstab(\(l\)) for linear equations involving unsymmetric matrices with complex spectrum
• Accelerating with rank-one updates
• Look-ahead in Bi-CGSTAB and other product methods for linear systems
• SOR as a preconditioner
• A theoretical overview of Krylov subspace methods
• Nested grids ILU-decomposition (NGILU)
• Generalized conjugate gradient squared
• Chaotic relaxation
• Projection method for solving a singular system of linear equations and its applications
• Über die Determinanten mit überwiegender Hauptdiagonale
• Variational Iterative Methods for Nonsymmetric Systems of Linear Equations
• Algebraic Multilevel Preconditioning Methods, II
• Block Preconditioning for the Conjugate Gradient Method
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method
• The question of non-self-adjoint extension of the conjugate gradients method is closed
• SOLVING SPARSE TRIANGULAR LINEAR SYSTEMS ON PARALLEL COMPUTERS
• High Performance Preconditioning
• Krylov Subspace Methods on Supercomputers
• A Note on the Efficiency of Domain Decomposed Incomplete Factorizations
• Polynomial Preconditioners for Conjugate Gradient Calculations
• A Look-Ahead Lanczos Algorithm for Unsymmetric Matrices
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Practical Use of Polynomial Preconditionings for the Conjugate Gradient Method
• Least Squares Polynomials in the Complex Plane and Their Use for Solving Nonsymmetric Linear Systems
• A Stability Analysis of Incomplete LU Factorizations
• Computing the Roots of Complex Orthogonal and Kernel Polynomials
• CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems
• Some History of the Conjugate Gradient and Lanczos Algorithms: 1948–1976
• An extrapolation procedure for solving linear systems
• Extremal Polynomials with Application to Richardson Iteration for Indefinite Linear Systems
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• A Vectorizable Variant of some ICCG Methods
• Use of Iterative Refinement in the Solution of Sparse Linear Systems
• A Black Box Generalized Conjugate Gradient Solver with Inner Iterations and Variable-Step Preconditioning
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Row Projection Methods for Large Nonsymmetric Linear Systems
• Line Iterative Methods for Cyclically Reduced Discrete Convection-Diffusion Problems
• Generalized Schwarz Splittings
• Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
• Reduction to Tridiagonal Form and Minimal Realizations
• A Completed Theory of the Unsymmetric Lanczos Process and Related Algorithms, Part I
• How Fast are Nonsymmetric Matrix Iterations?
• Ordering Methods for Preconditioned Conjugate Gradient Methods Applied to Unstructured Grid Problems
• Approximate inverse preconditionings for sparse linear systems
• Factorized Sparse Approximate Inverse Preconditionings I. Theory
• Solution of Sparse Indefinite Systems of Linear Equations
• An Iterative Solution Method for Linear Systems of Which the Coefficient Matrix is a Symmetric M-Matrix
• Multi-Level Adaptive Solutions to Boundary-Value Problems
• A class of first order factorization methods
• A Lanczos Method for a Class of Nonsymmetric Systems of Linear Equations
• Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations
• Numerical Linear Algebra for High-Performance Computers
• Orderings for Incomplete Factorization Preconditioning of Nonsymmetric Problems
• A Quasi-Minimal Residual Variant of the Bi-CGSTAB Algorithm for Nonsymmetric Systems
• Iterative Solution Methods
• Error-Minimizing Krylov Subspace Methods
• GPBi-CG: Generalized Product-type Methods Based on Bi-CG for Solving Nonsymmetric Linear Systems
• Parallel Preconditioning with Sparse Approximate Inverses
• Approximate Inverse Techniques for Block-Partitioned Matrices
• An Evaluation of Parallel Multigrid as a Solver and a Preconditioner for Singularly Perturbed Problems
• Approximate Inverse Preconditioners via Sparse-Sparse Iterations
• A Hybrid Chebyshev Krylov Subspace Algorithm for Solving Nonsymmetric Systems of Linear Equations
• Application of Sparse Matrix Solvers as Effective Preconditioners
• Ordering Strategies for Modified Block Incomplete Factorizations
• GMRESR: a family of nested GMRES methods
• DRIC: A dynamic version of the RIC method
• Parallel block preconditioning based on SSOR and MILU
• Relations between Galerkin and Norm-Minimizing Iterative Methods for Solving Linear Systems
• Any Nonincreasing Convergence Curve is Possible for GMRES
• A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method
• A Flexible Inner-Outer Preconditioned GMRES Algorithm
• A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
• An Iterative Least-Square Method Suitable for Solving Large Sparse Matrices
• The speed of convergence of one iterative process
• The Conjugate Gradient Method for Linear and Nonlinear Operator Equations
• Estimates for Some Computational Techniques in Linear Algebra
• A New Method of Solving Nonlinear Simultaneous Equations
• An Approximate Factorization Procedure for Solving Self-Adjoint Elliptic Difference Equations
• Hyperbolic Pairs in the Method of Conjugate Gradients
• Iterative Solution of Implicit Approximations of Multidimensional Partial Differential Equations
• On the Approximate Minimization of Functionals
• The Use of Pre-conditioning in Iterative Methods for Solving Linear Equations with Symmetric Positive Definite Matrices
• A generalized SSOR method
• A Theoretical Comparison of the Arnoldi and GMRES Algorithms
• On the Solution of Linear Simultaneous Equations By Iteration
• On the Convergence of the Classical Iterative Method of Solving Linear Simultaneous Equations
• The principle of minimized iterations in the solution of the matrix eigenvalue problem
• Convergence of a Method of Solving Linear Problems
• Methods of conjugate gradients for solving linear systems
• Use of Tschebyscheff-Polynomial Operators in the Numerical Solution of Boundary-Value Problems
• On Richardson's Method for Solving Linear Systems with Positive Definite Matrices
• On the Numerical Solution of Elliptic Difference Equations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Iterative solution of linear systems in the 20th century