Based on the recently developed ABS algorithm for solving linear Diophantine equations, we present a special ABS algorithm for solving such equations which is effective in computation and storage, not requiring the co...
详细信息
Based on the recently developed ABS algorithm for solving linear Diophantine equations, we present a special ABS algorithm for solving such equations which is effective in computation and storage, not requiring the computation of the greatest common divisor. A class of equations always solvable in integers is identified. Using this result, we discuss the ILP problem with upper and lower bounds on the variables.
The implicit lu algorithm of the (basic) ABS class corresponds to the parameter choices H-1= I, z(i) = w(i) = e(i). The algorithm can be considered as the ABS version of the classic lu factorization algorithm. In this...
详细信息
The implicit lu algorithm of the (basic) ABS class corresponds to the parameter choices H-1= I, z(i) = w(i) = e(i). The algorithm can be considered as the ABS version of the classic lu factorization algorithm. In this paper we consider the generalization where the initial matrix H-1 is arbitrary except for a certain condition. We prove that every algorithm in the ABS class is equivalent, in the sense of generating the same set of search directions, to a generalized implicit lu algorithm, with suitable initial matrix, that can be interpreted as a right preconditioning matrix. We discuss some consequences of this result, including a straightforward derivation of Bienayme's (1853) classical result on the equivalence of the Gram-Schmidt orthogonalization procedure with Gaussian elimination on the normal equations.
We describe an algorithm of the ABS class, which solves a general nonsingular linear system in n(3)/3 + 0(n(2)) multiplications without the assumption that the coefficient matrix be regular. The method can be viewed a...
详细信息
We describe an algorithm of the ABS class, which solves a general nonsingular linear system in n(3)/3 + 0(n(2)) multiplications without the assumption that the coefficient matrix be regular. The method can be viewed as a variation of the implicit lu algorithm of the ABS class, whose associated factorization contains a factor which is not triangular (but can be reduced to triangular form after suitable row permutations). We describe properties of the method, including in particular an efficient way of updating the Abaffan matrix after column interchanges. Such a problem arises in the application to the simplex algorithm, where the implicit LX algorithm provides a faster technique than the standard lu factorization for the pivoting operation if the number of equality constraints m is greater than n/2.
One of the most important problems in numerical analysis and numerical optimization is to solve a linear system of equations. Sometimes it should be repeated when one of the equations is replaced by a new one. In this...
详细信息
One of the most important problems in numerical analysis and numerical optimization is to solve a linear system of equations. Sometimes it should be repeated when one of the equations is replaced by a new one. In this paper as a result of theoretical analysis, an algorithm model and a particular algorithm which are based on the ABS class are proposed. After the original linear system has been solved by the ABS class, the algorithms proposed here can efficiently solve the new system which is obtained from the original system by replacing one of its equations by using information obtained in the previous computation. These algorithms can be used continually when some equations of the original system are replaced by new equations successively with less computation effort.
暂无评论