Optimizing and improving of the C-to-R method for solving complex symmetric linear systems

For complex symmetric linear systems, Axelsson et al. (2014) proposed the C-to-R method. In this paper, by further studying the C-to-R method with $W$ and $T$ being symmetric positive semidefinite, the optimal iteration parameter for the C-to-R method ${\alpha }_{opt}=\frac{\sqrt{2\sqrt{2}}}{2}$ is obtained and the C-to-R method is optimized. Furthermore, based on the optimized C-to-R method, we further propose an optimized preconditioner. Eigenvalue properties of the optimized preconditioned matrix are analyzed, which show that all the eigenvalues of the preconditioned matrix are located in tighter interval. Numerical results are presented, not only confirm the validity of the theoretical analysis, but also demonstrate the feasibility and effectiveness of the proposed optimized C-to-R method.     

On the Odir iterative method for non‐symmetric indefinite linear systems

Several Krylov subspace iterative methods have been proposed for the approximation of the solution of general non‐symmetric linear systems. Odir is such a method. Here we study the restarted version of Odir for non‐symmetric indefinite linear systems and we prove convergence under certain conditions on the matrix of coefficients. These results hold for all the restarted Krylov methods equivalent to Odir. We also introduce a new truncated Odir method which is proved to converge for a large class of non‐symmetric indefinite linear systems. This new method requires one‐half of the storage of the standard Odir. Copyright © 2001 John Wiley & Sons, Ltd.     

Convergences of splitting iterative methods for symmetric indefinite linear systems

In this paper, we generalize the saddle point problem to general symmetric indefinite systems, we also present a kind of convergent splitting iterative methods for the symmetric indefinite systems. A special divergent splitting is introduced. The sufficient condition is discussed that the eigenvalues of the iteration matrix are real. The spectral radius of the iteration matrix is discussed in detail, the convergence theories of the splitting iterative methods for the symmetric indefinite systems are obtained. Finally, we present a preconditioner and discuss the eigenvalues of preconditioned matrix.     

An EM-based iterative method for solving large sparse linear systems

ABSTRACT

We propose a novel iterative algorithm for solving a large sparse linear system. The method is based on the EM algorithm. If the system has a unique solution, the algorithm guarantees convergence with a geometric rate. Otherwise, convergence to a minimal Kullback–Leibler divergence point is guaranteed. The algorithm is easy to code and competitive with other iterative algorithms.     

Real valued iterative methods for solving complex symmetric linear systems

Complex valued systems of equations with a matrix R + 1S where R and S are real valued arise in many applications. A preconditioned iterative solution method is presented when R and S are symmetric positive semi‐definite and at least one of R, S is positive definite. The condition number of the preconditioned matrix is bounded above by 2, so only very few iterations are required. Applications when solving matrix polynomial equation systems, linear systems of ordinary differential equations, and using time‐stepping integration schemes based on Padé approximation for parabolic and hyperbolic problems are also discussed. Numerical comparisons show that the proposed real valued method is much faster than the iterative complex symmetric QMR method. Copyright © 2000 John Wiley & Sons, Ltd.     

关于解线性系统的一个有效的贝叶斯迭代方法

This paper concerns with the statistical methods for solving general linear systems. After a brief review of Bayesian perspective for inverse problems,a new and efficient iterative method for general linear systems from a Bayesian perspective is proposed.The convergence of this iterative method is proved,and the corresponding error analysis is studied.Finally, numerical experiments are given to support the efficiency of this iterative method,and some conclusions are obtained.     

The generalized HSS method for solving singular linear systems

For the singular, non-Hermitian, and positive semidefinite linear systems, we propose an alternating-direction iterative method with two parameters based on the Hermitian and skew-Hermitian splitting. The semi-convergence analysis and the quasi-optimal parameters of the proposed method are discussed. Moreover, the corresponding preconditioner based on the splitting is given to improve the semi-convergence rate of the GMRES method. Numerical examples are given to illustrate the theoretical results and the efficiency of the generalized HSS method either as a solver or a preconditioner for GMRES.     

Solving symmetric indefinite systems in an interior-point method for linear programming

We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite augmented systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite normal equations that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This work has been supported in part by National Science Foundation grants DDM-8908818 (Fourer) and CCR-8810107 (Mehrotra), and by a grant from GTE Laboratories (Mehrotra).     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

The extrapolated first order method for solving systems with complex eigenvalues

An extrapolated form of the basic first order stationary iterative method for solving linear systems when the associated iteration matrix possesses complex eigenvalues, is investigated. Sufficient (and necessary) conditions are given such that convergence is assured. An analytic determination of good (and sometimes optimum) values of the involved real parameter is presented in terms of certain bounds on the eigenvalues of the iteration matrix. The usefulness of the developed theory is shown through a simple application to the conventional Jacobi method.     

A COCR method for solving complex symmetric linear systems

The Conjugate Orthogonal Conjugate Gradient (COCG) method has been recognized as an attractive Lanczos-type Krylov subspace method for solving complex symmetric linear systems; however, it sometimes shows irregular convergence behavior in practical applications. In the present paper, we propose a Conjugate A$A$-Orthogonal Conjugate Residual (COCR) method, which can be regarded as an extension of the Conjugate Residual (CR) method. Numerical examples show that COCR often gives smoother convergence behavior than COCG.     

Preconditioned weighted full orthogonalization method for solving singular linear systems from PageRank problems

The PageRank model, which was first proposed by Google for its web search engine application, has since become a popular computational tool in a wide range of scientific fields, including chemistry, bioinformatics, neuroscience, bibliometrics, social networks, and others. PageRank calculations necessitate the use of fast computational techniques with low algorithmic and memory complexity. In recent years, much attention has been paid to Krylov subspace algorithms for solving difficult PageRank linear systems, such as those with large damping parameters close to one. In this article, we examine the full orthogonalization method (FOM). We present a convergence study of the method that extends and clarifies part of the conclusions reached in Zhang et al. (J Comput Appl Math. 2016; 296:397–409.). Furthermore, we demonstrate that FOM is breakdown free when solving singular PageRank linear systems with index one and we investigate the effect of using weighted inner-products instead of conventional inner-products in the orthonormalization procedure on FOM convergence. Finally, we develop a shifted polynomial preconditioner that takes advantage of the special structure of the PageRank linear system and has a good ability to cluster most of the eigenvalues, making it a good choice for an iterative method like FOM or GMRES. Numerical experiments are presented to support the theoretical findings and to evaluate the performance of the new weighted preconditioned FOM PageRank solver in comparison to other established solvers for this class of problem, including conventional stationary methods, hybrid combinations of stationary and Krylov subspace methods, and multi-step splitting strategies.     

Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems

A variant of balancing domain decomposition method by constraints (BDDC) is proposed for solving a class of indefinite systems of linear equations of the form (K?σ²M)u=f, which arise from solving eigenvalue problems when an inverse shifted method is used and also from the finite element discretization of Helmholtz equations. Here, both K and M are symmetric positive definite. The proposed BDDC method is closely related to the previous dual–primal finite element tearing and interconnecting method (FETI‐DP) for solving this type of problems (Appl. Numer. Math. 2005; 54 :150–166), where a coarse level problem containing certain free‐space solutions of the inherent homogeneous partial differential equation is used in the algorithm to accelerate the convergence. Under the condition that the diameters of the subdomains are small enough, the convergence rate of the proposed algorithm is established, which depends polylogarithmically on the dimension of the individual subdomain problems and which improves with a decrease of the subdomain diameters. These results are supported by numerical experiments of solving a two‐dimensional problem. Copyright © 2009 John Wiley & Sons, Ltd.     

A continuation method for solving symmetric Toeplitz systems

A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix T. The memory requirements for the algorithm are O(n), and its complexity is O(log κ(T)nlogn), where (T) is the condition number of T. Numerical results are presented that confirm the efficiency of the proposed algorithm.     

A new single-step iteration method for solving complex symmetric linear systems

For solving a class of complex symmetric linear systems, we introduce a new single-step iteration method, which can be taken as a fixed-point iteration adding the asymptotical error (FPAE). In order to accelerate the convergence, we further develop the parameterized variant of the FPAE (PFPAE) iteration method. Each iteration of the FPAE and the PFPAE methods requires the solution of only one linear system with a real symmetric positive definite coefficient matrix. Under suitable conditions, we derive the spectral radius of the FPAE and the PFPAE iteration matrices, and discuss the quasi-optimal parameters which minimize the above spectral radius. Numerical tests support the contention that the PFPAE iteration method has comparable advantage over some other commonly used iteration methods, particularly when the experimental optimal parameters are not used.     

A new block preconditioner for complex symmetric indefinite linear systems

Using the equivalent block two-by-two real linear systems and relaxing technique, we establish a new block preconditioner for a class of complex symmetric indefinite linear systems. The new preconditioner is much closer to the original block two-by-two coefficient matrix than the Hermitian and skew-Hermitian splitting (HSS) preconditioner. We analyze the spectral properties of the new preconditioned matrix, discuss the eigenvalue distribution and derive an upper bound for the degree of its minimal polynomial. Finally, some numerical examples are provided to show the effectiveness and robustness of our proposed preconditioner.     

A hybrid iterative method for symmetric indefinite linear systems

Hybrid iterative methods that combine a conjugate direction method with a simpler iteration scheme, such as Chebyshev or Richardson iteration, were first proposed in the 1950s. The ease with which Chebyshev and Richardson iteration can be implemented efficiently on a large variety of computer architectures has in recent years lead to renewed interest in iterative methods that use Chebyshev or Richardson iteration. This paper presents a new hybrid iterative method for the solution of linear systems of equations with a symmetric indefinite matrix. Our method combines the conjugate residual method with Richardson iteration. Special attention is paid to the determination of two real intervals, one on each side of the origin, that contain most of the eigenvalues of the matrix. These intervals are used to compute suitable iteration parameters for Richardson iteration. We also discuss when to switch between the methods. The hybrid scheme typically uses the Richardson method for most iterations, and this reduces the number of arithmetic vector operations significantly compared with the number of arithmetic vector operations required when only the conjugate residual method is used. Computed examples illustrate the competitiveness of the hybrid scheme.     

Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations

In this paper, we present a preconditioned variant of the generalized successive overrelaxation (GSOR) iterative method for solving a broad class of complex symmetric linear systems. We study conditions under which the spectral radius of the iteration matrix of the preconditioned GSOR method is smaller than that of the GSOR method and determine the optimal values of iteration parameters. Numerical experiments are given to verify the validity of the presented theoretical results and the effectiveness of the preconditioned GSOR method. Copyright © 2015 John Wiley & Sons, Ltd.     

A parameter shift-splitting iterative method for complex symmetric linear systems

Recently, Chen and Ma [Journal of Computational and Applied Mathematics, 344(2018): 691-700] constructed the generalized shift-splitting (GSS) preconditioner, and gave the corresponding theoretical analysis and numerical experiments. In this paper, based on the generalized shift-splitting (GSS) preconditioner, we generalize their algorithms and further study the parameter shift-splitting (PSS) preconditioner for complex symmetric linear systems. Moreover, by similar theoretical analysis, we obtain that the parameter shift-splitting iterative method is unconditionally convergent. In finally, one example is provided to confirm the effectiveness.     

A modified modulus method for symmetric positive‐definite linear complementarity problems

By reformulating the linear complementarity problem into a new equivalent fixed‐point equation, we deduce a modified modulus method, which is a generalization of the classical one. Convergence for this new method and the optima of the parameter involved are analyzed. Then, an inexact iteration process for this new method is presented, which adopts some kind of iterative methods for determining an approximate solution to each system of linear equations involved in the outer iteration. Global convergence for this inexact modulus method and two specific implementations for the inner iterations are discussed. Numerical results show that our new methods are more efficient than the classical one under suitable conditions. Copyright © 2008 John Wiley & Sons, Ltd.