Preconditioning techniques for large linear systems: A survey

DOI10.1006/JCPH.2002.7176zbMath1015.65018OpenAlexW1981220107MaRDI QIDQ1868569

Michele Benzi

Publication date: 28 April 2003

Published in: Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcph.2002.7176

zbMATH Keywords

linear systemsbibliographyiterative methodsparallel computingsparse matricesorderingsunstructured gridssurvey papermultilevel methodsblock algorithmssparse approximate inversesincomplete factorizationsalgebraic preconditioners

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Parallel numerical computation (65Y05) General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to numerical analysis (65-00)

Related Items (only showing first 100 items - show all)

A hybrid recursive multilevel incomplete factorization preconditioner for solving general linear systems ⋮ Off-diagonal low-rank preconditioner for difficult PageRank problems ⋮ A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows ⋮ High performance inverse preconditioning ⋮ Lanczos-type variants of the COCR method for complex nonsymmetric linear systems ⋮ An orthogonally accumulated projection method for symmetric linear system of equations ⋮ Additive preconditioning for matrix computations ⋮ MPI-CUDA sparse matrix-vector multiplication for the conjugate gradient method with an approximate inverse preconditioner ⋮ Parallel adaptive simulation of gravity currents on the lock-exchange problem ⋮ GPU-accelerated large-scale simulations of interfacial multiphase fluids for real-case applications ⋮ Hybrid reordering strategies for ILU preconditioning of indefinite sparse matrices ⋮ A fast preconditioned penalty method for American options pricing under regime-switching tempered fractional diffusion models ⋮ Sparse approximations of matrix functions via numerical integration of ODEs ⋮ Sparse approximate solution of fitting surface to scattered points by MLASSO model ⋮ A domain decomposition method of stochastic PDEs: an iterative solution techniques using a two-level scalable preconditioner ⋮ A hybrid boundary element-finite element approach to modeling plane wave 3D electromagnetic induction responses in the Earth ⋮ On preconditioned BiCGSTAB solver for MLPG method applied to heat conduction in 3D complex geometry ⋮ Preconditioning complex symmetric linear systems ⋮ A black-box rational Arnoldi variant for Cauchy-Stieltjes matrix functions ⋮ On a parallel, 3-dimensional, finite element solver for viscous, resistive, stationary magnetohydrodynamics equations: velocity-current formulation ⋮ A comparative study of iterative solutions to linear systems arising in quantum mechanics ⋮ Parallel solution of large-scale free surface viscoelastic flows via sparse approximate inverse preconditioning ⋮ A fully implicit, compact finite difference method for the numerical solution of unsteady laminar flames ⋮ Factored sparse approximate inverse of block tridiagonal and block pentadiagonal matrices ⋮ Fractional PDE constrained optimization: an optimize-then-discretize approach with L-BFGS and approximate inverse preconditioning ⋮ On POD-based deflation vectors for DPCG applied to porous media problems ⋮ Solution of generalized shifted linear systems with complex symmetric matrices ⋮ On the solution of a class of complex symmetric linear systems ⋮ A partitioned shift-without-invert algorithm to improve parallel eigensolution efficiency in real-space electronic transport ⋮ Application of the incomplete Cholesky factorization preconditioned Krylov subspace method to the vector finite element method for 3-D electromagnetic scattering problems ⋮ \(\mathcal H\)-FAINV: hierarchically factored approximate inverse preconditioners ⋮ A tensor-train accelerated solver for integral equations in complex geometries ⋮ LUPOD: collocation in POD via LU decomposition ⋮ Multigrid in energy preconditioner for Krylov solvers ⋮ A modified SSOR preconditioning strategy for Helmholtz equations ⋮ A new preconditioner update strategy for the solution of sequences of linear systems in structural mechanics: application to saddle point problems in elasticity ⋮ Comparison of eigenvalue ratios in artificial boundary perturbation and Jacobi preconditioning for solving Poisson equation ⋮ Approximate factoring of the inverse ⋮ Preconditioning the bidomain model with almost linear complexity ⋮ GMRES with multiple preconditioners ⋮ Remarks on continuum theory of mixtures: editorial to special issue on mixture theory ⋮ Efficient unsteady high Reynolds number flow computations on unstructured grids ⋮ On the performance of a simple parallel implementation of the ILU-PCG for the Poisson equation on irregular domains ⋮ On iterative techniques for computing flow in large two-dimensional discrete fracture networks ⋮ Jacobian-free Newton-Krylov methods: a survey of approaches and applications. ⋮ The pre/post equilibrated conditioning methods to solve Cauchy problems ⋮ Convergence analysis of modified iterative methods to solve linear systems ⋮ On optimizing Jacobi-Davidson method for calculating eigenvalues in low dimensional structures using eight band \(\mathbf{k}\cdot\mathbf{p}\) model ⋮ A new iterative method for finding approximate inverses of complex matrices ⋮ New preconditioning techniques for saddle point problems arising from the time-harmonic Maxwell equations ⋮ An inexact Newton-type method for inverse singular value problems ⋮ On the application of homotopy perturbation method for solving systems of linear equations ⋮ On the performance of the algebraic optimized Schwarz methods with applications ⋮ Envelope functions: unifications and further properties ⋮ Positive stable preconditioners for symmetric indefinite linear systems arising from Helmholtz equations ⋮ Effective preconditioning through minimum degree ordering interleaved with incomplete factorization ⋮ Preconditioned HSS iteration method and its non-alternating variant for continuous Sylvester equations ⋮ A nonstationary accelerating alternating direction method for frame-based Poissonian image deblurring ⋮ High performance finite element approximate inverse preconditioning ⋮ A parallel algorithm to approximate inverse factors of a matrix via sparse-sparse iterations ⋮ Computing the smallest eigenpairs of the graph Laplacian ⋮ Fast preconditioned iterative methods for finite volume discretization of steady-state space-fractional diffusion equations ⋮ Geometrical properties of the Frobenius condition number for positive definite matrices ⋮ On the preconditioning of the block tridiagonal linear system of equations ⋮ A new relaxed HSS preconditioner for saddle point problems ⋮ A non-alternating preconditioned HSS iteration method for non-Hermitian positive definite linear systems ⋮ Sparse approximate inverse preconditioners on high performance GPU platforms ⋮ A fast 3D dual boundary element method based on hierarchical matrices ⋮ Solving mixed classical and fractional partial differential equations using short-memory principle and approximate inverses ⋮ Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming ⋮ Additive preconditioning, eigenspaces, and the inverse iteration ⋮ Modification of Karmarkar's projective scaling algorithm ⋮ On the relation between the AINV and the FAPINV algorithms ⋮ A parallel multilevel preconditioned iterative pressure Poisson solver for the large-eddy simulation of turbulent flow inside a duct ⋮ Numerical stability of orthogonalization methods with a non-standard inner product ⋮ Wavelet based ILU preconditioners for the numerical solution by PUFEM of high frequency elastic wave scattering ⋮ OSQP: An Operator Splitting Solver for Quadratic Programs ⋮ JADAMILU: a software code for computing selected eigenvalues of large sparse symmetric matrices ⋮ Performance of fully-coupled algebraic multigrid preconditioners for large-scale VMS resistive MHD ⋮ An analytical method as a preconditioning modeling for systems of linear equations ⋮ An evaluation of low-cost heuristics for matrix bandwidth and profile reductions ⋮ Efficient solution of the simplified \(P_N\) equations ⋮ On the improved finite volume procedure for simulation of turbulent flows over real complex terrains ⋮ FGMRES preconditioning by symmetric/skew-symmetric decomposition of generalized Stokes problems ⋮ Extending linear relaxation for non-square matrices and soft constraints ⋮ Optimization of the parameterized Uzawa preconditioners for saddle point matrices ⋮ Block splitting for distributed optimization ⋮ Factoring matrices into the product of circulant and diagonal matrices ⋮ Stabilized forms of orthogonal residual and constant incremental work control path following methods ⋮ A new family of \((I+S)\)-type preconditioner with some applications ⋮ A sparse-sparse iteration for computing a sparse incomplete factorization of the inverse of an SPD matrix ⋮ Multilevel sparse approximate inverse preconditioners for adaptive mesh refinement ⋮ Design and deployment of distributed numerical applications using .NET and component oriented programming ⋮ Partitioned versus global Krylov subspace iterative methods for FE solution of 3-D Biot's problem ⋮ An implicit compact scheme solver for two-dimensional multicomponent flows ⋮ A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems ⋮ Preconditioned optimization algorithms solving the problem of the non unitary joint block diagonalization: application to blind separation of convolutive mixtures ⋮ Reanalysis of structural modifications due to removal of degrees of freedom ⋮ A comparison of stiff ODE solvers for astrochemical kinetics problems ⋮ An ILU preconditioner for nonsymmetric positive definite matrices by using the conjugate Gram-Schmidt process

Uses Software

• ARMS
• BoomerAMG
• pARMS
• PETSc
• MUMPS
• TAUCS
• SparseMatrix
• Algorithm 740
• BPKit
• BILUTM
• ILUM
• ILUS
• symrcm
• ILUT

Cites Work

• Maximum‐weight‐basis preconditioners
• Comparison of Fast Iterative Methods for Symmetric Systems
• Polynomial Preconditioners for Conjugate Gradient Calculations
• Decay Rates for Inverses of Band Matrices
• Modification of the minimum-degree algorithm by multiple elimination
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• An algorithm for profile and wavefront reduction of sparse matrices
• A Stability Analysis of Incomplete LU Factorizations
• Multicolor ICCG Methods for Vector Computers
• The Evolution of the Minimum Degree Ordering Algorithm
• Some History of the Conjugate Gradient and Lanczos Algorithms: 1948–1976
• On the Robustness of ILU Smoothing
• An extrapolation procedure for solving linear systems
• An Incomplete Factorization Technique for Positive Definite Linear Systems
• Generalized Nested Dissection
• Efficient Implementation of a Class of Preconditioned Conjugate Gradient Methods
• Incomplete Factorizations of Matrices and Connections with H-Matrices
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
• An approximate inverse based multigrid approach to the biharmonic problem
• A Review on the Inverse of Symmetric Tridiagonal and Block Tridiagonal Matrices
• Ordering Methods for Preconditioned Conjugate Gradient Methods Applied to Unstructured Grid Problems
• Approximate inverse preconditionings for sparse linear systems
• A method of finite element tearing and interconnecting and its parallel solution algorithm
• Factorized Sparse Approximate Inverse Preconditionings I. Theory
• On Finding Supernodes for Sparse Matrix Computations
• Solution of Sparse Indefinite Systems of Linear Equations
• An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
• 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
• Numerical Linear Algebra for High-Performance Computers
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• On a Class of Preconditioning Methods for Dense Linear Systems from Boundary Elements
• A Multigrid Method Based on Incomplete Gaussian Elimination
• An assessment of some preconditioning techniques in shell problems
• The Incomplete Factorization Multigraph Algorithm
• Orderings for Incomplete Factorization Preconditioning of Nonsymmetric Problems
• An object-oriented framework for block preconditioning
• Predicting Structure in Sparse Matrix Computations
• Iterative Solution Methods
• A Linear Algebraic Analysis of Diffusion Synthetic Acceleration for the Boltzmann Transport Equation
• Parallel Preconditioning with Sparse Approximate Inverses
• HIGH-PERFORMANCE PCG SOLVERS FOR FEM STRUCTURAL ANALYSIS
• ROBUST PRECONDITIONERS FOR LINEAR ELASTICITY FEM ANALYSES
• ILUS: An incomplete LU preconditioner in sparse skyline format
• An improved incomplete Cholesky factorization
• Algorithm 740: Fortran subroutines to compute improved incomplete Cholesky factorizations
• Approximate Inverse Techniques for Block-Partitioned Matrices
• Sparse Approximate-Inverse Preconditioners Using Norm-Minimization Techniques
• A Sparse Approximate Inverse Preconditioner for Nonsymmetric Linear Systems
• Approximate Inverse Preconditioners via Sparse-Sparse Iterations
• Finding Exact and Approximate Block Structures for ILU Preconditioning
• Solution ofthe DiscontinuousP₁Equations in Two-Dimensional Cartesian Geometry with Two-Level Preconditioning
• A Robust Preconditioner with Low Memory Requirements for Large Sparse Least Squares Problems
• Exploiting Multilevel Preconditioning Techniques in Eigenvalue Computations
• Fast wavelet iterative solvers applied to the Neumann problem
• A Multigrid Tutorial, Second Edition
• Sparse Approximate Inverse Smoother for Multigrid
• The Fast Multipole Method I: Error Analysis and Asymptotic Complexity
• Inexact Preconditioned Conjugate Gradient Method with Inner-Outer Iteration
• A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners
• Orderings for Factorized Sparse Approximate Inverse Preconditioners
• Robustness and Scalability of Algebraic Multigrid
• A Note on Preconditioning for Indefinite Linear Systems
• Optimal Order Preconditioning of Finite Difference Matrices
• Problem-dependent preconditioners for iterative solvers in FE elastostatics
• The effect of ordering on preconditioned GMRES algorithm, for solving the compressible Navier‐Stokes equations
• The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices
• Matrix Renumbering ILU: An Effective Algebraic Multilevel ILU Preconditioner for Sparse Matrices
• BILUTM: A Domain-Based Multilevel Block ILUT Preconditioner for General Sparse Matrices
• BILUM: Block Versions of Multielimination and Multilevel ILU Preconditioner for General Sparse Linear Systems
• Incomplete Cholesky Factorizations with Limited Memory
• Ordering, Anisotropy, and Factored Sparse Approximate Inverses
• An Approximate Minimum Degree Ordering Algorithm
• Algebraic Multilevel Methods and Sparse Approximate Inverses
• On the Relations between ILUs and Factored Approximate Inverses
• A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling
• Projection methods for linear systems
• Parallel ocean general circulation modeling
• Fast approximate solution of large scale sparse linear systems
• Algebraic multigrid (AMG): Experiences and comparisons
• On some versions of incomplete block-matrix factorization iterative methods
• On parallelism and convergence of incomplete LU factorizations
• A new preconditioning technique for solving large sparse linear systems
• A survey of preconditioned iterative methods for linear systems of algebraic equations
• A general incomplete block-matrix factorization method
• Large tridiagonal and block tridiagonal linear systems on vector and parallel computers
• Algebraic multilevel preconditioning methods. I
• Preconditioning techniques for nonsymmetric and indefinite linear systems
• Explicit preconditioning of systems of linear algebraic equations with dense matrices
• Vectorizable preconditioners for elliptic difference equations in three space dimensions
• Approximating the inverse of a matrix for use in iterative algorithms on vector processors
• Iterative solution methods for certain sparse linear systems with a non- symmetric matrix arising from PDE-problems
• Black box multigrid
• Regular incomplete factorizations of real positive definite matrices
• Analysis of parallel incomplete point factorizations
• QMR: A quasi-minimal residual method for non-Hermitian linear systems
• An incomplete-factorization preconditioning using repeated red-black ordering
• The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations
• The effect of ordering on preconditioned conjugate gradients
• Adaptive polynomial preconditioning for Hermitian indefinite linear systems
• Numerical experiments with two approximate inverse preconditioners
• Using approximate inverses in algebraic multilevel methods
• Inexact Newton preconditioning techniques for large symmetric eigenvalue problems
• Preconditioning eigensolvers -- an Oxymoron?
• Numerical experiments with parallel orderings for ILU preconditioners
• Approximate sparsity patterns for the inverse of a matrix and preconditioning
• A comparative study of sparse approximate inverse preconditioners
• Iterative solution of large sparse systems of equations. Transl. from the German
• Scalable iterative solution of sparse linear systems
• Sparse approximate inverse smoothers for geometric and algebraic multigrid
• A parallel solver for large-scale Markov chains
• \textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
• Wavelet sparse approximate inverse preconditioners
• Experimental study of ILU preconditioners for indefinite matrices
• Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics
• Factorized sparse approximate inverses for preconditioning
• Vaidya's preconditioners: Implementation and experimental study
• Physics-based preconditioning and the Newton-Krylov method for non-equilibrium radiation diffusion
• Discrete wavelet transforms accelerated sparse preconditioners for dense boundary element systems
• A general parallel sparse-blocked matrix multiply for linear scaling SCF theory
• An incomplete Cholesky factorization for dense symmetric positive definite matrices
• Sparse approximate inverse and multilevel block ILU preconditioning techniques for general sparse matrices
• Iterative solution of linear systems in the 20th century
• Preconditioning eigenvalues and some comparison of solvers
• Multilevel ILU decomposition
• A multilevel block incomplete factorization preconditioning
• Weighted graph based ordering techniques for preconditioned conjugate gradient methods
• Numerical stability of GMRES
• A new pivoting strategy for Gaussian elimination
• Nested grids ILU-decomposition (NGILU)
• The two-level FETI method for static and dynamic plate problems I: An optimal iterative solver for biharmonic systems
• Ordering techniques for two- and three-dimensional convection-dominated elliptic boundary value problems
• Experimental comparison of three-dimensional point and line modified incomplete factorizations
• The fast multipole method: Numerical implementation
• Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix
• Generalized Augmented Matrix Preconditioning Approach and its Application to Iterative Solution of Ill-Conditioned Algebraic Systems
• Incomplete Multilevel Cholesky Factorizations
• A Multilevel Dual Reordering Strategy for Robust Incomplete LU Factorization of Indefinite Matrices
• On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix
• An Analysis of Sparse Approximate Inverse Preconditioners for Boundary Integral Equations
• Robust Approximate Inverse Preconditioning for the Conjugate Gradient Method
• Preconditioning Highly Indefinite and Nonsymmetric Matrices
• Flexible Conjugate Gradients
• A Structural Diagnosis of Some IC Orderings
• A Scalable Parallel Algorithm for Incomplete Factor Preconditioning
• Approximate inverse preconditioning in the parallel solution of sparse eigenproblems
• Factorized sparse approximate inverse preconditionings. IV: Simple approaches to rising efficiency
• Multiresolution Approximate Inverse Preconditioners
• Robust Parallel Smoothing for Multigrid Via Sparse Approximate Inverses
• An Algebraic Multilevel Multigraph Algorithm
• A Factored Approximate Inverse Preconditioner with Pivoting
• Ordering Effects on Relaxation Methods Applied to the Discrete One-Dimensional Convection-Diffusion Equation
• Algebraic Multilevel Preconditioning Methods, II
• A New Modified Cholesky Factorization
• Block Preconditioning for the Conjugate Gradient Method
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Analysis of a Multigrid Method as an Iterative Technique for Solving Linear Systems
• A robust incomplete Choleski-conjugate gradient algorithm
• Krylov Subspace Methods on Supercomputers
• A Block Ordering Method for Sparse Matrices
• Frequency domain behavior of a set of parallel multigrid smoothing operators
• A robust incomplete factorization based on value and space constraints
• Compressed Graphs and the Minimum Degree Algorithm
• Diagonally compensated reduction and related preconditioning methods
• New convergence results and preconditioning strategies for the conjugate gradient method
• ILUT: A dual threshold incomplete LU factorization
• Any Nonincreasing Convergence Curve is Possible for GMRES
• ILUM: A Multi-Elimination ILU Preconditioner for General Sparse Matrices
• A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method
• Wavelet Methods for Second-Order Elliptic Problems, Preconditioning, and Adaptivity
• A Flexible Inner-Outer Preconditioned GMRES Algorithm
• A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
• A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems
• ARMS: an algebraic recursive multilevel solver for general sparse linear systems
• pARMS: a parallel version of the algebraic recursive multilevel solver
• Combining Fast Multipole Techniques and an Approximate Inverse Preconditioner for Large Electromagnetism Calculations
• The speed of convergence of one iterative process
• A relaxation method for solving elliptic difference equations
• An Approximate Factorization Procedure for Solving Self-Adjoint Elliptic Difference Equations
• The Use of Pre-conditioning in Iterative Methods for Solving Linear Equations with Symmetric Positive Definite Matrices
• A generalized SSOR method
• Nested Dissection of a Regular Finite Element Mesh
• Limits on Parallelism in the Numerical Solution of Linear Partial Differential Equations
• ROUNDING-OFF ERRORS IN MATRIX PROCESSES
• NOTES ON THE SOLUTION OF ALGEBRAIC LINEAR SIMULTANEOUS EQUATIONS
• Methods of conjugate gradients for solving linear systems
• On the Numerical Solution of Elliptic Difference Equations
• FQMR: A Flexible Quasi-Minimal Residual Method with Inexact Preconditioning
• Numerical experiments with algebraic multilevel preconditioners
• A review of algebraic multigrid
• Parallel preconditioning of a sparse eigensolver
• Parallel incomplete factorizations with pseudo-overlapped subdomains
• Parallel algebraic multigrid based on subdomain blocking
• Parallel approximate factorization method for solving discrete elliptic equations
• Stabilized and block approximate inverse preconditioners for problems in solid and structural mechanics
• A robust ILU with pivoting based on monitoring the growth of the inverse factors
• A multilevel AINV preconditioner
• 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
• 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: Preconditioning techniques for large linear systems: A survey