s-step iterative methods for symmetric linear systems
From MaRDI portal
S-step iterative methods for symmetric linear systems
The authors introduce and study the s-step conjugate gradient (CG) method for solving systems \(Ax=b\) of linear algebraic equations with a symmetric and positive definite system matrix A. In the s-step CG-method, the new iterate \(x_{i+1}=x_ ia^ 1_ ip^ 1_ i+...+a^ s_ ip^ s_ i\) is defined by minimizing the A-energy norm \(\| x_{i+1}-x\|_ A\) of the iteration error over \(\{x_ i+\sum^{s}_{j=1}a^ j_ ip^ j_ i\}\), where the search directions \(p^ j_ i=A^{j-1}r_ i+\sum^{s}_{k=1}b_{i-1}^{(j,k)}p^ k_{i-1}\), \(j=1,2,...,s\), are forced to be A-orthogonal to the preceding s directions, where \(r_ i=f-Ax_ i.\) From a theoretical point of view, s steps of the classical CG method are identical to one step of the s-step CG-method. However, there are several advantages of the s-step CG-method over the classical CG-method for parallel processing, e.g. a more appropriate data access and the simultaneous calculation of 2s inner products. In analogy to the s-step CG-method, the authors also discuss the s-step conjugate residual method. Stability investigations are made with respect to s. Finally, the authors present some numerical results in order to show the speed-up obtained on the multiprocessor system ALLIANT FX/8.
Recommendations
- s-Step Iterative Methods for (Non)Symmetric (In)Definite Linear Systems
- A hybrid iterative method for symmetric positive definite linear systems
- On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchy
- A generalization of s-step variants of gradient methods
- Parallel iterative S-step methods for unsymmetric linear systems
Cites work
- An Iterative Least-Square Method Suitable for Solving Large Sparse Matrices
- Block Preconditioning for the Conjugate Gradient Method
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- scientific article; zbMATH DE number 3215568 (Why is no real title available?)
- scientific article; zbMATH DE number 3057625 (Why is no real title available?)
- Methods of conjugate gradients for solving linear systems
- Moments and characteristic roots
- Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method
- On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method
- On the asymptotic directions of the s-dimensional optimum gradient method
- On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchy
- On the Lanczos Method for Solving Symmetric Linear Systems with Several Right-Hand Sides
- The block conjugate gradient algorithm and related methods
- The block preconditioned conjugate gradient method on vector computers
- The Conjugate Gradient Method for Linear and Nonlinear Operator Equations
- Über einige Methoden der Relaxationsrechnung
Cited in
(63)- Non-adaptive and adaptive SAOR-CG algorithms
- An efficient nonsymmetric Lanczos method on parallel vector computers
- Matrix-free GPU implementation of a preconditioned conjugate gradient solver for anisotropic elliptic PDEs
- On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchy
- Projection-minimization methods for nonsymmetric linear systems
- Reducing the effect of global communication in \(\text{GMRES} (m)\) and CG on parallel distributed memory computers
- A hybrid iterative method for symmetric positive definite linear systems
- The techniques for constructing a family of symmetric multistep methods
- Scalability pipelined algorithm of the conjugate gradient method on heterogeneous platforms
- Analysis and practical use of flexible biCGStab
- Numerical results on the SD and CG methods for slightly non-symmetric matrices
- Enlarged Krylov subspace conjugate gradient methods for reducing communication
- Pipelined, flexible Krylov subspace methods
- Minimizing synchronization in \(\text{IDR}(s)\).
- Two implementations of the preconditioned conjugate gradient method on heterogeneous computing grids
- Block-s-step Krylov iterative methods
- Parallel finite element technique using Gaussian belief propagation
- Minimizing synchronizations in sparse iterative solvers for distributed supercomputers
- The non-symmetric \(s\)-step Lanczos algorithm: derivation of efficient recurrences and synchronization-reducing variants of BiCG and QMR
- A Positive Barzilai–Borwein-Like Stepsize and an Extension for Symmetric Linear Systems
- Efficient Implementations of Certain Iterative Methods
- s-Step Iterative Methods for (Non)Symmetric (In)Definite Linear Systems
- Parallelizable restarted iterative methods for nonsymmetric linear systems. II: parallel implementation
- A generalization of s-step variants of gradient methods
- scientific article; zbMATH DE number 1977309 (Why is no real title available?)
- The numerical stability analysis of pipelined conjugate gradient methods: historical context and methodology
- The adaptive s-step conjugate gradient method
- Avoiding Communication in Primal and Dual Block Coordinate Descent Methods
- Introduction to communication avoiding algorithms for direct methods of factorization in linear algebra
- Multiple search direction conjugate gradient method II: theory and numerical experiments
- Communication lower bounds and optimal algorithms for numerical linear algebra
- scientific article; zbMATH DE number 1894318 (Why is no real title available?)
- Multiple search direction conjugate gradient method I: methods and their propositions
- Improving the arithmetic intensity of multigrid with the help of polynomial smoothers.
- Delayed gradient methods for symmetric and positive definite linear systems
- Predict-and-Recompute Conjugate Gradient Variants
- Scalable asynchronous domain decomposition solvers
- On the Convergence Rate of Variants of the Conjugate Gradient Algorithm in Finite Precision Arithmetic
- s-step enlarged Krylov subspace conjugate gradient methods
- Communication Avoiding ILU0 Preconditioner
- Accuracy of the s-Step Lanczos Method for the Symmetric Eigenproblem in Finite Precision
- Pipelined iterative solvers with kernel fusion for graphics processing units
- A s-step variant of the double orthogonal series algorithm
- Analyzing the effect of local rounding error propagation on the maximal attainable accuracy of the pipelined conjugate gradient method
- Algorithmic optimizations of a conjugate gradient solver on shared memory architectures
- Iterative methods for unsymmetric linear systems
- Developing variable s-step CGNE and CGNR algorithms for non-symmetric linear systems
- Finding solution of linear systems via new forms of BiCG, BiCGstab and CGS algorithms
- A numerically stable communication-avoiding s-step GMRES algorithm
- Parallel iterative S-step methods for unsymmetric linear systems
- The detection and correction of silent errors in pipelined Krylov subspace methods
- Analysis of randomized Householder-Cholesky QR factorization with multisketching
- Variable s-step generalized semi-conjugate gradient algorithm for solving nonsymmetric linear systems arising in signal recovery
- Variable s-step technique for planar algorithms in solving indefinite linear systems
- Efficient image reconstruction via regularized variable s-step conjugate gradient method for Sylvester matrix equations
- Variable s-step technique for new conjugate residual algorithms for solving non-square linear systems arising in control problems
- A speed up strategy for gradient methods
- Accelerating the Conjugate Gradient Method by Solving Multiple GPU-Parallelized Duplicate Systems
- Gradient adaptive parameter method for coupled matrix equations with applications in transient heat conduction problem and image steganography
- An adaptive \(s\)-step conjugate gradient algorithm with dynamic basis updating.
- Implementation of an adaptive algorithm for Richardson's method
- A parallel alternating direction implicit preconditioning method
- High performance inverse preconditioning
This page was built for publication: s-step iterative methods for symmetric linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1118971)
