求解Sylvester矩阵方程的一种改进的梯度方法

提出了一种改进的梯度迭代算法来求解Sylvester矩阵方程和Lyapunov矩阵方程.该梯度算法是通过构造一种特殊的矩阵分裂,综合利用Jaucobi迭代算法和梯度迭代算法的求解思路.与已知的梯度算法相比,提高了算法的迭代效率.同时研究了该算法在满足初始条件下的收敛性.数值算例验证了该算法的有效性.     

Weighted least squares solutions to general coupled Sylvester matrix equations

This paper is concerned with weighted least squares solutions to general coupled Sylvester matrix equations. Gradient based iterative algorithms are proposed to solve this problem. This type of iterative algorithm includes a wide class of iterative algorithms, and two special cases of them are studied in detail in this paper. Necessary and sufficient conditions guaranteeing the convergence of the proposed algorithms are presented. Sufficient conditions that are easy to compute are also given. The optimal step sizes such that the convergence rates of the algorithms, which are properly defined in this paper, are maximized and established. Several special cases of the weighted least squares problem, such as a least squares solution to the coupled Sylvester matrix equations problem, solutions to the general coupled Sylvester matrix equations problem, and a weighted least squares solution to the linear matrix equation problem are simultaneously solved. Several numerical examples are given to illustrate the effectiveness of the proposed algorithms.     

Weighted FOM and GMRES for solving nonsymmetric linear systems

This paper presents two new methods called WFOM and WGMRES, which are variants of FOM and GMRES, for solving large and sparse nonsymmetric linear systems. To accelerate the convergence, these new methods use a different inner product instead of the Euclidean one. Furthermore, at each restart, a different inner product is chosen. The weighted Arnoldi process is introduced for implementing these methods. After describing the weighted methods, we give the relations that link them to FOM and GMRES. Experimental results are presented to show the good performances of the new methods compared to FOM(m) and GMRES(m). This revised version was published online in August 2006 with corrections to the Cover Date.     

Implicitly restarted and deflated GMRES

We introduce a deflation method that takes advantage of the IRA method, by extracting a GMRES solution from the Krylov basis computed within the Arnoldi process of the IRA method itself. The deflation is well-suited because it is done with eigenvectors associated to the eigenvalues that are closest to zero, which are approximated by IRA very quickly. By a slight modification, we adapt it to the FOM algorithm, and then to GMRES enhanced by imposing constraints within the minimization condition. The use of IRA enables us to reduce the number of matrix-vector products, while keeping a low storage. This revised version was published online in June 2006 with corrections to the Cover Date.     

A modified gradient based algorithm for solving Sylvester equations

In this paper a modified gradient based algorithm for solving Sylvester equations is presented. Different from the gradient based method introduced by Ding and Chen [7] and the relaxed gradient based algorithm proposed by Niu et al. [18], the information generated in the first half-iterative step is fully exploited and used to construct the approximate solution. Theoretical analysis shows that the new method converges under certain assumptions. Numerical results are given to verify the efficiency of the new method.     

Iterative algorithms for solving a class of complex conjugate and transpose matrix equations

This paper is concerned with iterative solutions to a class of complex matrix equations, which include some previously investigated matrix equations as special cases. By applying the hierarchical identification principle, an iterative algorithm is constructed to solve this class of matrix equations. A sufficient condition is presented to guarantee that the proposed algorithm is convergent for an arbitrary initial matrix with a real representation of a complex matrix as tools. By using some properties of the real representation, a convergence condition that is easier to compute is also given in terms of original coefficient matrices. A numerical example is employed to illustrate the effectiveness of the proposed methods.     

Parallel algorithms for solving retrieval equations

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 28–36, Moscow State University, 1989.     

LSQR iterative method for generalized coupled Sylvester matrix equations

An iterative method is proposed to solve generalized coupled Sylvester matrix equations, based on a matrix form of the least-squares QR-factorization (LSQR) algorithm. By this iterative method on the selection of special initial matrices, we can obtain the minimum Frobenius norm solutions or the minimum Frobenius norm least-squares solutions over some constrained matrices, such as symmetric, generalized bisymmetric and (R, S)-symmetric matrices. Meanwhile, the optimal approximate solutions to the given matrices can be derived by solving the corresponding new generalized coupled Sylvester matrix equations. Finally, numerical examples are given to illustrate the effectiveness of the present method.     

A projection method and Kronecker product preconditioner for solving Sylvester tensor equations

The preconditioned iterative solvers for solving Sylvester tensor equations are considered in this paper.By fully exploiting the structure of the tensor equation,we propose a projection method based on the tensor format,which needs less flops and storage than the standard projection method.The structure of the coefficient matrices of the tensor equation is used to design the nearest Kronecker product(NKP) preconditioner,which is easy to construct and is able to accelerate the convergence of the iterative solver.Numerical experiments are presented to show good performance of the approaches.     

Alternating direction algorithms for solving Hamilton-Jacobi-Bellman equations

We focus on numerically solving a typical type of Hamilton-Jacobi-Bellman (HJB) equations arising from a class of optimal controls with a standard multidimensional diffusion model. Solving such an equation results in the value function and an optimal feedback control law. The Bellman's curse of dimensionality seems to be the main obstacle to applicability of most numerical algorithms for solving HJB. We decompose HJB into a number of lower-dimensional problems, and discuss how the usual alternating direction method can be extended for solving HJB. We present some convergence results, as well as preliminary experimental outcomes.This research was funded in part by an RGC grant from the University of Alabama.     

Parallel algorithms for solving large linear systems

The solution of linear systems continues to play an important role in scientific computing. The problems to be solved often are of very large size, so that solving them requires large computer resources. To solve these problems, at least supercomputers with large shared memory or massive parallel computer systems with distributed memory are needed.

This paper gives a survey of research on parallel implementation of various direct methods to solve dense linear systems. In particular are considered: Gaussian elimination, Gauss-Jordan elimination and a variant due to Huard (1979), and an algorithm due to Enright (1978), designed in relation to solving (stiff) ODEs, such that stepsize and other method parameters can easily be varied.

Some theoretical results are mentioned, including a new result on error analysis of Huard's algorithm. Moreover, practical considerations and results of experiments on supercomputers and on a distributed-memory computer system are presented.     

Numerical solution of Sylvester matrix equations with normal coefficients

Algorithms of the Bartels–Stewart type for the numerical solution of Sylvester matrix equations of modest size are modified for the case where the linear operators associated with these equations are normal. The superiority of the modified algorithms over the original ones is illustrated by numerical results.     

On restarted and deflated block FOM and GMRES methods for sequences of shifted linear systems

Numerical Algorithms - The problem of shifted linear systems is an important and challenging issue in a number of research applications. Krylov subspace methods are effective techniques for...     

Exploiting structure in piecewise-linear homotopy algorithms for solving equations

We consider the recent algorithms for computing fixed points or zeros of continuous functions fromR ⁿ to itself that are based on tracing piecewise-linear paths in triangulations. We investigate the possible savings that arise when these fixed-point algorithms with their usual triangulations are applied to computing zeros of functionsf with special structure:f is either piecewise-linear in certain variables, separable, or has Jacobian with small bandwidth. Each of these structures leads to a property we call modularity; the algorithmic path within a simplex can be continued into an adjacent simplex without a function evaluation or linear programming pivot. Modularity also arises without any special structure onf from the linearity of the function that is deformed tof. In the case thatf is separable we show that the path generated by Kojima's algorithm with the homotopyH ² coincides with the path generated by the standard restart algorithm of Merrill when the usual triangulations are employed. The extra function evaluations and linear programming steps required by the standard algorithm can be avoided by exploiting modularity.This research was performed while the author was visiting the Mathematics Research Center, University of Wisconsin-Madison, and was sponsored by the United States Army under Contract No. DAAG-29-75-C-0024 and by the National Science Foundation under Grant No. ENG76-08749.     

Efficient algorithms for solving tensor product finite element equations

Summary There are currently several highly efficient methods for solving linear systems associated with finite difference approximations of Poisson's equation in rectangular regions. These techniques are employed to develop both direct and iterative methods for solving the linear systems arising from the use ofC ⁰ quadratic orC ¹ cubic tensor product finite elements.