共查询到20条相似文献,搜索用时 32 毫秒
1.
Iterative methods are developed for computing the Moore-Penrose pseudoinverse solution of a linear system Ax= b, where A is an m × n sparse matrix. The methods do not require the explicit formation of A
T
A or AA
T
and therefore are advantageous to use when these matrices are much less sparse than A itself. The methods are based on solving the two related systems (i) x= A
T
y, AA
T
y= b, and (ii) A
T
Ax= A
T
b. First it is shown how the SOR-and SSOR-methods for these two systems can be implemented efficiently. Further, the acceleration of the SSOR-method by Chebyshev semi-iteration and the conjugate gradient method is discussed. In particular it is shown that the SSOR-cg method for (i) and (ii) can be implemented in such a way that each step requires only two sweeps through successive rows and columns of A respectively. In the general rank deficient and inconsistent case it is shown how the pseudoinverse solution can be computed by a two step procedure. Some possible applications are mentioned and numerical results are given for some problems from picture reconstruction. 相似文献
2.
For a rank-1 matrix A = ab
t, we define the perimeter of A as the number of nonzero entries in both a and b. We characterize the linear operators which preserve the rank and perimeter of rank-1 matrices over semifields. That is,
a linear operator T preserves the rank and perimeter of rank-1 matrices over semifields if and only if it has the form T( A) = U AV, or T( A) = U A
t
V with some invertible matrices U and V.
This work was supported by the research grant of the Cheju National University in 2006. 相似文献
3.
In this preliminary work, left and right conjugate direction vectors are defined for nonsymmetric, nonsingular matrices A and some properties of these vectors are studied. A left conjugate direction (LCD) method for solving nonsymmetric systems
of linear equations is proposed. The method has no breakdown for real positive definite systems. The method reduces to the
usual conjugate gradient method when A is symmetric positive definite. A finite termination property of the semi-conjugate direction method is shown, providing
a new simple proof of the finite termination property of conjugate gradient methods. The new method is well defined for all
nonsingular M-matrices. Some techniques for overcoming breakdown are suggested for general nonsymmetric A. The connection between the semi-conjugate direction method and LU decomposition is established. The semi-conjugate direction
method is successfully applied to solve some sample linear systems arising from linear partial differential equations, with
attractive convergence rates. Some numerical experiments show the benefits of this method in comparison to well-known methods.
This revised version was published online in July 2006 with corrections to the Cover Date. 相似文献
4.
Tikhonov regularization is one of the most popular methods for solving linear systems of equations or linear least-squares
problems with a severely ill-conditioned matrix A. This method replaces the given problem by a penalized least-squares problem. The present paper discusses measuring the residual
error (discrepancy) in Tikhonov regularization with a seminorm that uses a fractional power of the Moore-Penrose pseudoinverse
of AA
T
as weighting matrix. Properties of this regularization method are discussed. Numerical examples illustrate that the proposed
scheme for a suitable fractional power may give approximate solutions of higher quality than standard Tikhonov regularization. 相似文献
5.
The major drawback of the s-step iterative methods for nonsymmetric linear systems of equations is that, in the floating-point arithmetic, a quick loss
of orthogonality of s-dimensional direction subspaces can occur, and consequently slow convergence and instability in the algorithm may be observed
as s gets larger than 5. In [18], Swanson and Chronopoulos have demonstrated that the value of s in the s-step Orthomin(k) algorithm can be increased beyond s=5 by orthogonalizing the s direction vectors in each iteration, and have shown that the A TA-orthogonal s-step Orthomin(k) is stable for large values of s (up to s=16). The subject of this paper is to show how by using the CADNA library, it is possible to determine a good value of s for
A TA-orthogonal s-step Orthomin(k), and during the run of its code to detect the numerical instabilities and to stop the process correctly,
and to restart the A TA-orthogonal s-step Orthomin(k) in order to improve the computed solution. Numerical examples are used to show the good numerical properties.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
6.
We study and compare preconditioners available for network interior point methods. We derive upper bounds for the condition number of the preconditioned matrices used in the solution of systems of linear equations defining the algorithm search directions. The preconditioners are tested using PDNET, a state-of-the-art interior point code for the minimum cost network flow problem. A computational comparison using a set of standard problems improves the understanding of the effectiveness of preconditioners in network interior point methods. 相似文献
7.
During the iterations of interior point methods symmetric indefinite systems are decomposed by LD̂L
T
factorization. This step can be performed in a special way where the symmetric indefinite system is transformed to a positive
definite one, called the normal equations system. This approach proved to be efficient in most of the cases and numerically
reliable, due to the positive definite property. It has been recognized, however, that in case the linear program contains
“dense” columns, this approach results in an undesirable fill–in during the computations and the direct factorization of the
symmetric indefinite system is more advantageous. The paper describes a new approach to detect cases where the system of normal
equations is not preferable for interior point methods and presents a new algorithm for detecting the set of columns which
is responsible for the excessive fill–in in the matrix AA
T
. By solving large–scale linear programming problems we demonstrate that our heuristic is reliable in practice.
This work was supported in part by the Hungarian Scientific Research Fund OTKA K60480. 相似文献
8.
The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point
methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In
this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity
bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite
programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive). 相似文献
9.
The vast majority of linear programming interior point algorithms successively move from an interior solution to an improved interior solution by following a single search direction, which corresponds to solving a one-dimensional subspace linear program at each iteration. On the other hand, two-dimensional search interior point algorithms select two search directions, and determine a new and improved interior solution by solving a two-dimensional subspace linear program at each step. This paper presents primal and dual two-dimensional search interior point algorithms derived from affine and logarithmic barrier search directions. Both search directions are determined by randomly partitioning the objective function into two orthogonal vectors. Computational experiments performed on benchmark instances demonstrate that these new methods improve the average CPU time by approximately 12% and the average number of iterations by 14%. 相似文献
10.
This paper concerns with the properties of Hadamard product of inverse M‐matrices. Structures of tridiagonal inverse M‐matrices and Hessenberg inverse M‐matrices are analysed. It is proved that the product A ○ AT satisfies Willoughby's necessary conditions for being an inverse M‐matrix when A is an irreducible inverse M‐matrix. It is also proved that when A is either a Hessenberg inverse M‐matrix or a tridiagonal inverse M‐matrix then A ○ AT is an inverse M‐matrix. Based on these results, the conjecture that A ○ AT is an inverse M‐matrix when A is an inverse M‐matrix is made. Unfortunately, the conjecture is not true. Copyright © 2004 John Wiley Sons, Ltd. 相似文献
11.
We propose an interior point method for large-scale convex quadratic programming where no assumptions are made about the sparsity structure of the quadratic coefficient matrix Q. The interior point method we describe is a doubly iterative algorithm that invokes a conjugate projected gradient procedure to obtain the search direction. The effect is that Q appears in a conjugate direction routine rather than in a matrix factorization. By doing this, the matrices to be factored have the same nonzero structure as those in linear programming. Further, one variant of this method is theoretically convergent with only one matrix factorization throughout the procedure. 相似文献
12.
We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is
instead of reducing to obtain the usual AD
2
A
T system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product AD
2
A
T when A has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only that D be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense. 相似文献
13.
Given a square matrix A, the inverse subspace problem is concerned with determining a closest matrix to A with a prescribed invariant subspace. When A is Hermitian, the closest matrix may be required to be Hermitian. We measure distance in the Frobenius norm and discuss applications to Krylov subspace methods for the solution of large‐scale linear systems of equations and eigenvalue problems as well as to the construction of blurring matrices. Extensions that allow the matrix A to be rectangular and applications to Lanczos bidiagonalization, as well as to the recently proposed subspace‐restricted SVD method for the solution of linear discrete ill‐posed problems, also are considered.Copyright © 2013 John Wiley & Sons, Ltd. 相似文献
14.
In this paper, an interior point algorithm based on trust region techniques is proposed for solving nonlinear optimization problems with linear equality constraints and nonnegative variables. Unlike those existing interior-point trust region methods, this proposed method does not require that a general quadratic subproblem with a trust region bound be solved at each iteration. Instead, a system of linear equations is solved to get a search direction, and then a linesearch of Armijo type is performed in this direction to obtain a new iteration point. From a computational point of view, this approach may in general reduce a computational effort, and thus improve the computational efficiency. Under suitable conditions, it is proven that any accumulation of the sequence generated by the algorithm satisfies the first-order optimality condition. 相似文献
15.
Let F be a field, T n ( F) (respectively, N n ( F)) the matrix algebra consisting of all n × n upper triangular matrices (respectively, strictly upper triangular matrices) over F. A ∈ T n ( F) is said to be square zero if A 2 = 0. In this article, we firstly characterize non-singular linear maps on N n ( F) preserving square-zero matrices in both directions, then by using it we determine non-singular linear maps on T n ( F) preserving square-zero matrices in both directions. 相似文献
16.
In this paper, we consider the existence of quadratic Lyapunov functions for certain types of switched linear systems. Given a partition of the state-space, a set of matrices (linear dynamics), and a matrix-valued function A( x) constructed by associating these matrices with regions of the state-space in a manner governed by the partition, we ask whether there exists a positive definite symmetric matrix P such that A( x) TP+ PA( x) is negative definite for all x( t). For planar systems, necessary and sufficient conditions are given. Extensions for higher order systems are also presented. 相似文献
17.
We present results on how partial knowledge helps to solve linear programs. In particular, if a linear system, Ax= band x≥ 0, has an interior feasible point, then we show that finding a feasible point to this system can be done in O( n2.5c( A)) iterations by the layered interior-point method, and each iteration solves a least-squares problem, where nis the dimension of vector xand c( A) is the condition number of matrix Adefined by Vavasis and Ye. This complexity bound is reduced by a factor nfrom that when this property does not exists. We also present a result for solving the problem using a little strong knowledge. 相似文献
18.
In this paper we develop the Complex method; an algorithm for solving linear programming (LP) problems with interior search directions. The Complex Interior-Boundary method (as the name suggests) moves in the interior of the feasible region from one boundary point to another of the feasible region bypassing several extreme points at a time. These directions of movement are guaranteed to improve the objective function. As a result, the Complex method aims to reach the optimal point faster than the Simplex method on large LP programs. The method also extends to nonlinear programming (NLP) with linear constraints as compared to the generalized-reduced gradient.The Complex method is based on a pivoting operation which is computationally efficient operation compared to some interior-point methods. In addition, our algorithm offers more flexibility in choosing the search direction than other pivoting methods (such as reduced gradient methods). The interior direction of movement aims at reducing the number of iterations and running time to obtain the optimal solution of the LP problem compared to the Simplex method. Furthermore, this method is advantageous to Simplex and other convex programs in regard to starting at a Basic Feasible Solution (BFS); i.e. the method has the ability to start at any given feasible solution.Preliminary testing shows that the reduction in the computational effort is promising compared to the Simplex method. 相似文献
19.
Second-order cone programming (SOCP) problems are typically solved by interior point methods. As in linear programming (LP), interior point methods can, in theory, solve SOCPs in polynomial time and can, in practice, exploit sparsity in the problem data. Specifically, when cones of large dimension are present, the density that results in the normal equations that are solved at each iteration can be remedied in a manner similar to the treatment of dense columns in an LP. Here we propose a product-form Cholesky factorization (PFCF) approach, and show that it is more numerically stable than the alternative Sherman-Morrison-Woodbury approach. We derive several PFCF variants and compare their theoretical perfomance. Finally, we prove that the elements of L in the Cholesky factorizations LDLT that arise in interior point methods for SOCP are uniformly bounded as the duality gap tends to zero as long as the iterates remain is some conic neighborhood of the cental path. Mathematics Subject Classification (1991): 90C25, 90C51, 15A23Research supported in part by NSF Grants CDA 97-26385, DMS 01-04282, ONR Grant N000140310514 and DOE Grant GE-FG01-92ER-25126 相似文献
20.
Summary We discuss block matrices of the form A=[ A
ij
], where A
ij
is a k× k symmetric matrix, A
ij
is positive definite and A
ij
is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices. 相似文献
|