Solving A\underline x =\underline b Using a Modified Conjugate Gradient Method Based on Roots of A

We consider the modified conjugate gradient procedure for solving A = in which the approximation space is based upon the Krylov space associated with A ^1/p and , for any integer p. For the square-root MCG (p=2) we establish a sharpened bound for the error at each iteration via Chebyshev polynomials in . We discuss the implications of the quickly accumulating effect of an error in in the initial stage, and find an error bound even in the presence of such accumulating errors. Although this accumulation of errors may limit the usefulness of this method when is unknown, it may still be successfully applied to a variety of small, almost-SPD problems, and can be used to jump-start the conjugate gradient method. Finally, we verify these theoretical results with numerical tests.     

MCGS: A Modified Conjugate Gradient Squared Algorithm for Nonsymmetric Linear Systems

The conjugate gradient squared (CGS) algorithm is a Krylov subspace algorithm that can be used to obtain fast solutions for linear systems (Ax=b) with complex nonsymmetric, very large, and very sparse coefficient matrices (A). By considering electromagnetic scattering problems as examples, a study of the performance and scalability of this algorithm on two MIMD machines is presented. A modified CGS (MCGS) algorithm, where the synchronization overhead is effectively reduced by a factor of two, is proposed in this paper. This is achieved by changing the computation sequence in the CGS algorithm. Both experimental and theoretical analyses are performed to investigate the impact of this modification on the overall execution time. From the theoretical and experimental analysis it is found that CGS is faster than MCGS for smaller number of processors and MCGS outperforms CGS as the number of processors increases. Based on this observation, a set of algorithms approach is proposed, where either CGS or MGS is selected depending on the values of the dimension of the A matrix (N) and number of processors (P). The set approach provides an algorithm that is more scalable than either the CGS or MCGS algorithms. The experiments performed on a 128-processor mesh Intel Paragon and on a 16-processor IBM SP2 with multistage network indicate that MCGS is approximately 20% faster than CGS.     

自适应解卷积与二次型共轭梯度算法

提出一种新的解卷积算法，它是将卷积运算关系ｙｉ＝ｈｉ＊ｆｉ转换为解矩阵方程Ｙ＝ＡＨ．运算这个矩阵方程可实现卷积与解卷积。文中也给出解矩阵方程的优化算法、ＱＣＧ（二次型共轭梯度）算法。计算机模拟表明，新算法具有精度高、速度快、数据短和计算稳定等优点．     

Uzawa Conjugate Gradient Domain Decomposition Methods for Coupled Stokes Flows

This paper deals with nonoverlapping domain decomposition methods for two coupled Stokes flows, based on the duality theory. By introducing a fictitious variable in the transmission condition and using saddle-point equations, the problem is restated as a linearly constrained maximization problem. According to whether constraints are uncoupled Stokes problems or uncoupled Poisson problems, two Uzawa-type domain decomposition algorithms are proposed. The results of some numerical experiments on a model problem are given.     

Implementing Temporal-Difference Learning with the Scaled Conjugate Gradient Algorithm

This paper investigates the use of the scaled conjugate gradient (SCG) algorithm in temporal-difference (TD) learning for time series prediction. Special emphasis is given on the implementation details, after examining the theoretical background of the algorithm and the learning methodology and how these could be combined. Simple time series (linear, sinusoidal, etc.) as well as more complex ones, coming from real data, are used to examine the behavior of this novel combination of learning algorithm and methodology. Preliminary experimental results indicate that the implementation as presented in this paper indeed works, but the performance (in terms of learning speed and generalization ability) of TD learning using the SCG algorithm is not as good as expected, at least on the representative problems examined. An attempt to rationalize these results is presented.     

二维泊松问题的并行共轭梯度算法

该论文研究了利用并行共轭梯度算法求解二维泊松方程的方法,在由24台微机组成的机群上进行了实验。实验数据表明并行共轭梯度算法适用于求解二维泊松方程,它具有收敛快,可扩展性强的特点。在实验的基础上提出并验证了适用于并行共轭梯度算法的合理计算节点数的选择函数。     

Fast parallel Preconditioned Conjugate Gradient algorithms for robot manipulator dynamics simulation

In this paper fast parallel Preconditioned Conjugate Gradient (PCG) algorithms for robot manipulator forward dynamics, or dynamic simulation, problem are presented. By exploiting the inherent structure of the forward dynamics problem, suitable preconditioners are devised to accelerate the iterations. Also, based on the choice of preconditioners, a modified dynamic formulation is used to speedup both serial and parallel computation of each iteration. The implementation of the parallel algorithms on two interconnected processor arrays is discussed and their computation and communication complexities are analyzed. The simulation results for a Puma Arm are presented to illustrate the effectiveness of the proposed preconditioners. With a faster convergence due to preconditioning and a faster computation of iterations due to parallelization, the developed parallel PCG algorithms represent the fastest alternative for parallel computation of the problem withO(n) processors.     

基于共轭梯度法的FIR数字滤波器优化设计

针对高阶FIR数字滤波器要中高阶矩阵逆计算困难,提出了一种共轭梯度法的FIR线性相位数字滤波器的优化设计方法.方法的主要思想是采用共轭梯度法计算余弦基函数的加权系数,从而获得FIR滤波器的单位脉冲响应,使得设计出的FIR滤波器的频率响应与理想滤波器的频率响应的全局误差在整个通带和阻带的范围内最小.仿真结果表明,与其它优化设计方法相比,提出的优化设计方法不仅具有更小的逼近误差,而且过渡带窄,阻带衰耗更大.上述方法不涉及逆矩阵计算,因而计算量小,在FIR数字滤波器优化设计中具有重要的应用价值.     

Applications of the Conjugate Gradient method in optimal surface parameterizations

This paper concerns the solutions of very large symmetric semipositive definite (singular) linear systems involved in the problem of optimal surface parameterizations using inverse curvature mapping. Two approaches are presented that transform the singular linear systems into two kinds of symmetric positive definite linear systems, so that the famous Conjugate Gradient (CG) method can be used for solving them. Numerical experiments are run on two practical large problems to illustrate that the CG algorithm works very efficiently.     

Approximate Inverse Preconditioners for the Conjugate Gradient Method

The method of Conjugate Gradients is known to converge for symmetric positive definite systems of equations. This paper applies it to non-symmetric and ill-conditioned matrices. In order to facilitate convergence, an approximate inverse is used to precondition the Conjugate Gradient method. This is achieved by applying Newton's method. Three versions of Newton's method are introduced to compute the approximate inverse. Convergence of each version is compared. Numerical experimentation is done for some known "ill-conditioned" problems.     

A schmidt type process for the solution of Ax=b

An orthogonalization type algorithm is presented for the triangularization of the coefficient matrix of a system of linear algebraic equations. A backward error analysis is performed on the algorithm. Some numerical examples are presented. The algorithm is extended in order to perform the complete forward reduction.     

On the restrictively preconditioned conjugate gradient method for solving saddle point problems

Bai et al. [2003, IMA J Numer. Anal. 23, 561–580] proposed the restrictively preconditioned conjugate gradient (RPCG) method. In this paper, based on the special structure of saddle point systems, we consider the RPCG method and propose a new format. This new format can be obtained by applying the classical PCG method to a simpler system instead of the original format, which greatly reduces computational cost. The new format of the RPCG method can often attain almost the same convergence rate as the original one. In particular, for some practical problems, the former converges faster than the latter. Numerical experiments show the efficiency of the proposed format.     

A Modified Variational-Gradient Method for Quasilinear Equations

A modified variational-gradient method is proposed and substantiated for quasilinear operator equations in a Hilbert space.     

Comparison of Krylov subspace methods with preconditioning techniques for solving boundary value problems

In this paper, we made an attempt to establish the usefulness of Lanczos solver with preconditioning technique over the preconditioned Conjugate Gradient (CG) solvers. We have presented here a detail comparative study with respect to convergence, speed as well as CPU-time, by considering appropriate boundary value problems.     

梯度神经网络解线性矩阵方程之收敛性分析

为了求解线性矩阵方程问题,应用一种基于负梯度法的递归神经网络模型,并探讨了该递归神经网络实时求解线性矩阵方程的全局指数收敛问题.在讨论渐近收敛性基础上,进一步证明了该类神经网络在系数矩阵满足有解条件的情况下具有全局指数收敛性,在不能满足有解条件的情况下具有全局稳定性.计算机仿真结果证实了相关理论分析和该网络实时求解线性矩阵方程的有效性.     

Preconditioned Conjugate Gradient Method and Generalized Successive Overrelaxation Method for the Least Squares Problems

In a recent paper [4], Li et al . gave a generalized successive overrelaxation (GSOR) method for the least squares problems. In this paper, the connection between the GSOR method and the preconditioned conjugate gradient (PCG) method for the normal equations is investigated. It is shown that the PCG method is at least as fast as the GSOR method. Numerical examples demonstrates that the PCG method is much faster than the GSOR method.     

Sufficient descent conjugate gradient methods for large-scale optimization problems

Sufficient descent condition is very crucial in establishing the global convergence of nonlinear conjugate gradient method. In this paper, we modified two conjugate gradient methods such that both methods satisfy this property. Under suitable conditions, we prove the global convergence of the proposed methods. Numerical results show that the proposed methods are efficient for the given test problems.     

Pi-sigma神经网络的乘子法随机单点在线梯度算法*

在利用梯度算法训练Pi-sigma神经网络时,存在因权值选取过小导致收敛速度过慢的问题,而采用一般罚函数法虽然可以克服这个缺点,但要求罚因子必须趋近于∞且惩罚项绝对值不可微,从而导致数值求解困难。为克服以上缺点,提出了一种基于乘子法的随机单点在线梯度算法。利用最优化理论方法,将有约束问题转换为无约束问题,利用乘子法来求解网络误差函数。从理论上分析了算法的收敛速度和稳定性,仿真实验结果验证了算法的有效性。     

An Efficient Gradient Forecasting Search Method Utilizing the Discrete Difference Equation Prediction Model

Optimization theory and method profoundly impact numerous engineering designs and applications. The gradient descent method is simpler and more extensively used to solve numerous optimization problems than other search methods. However, the gradient descent method is easily trapped into a local minimum and slowly converges. This work presents a Gradient Forecasting Search Method (GFSM) for enhancing the performance of the gradient descent method in order to resolve optimization problems.GFSM is based on the gradient descent method and on the universal Discrete Difference Equation Prediction Model (DDEPM) proposed herein. In addition, the concept of the universal DDEPM is derived from the grey prediction model. The original grey prediction model uses a mathematical hypothesis and approximation to transform a continuous differential equation into a discrete difference equation. This is not a logical approach because the forecasting sequence data is invariably discrete. To construct a more precise prediction model, this work adopts a discrete difference equation. GFSM proposed herein can accurately predict the precise searching direction and trend of the gradient descent method via the universal DDEPM and can adjust prediction steps dynamically using the golden section search algorithm.Experimental results indicate that the proposed method can accelerate the searching speed of gradient descent method as well as help the gradient descent method escape from local minima. Our results further demonstrate that applying the golden section search method to achieve dynamic prediction steps of the DDEPM is an efficient approach for this search algorithm.