Numerical behavior of LP algorithms based upon the decomposition principle

We present a set of LP problems, each of which illustrates a particular numerical feature of the Dantzig-Wolfe decomposition algorithm. Although these particular examples each involve only a few constraints and variables, they identify numerical difficulties that can occur in general. Some implications for the implementation of decomposition algorithms in a numerically sound way are briefly discussed.     

A CLASS OF DECOMPOSITION METHODS FOR LARGE-SCALE SYSTEMS OF NONLINEAR EQUATIONS

This paper presents a new decomposition method for solving large-scale systems of nonlinear equations. The new method is of superlinear convergence speed and has rather less computa tional complexity than the Newton-type decomposition method as well as other known numerical methods, Primal numerical experiments show the superiority of the new method to the others.     

Numerical solutions of the Laplace’s equation

This paper uses the sinc methods to construct a solution of the Laplace’s equation using two solutions of the heat equation. A numerical approximation is obtained with an exponential accuracy. We also present a reliable algorithm of Adomian decomposition method to construct a numerical solution of the Laplace’s equation in the form a rapidly convergence series and not at grid points. Numerical examples are given and comparisons are made to the sinc solution with the Adomian decomposition method. The comparison shows that the Adomian decomposition method is efficient and easy to use.     

Irreducible Numerical Semigroups Having Toms Decomposition

In this article we prove that if S is an irreducible numerical semigroup and S is generated by an interval or S has multiplicity 3 or 4, then it enjoys Toms decomposition. We also prove that if a numerical semigroup can be expressed as an expansion of a numerical semigroup generated by an interval, then it is irreducible and has Toms decomposition.     

The oversemigroups of a numerical semigroup

We study the set of numerical semigroups containing a given numerical semigroup. As an application we prove characterizations of irreducible numerical semigroups that unify some of the existing characterizations for symmetric and pseudo-symmetric numerical semigroups. Finally we describe an algorithm for computing a minimal decomposition of a numerical semigroup in terms of irreducible numerical semigroups.     

A class of Dantzig–Wolfe type decomposition methods for variational inequality problems

We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig–Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with certain types of set-valued or nonmonotone operators, as well as with various kinds of approximations in the subproblems of the functions and derivatives in the single-valued case. Also, subproblems may be solved approximately. Convergence is established under reasonable assumptions. We also report numerical experiments for computing variational equilibria of the game-theoretic models of electricity markets. Our numerical results illustrate that the decomposition approach allows to solve large-scale problem instances otherwise intractable if the widely used PATH solver is applied directly, without decomposition.     

The Oversemigroups of a Numerical Semigroup

Abstract. We study the set of numerical semigroups containing a given numerical semigroup. As an application we prove characterizations of irreducible numerical semigroups that unify some of the existing characterizations for symmetric and pseudo-symmetric numerical semigroups. Finally we describe an algorithm for computing a minimal decomposition of a numerical semigroup in terms of irreducible numerical semigroups.     

The product-product singular value decomposition of matrix triplets

A new decomposition of a matrix triplet (A, B, C) corresponding to the singular value decomposition of the matrix productABC is developed in this paper, which will be termed theProduct-Product Singular Value Decomposition (PPSVD). An orthogonal variant of the decomposition which is more suitable for the purpose of numerical computation is also proposed. Some geometric and algebraic issues of the PPSVD, such as the variational and geometric interpretations, and uniqueness properties are discussed. A numerical algorithm for stably computing the PPSVD is given based on the implicit Kogbetliantz technique. A numerical example is outlined to demonstrate the accuracy of the proposed algorithm.The work was partially supported by NSF grant DCR-8412314.     

Analytical and numerical solutions of a one-dimensional fractional-in-space diffusion equation in a composite medium

In this paper a one-dimensional space fractional diffusion equation in a composite medium consisting of two layers in contact is studied both analytically and numerically. Since domain decomposition is the only approach available to solve this problem, we at first investigate analytical and numerical strategies for a composite medium with the same fractal dimension in each layer to ascertain which domain decomposition approach is the most accurate and consistent with a global solution methodology, which is available in this case. We utilise a matrix representation of the fractional-in-space operator to generate a system of linear ODEs with the matrix raised to the same fractional exponent. We show that the global and domain decomposition numerical strategies for this problem produce simulation results that are in good agreement with their analytic counterparts and conclude that the domain decomposition that imposes the Neumann condition at the interface produces the most consistent results. Finally, we carry this finding to study the composite problem with different fractal dimensions, where we again favourably compare analytic and numerical solutions. The resulting method can be naturally extended to space fractional diffusion in a composite medium consisting of more than two layers.     

非定常Burgers方程基于POD方法的全二阶差分格式降阶外推算法

利用特征投影分解方法和奇值分解技术对非定常Burgers 方程的经典全二阶有限差分格式做降阶处理, 给出一种时间和空间变量都是二阶精度的降阶差分格式, 并给出这种降阶全二阶精度差分解的误差估计和外推算法的实现, 最后用数值例子说明数值结果与理论结果是相吻合的.     

A comparative study of numerical methods for solving the generalized Ito system

This paper is devoted to the numerical comparison of methods applied to solve the generalized Ito system. Four numerical methods are compared, namely, the Laplace decomposition method (LDM), the variation iteration method (VIM), the homotopy perturbation method (HPM) and the Laplace decomposition method with the Pade approximant (LD–PA) with the exact solution.     

Symmetric-Triangular Decomposition and its Applications Part I: Theorems and Algorithms

A new decomposition of a nonsingular matrix, the Symmetric times Triangular (ST) decomposition, is proposed. By this decomposition, every nonsingular matrix can be represented as a product of a symmetric matrix S and a triangular matrix T. Furthermore, S can be made positive definite. Two numerical algorithms for computing the ST decomposition with positive definite S are presented.     

Use of Adomian decomposition method in the study of parallel plate flow of a third grade fluid

In this paper, Adomian’s decomposition method is used to solve non-linear differential equations which arise in fluid dynamics. We study basic flow problems of a third grade non-Newtonian fluid between two parallel plates separated by a finite distance. The technique of Adomian decomposition is successfully applied to study the problem of a non-Newtonian plane Couette flow, fully developed plane Poiseuille flow and plane Couette–Poiseuille flow. The results obtained show the reliability and efficiency of this analytical method. Numerical solutions are also obtained by solving non-linear ordinary differential equations using Chebyshev spectral method. We present a comparative study between the analytical solutions and numerical solutions. The analytical results are found to be in good agreement with numerical solutions which reveals the effectiveness and convenience of the Adomian decomposition method.     

抛物方程基于POD方法的降阶外推差分算法

用奇值分解和特征投影分解(Proper Orthogonal Decomposition,简记POD)方法去建立抛物方程的一种降阶外推有限差分算法,并给出误差估计.最后用数值例子验证这种基于POD方法降阶外推有限差分算法的可行性和有效性.     

The approximate and exact solutions of the space- and time-fractional Burgers equations with initial conditions by variational iteration method

In this paper, a scheme is developed to study numerical solution of the space- and time-fractional Burgers equations with initial conditions by the variational iteration method (VIM). The exact and numerical solutions obtained by the variational iteration method are compared with that obtained by Adomian decomposition method (ADM). The results show that the variational iteration method is much easier, more convenient, and more stable and efficient than Adomian decomposition method. Numerical solutions are calculated for the fractional Burgers equation to show the nature of solution as the fractional derivative parameter is changed.     

Column aggregation and primal decomposition in linear programming: some observations

In this paper we present a way to interpret column aggregation schemes in linear programming as a special kind of primal decomposition. This relation between aggregation and decomposition is obtained through a reformulation of the original problem by the introduction of auxiliary variables. The relation between aggregation and decomposition yields a natural iterative aggregation scheme, where weights updating can be done in different ways. We describe several weight updating schemes and illustrate three of them within an iterative aggregation technique with a numerical example. Finally we point out some new research issues that appear when the aggregation process is viewed in this decomposition framework     

Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems

In this article, we consider three decomposition techniques for permutation scheduling problems. We introduce a general iterative decomposition algorithm for permutation scheduling problems and apply it to the permutation flow shop scheduling problem. We also develop bounds needed for this iterative decomposition approach and compare its computational requirements to that of the traditional branch and bound algorithms. Two heuristic algorithms based on the iterative decomposition approach are also developed. extensive numerical study indicates that the heuristic algorithms are practical alternatives to very costly exact algorithms for large flow shop scheduling problems.     

Differential equations for the analytic singular value decomposition of a matrix

Summary This paper is concerned with finding a smooth singular value decomposition for a matrix which is smoothly dependent on a parameter. A previous approach to this problem was based on minimisation techniques, here, in contrast, a system of ordinary differential equations is derived for the decomposition. It is shown that the numerical solution of an initial value problem associated with these differential equations provides a feasible approach to the solution of this problem. Particular consideration is given to the situation which arises with equal modulus singular values which lead to indeterminacies in the evaluations needed for the numerical solution. Examples which illustrate the behaviour of the method are included.     

Solution of dual fuzzy polynomial equations by modified Adomian decomposition method

In this paper, we present some efficient numerical algorithm for solving dual fuzzy polynomial equations based on Newton’s method. The modified Adomian decomposition method is applied to construct the numerical algorithms. Some numerical illustrations are given to show the efficiency of the algorithms.     

A numerical solution of Blasius equation by Adomian’s decomposition method and comparison with homotopy perturbation method

In this paper, Adomian’s decomposition method is proposed to solve the well-known Blasius equation. Comparison with homotopy perturbation method and Howarth’s numerical solution reveals that the Adomian’s decomposition method is of high accuracy.