Iterative solution of linear systems in the 20th century

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

Yousef Saad, Henk A. van der Vorst

Publication date: 19 December 2000

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

zbMATH Keywords

preconditioning; Richardson method; parallel computation; historical survey; iterative methods; multigrid methods; projection methods; Krylov subspace methods; linear algebraic equations; incomplete factorization; polynomial accelerations; relaxation-based methods

Mathematics Subject Classification ID

65N55: Multigrid methods; domain decomposition for boundary value problems involving PDEs

01A60: History of mathematics in the 20th century

65F10: Iterative numerical methods for linear systems

65F35: Numerical computation of matrix norms, conditioning, scaling

65Y05: Parallel numerical computation

65-03: History of numerical analysis

Related Items

Conjugate gradient (CG)-type method for the solution of Newton's equation within optimization frameworks, Convergence analysis of Krylov subspace methods, A Distributed Normalized Explicit Preconditioned Conjugate Gradient Method, Finding the orthogonal projection of a point onto an affine subspace, Regularized conjugate gradient method for skew-symmetric indefinite system of linear equations and applications, Lanczos conjugate-gradient method and pseudoinverse computation on indefinite and singular systems, High performance finite element approximate inverse preconditioning, A fast 3D dual boundary element method based on hierarchical matrices, GPBiCG(\(m,\ell\)): A hybrid of biCGSTAB and GPBiCG methods with efficiency and robustness, Explicit approximate inverse preconditioning techniques, Jacobian-free Newton-Krylov methods: a survey of approaches and applications., The impact of high-performance computing in the solution of linear systems: Trends and problems, Alternating oblique projections for coupled linear systems, Preconditioning techniques for large linear systems: A survey, A projection method for semidefinite linear systems and its applications, SSOR and ASSOR preconditioners for block-Broyden method, A three-dimensional finite volume method based on radial basis functions for the accurate computational modelling of nonlinear diffusion equations, Asymmetric Hermitian and skew-Hermitian splitting methods for positive definite linear systems, Performance analysis of preconditioners based on Broyden method, A Frisch-Newton algorithm for sparse quantile regression, Planar conjugate gradient algorithm for large-scale unconstrained optimization. I: Theory

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