AE1: An extension matrix approximate method for the general covering problem

A new approach, the extension matrix approach, is introduced and used to show that some optimization problems in general covering problem areNP-hard. Approximate solutions for these problems are given. Combining these approximate solutions, this paper presents an approximately optimal covering algorithm,AE1. Implementation shows thatAE1 is efficient and gives optimal or near optimal results.This research was supported in part by the National Science Foundation under Grant DCR 84-06801, Office of Naval Research under Grant N00014-82-K-0186, Defense Advanced Research Project Agency under Grant N00014-K-85-0878, and Education Ministry of the People's Republic of China.On leave from Harbin Institute of Technology, Harbin, China.     

An iterative algorithm for a least squares solution of a matrix equation

In this article, we propose an iterative algorithm to compute the minimum norm least-squares solution of AXB+CYD=E, based on a matrix form of the algorithm LSQR for solving the least squares problem. We then apply this algorithm to compute the minimum norm least-squares centrosymmetric solution of min _X ‖AXB?E‖ _F . Numerical results are provided to verify the efficiency of the proposed method.     

An iterative algorithm for approximate orthogonalisation of symmetric matrices

In a previous article, one of the authors presented an extension of an iterative approximate orthogonalisation algorithm, due to Z. Kovarik, for arbitrary rectangular matrices. In the present article, we propose a modified version of this extension for the class of arbitrary symmetric matrices. For this new algorithm, the computational effort per iteration is much smaller than for the initial one. We prove its convergence and also derive an error reduction factor per iteration. In the second part of the article, we show that we can eliminate the matrix inversion required by the previous algorithm in each iteration, by replacing it with a polynomial matrix expression. Some numerical experiments are also presented for a collocation discretisation of a first kind integral equation.     

An approximate solution to a jit-based ordering system

In this paper we consider a multi-stage multi-product production, inventory and transportation system including lot production processes and develop a goal programming model for a pull type ordering system based on the concept of a Just-In-Time(JIT) production system. We also present a pragmatic approach which reduces the required computational time for the formulated mixed integer goal programming problem using a mathematical programming modeling language. The proposed solution procedure is realized utilizing the post-optimal analysis which can be performed by the modeling language.     

Least-squares symmetric solution to the matrix equation AXB = C with the norm inequality constraint

In this paper, an iterative method to compute symmetric least-squares solution of the matrix equation AXB = C with the norm inequality constraint is proposed. For this method, without the error of calculation, a desired solution can be obtained with finitely iterate steps. Numerical experiments are performed to illustrate the efficiency and application of the algorithm.     

Conformal mapping for the efficient MFS solution of Dirichlet boundary value problems

In this work, we use conformal mapping to transform harmonic Dirichlet problems of Laplace’s equation which are defined in simply-connected domains into harmonic Dirichlet problems that are defined in the unit disk. We then solve the resulting harmonic Dirichlet problems efficiently using the method of fundamental solutions (MFS) in conjunction with fast fourier transforms (FFTs). This technique is extended to harmonic Dirichlet problems in doubly-connected domains which are now mapped onto annular domains. The solution of the resulting harmonic Dirichlet problems can be carried out equally efficiently using the MFS with FFTs. Several numerical examples are presented.      

The approximate solution of the Euclidean traveling salesman problem on a CRAY X-MP

The efficient use of MIMD computers calls for a careful choice of adequate algorithms as for an implementation taking into account the particular architecture. To demonstrate these facts, a parallel algorithm to find an approximate solution to the Euclidean Traveling Salesman Problem (ETSP) is presented. The algorithm is a parallelization of Karp's partitioning algorithm. It is a divide-and-conquer method for solving the ETSP approximately. Since the successor vertex to any vertex in the tour is usually a nearby vertex, the problem can be ‘geographically’ partitioned into subproblems which then can be solved independently. The resulting subtours can be combined into a single tour which is an approximate solution to the ETSP. The algorithm is implemented on a CRAY X-MP with two and four processors, and results using macrotasking and microtasking are presented.     

On the solution of a nonlinear matrix equation for MIMO symmetric realizations

A result concerning a particular solution of a nonlinear solution matrix equation reported in a previous paper [2] and interesting for studying SISO systems, is extended to MIMO symmetric realizations. For such a class of systems other important SISO results can be generalized.     

An improved parallel Jacobi method for diagonalizing a symmetric matrix

We compare five implementations of the Jacobi method for diagonalizing a symmetric matrix. Two of these, the classical Jacobi and sequential sweep Jacobi, have been used on sequential processors. The third method, the parallel sweep Jacobi, has been proposed as the method of choice for parallel processors. The fourth and fifth methods are believed to be new. They are similar to the parallel sweep method but use different schemes for selecting the rotations.

The classical Jacobi method is known to take O(n⁴) time to diagonalize a matrix of order n. We find that the parallel sweep Jacobi run on one processor is about as fast as the sequential sweep Jacobi. Both of these methods take O(n³ log₂n) time. One of our new methods also takes O(n³ log₂n) time, but the other one takes only O(n³) time. The choice among the methods for parallel processors depends on the degree of parallelism possible in the hardware. The time required to diagonalize a matrix on a variety of architectures is modeled.

Unfortunately for proponents of the Jacobi method, we find that the sequential QR method is always faster than the Jacobi method. The QR method is faster even for matrices that are nearly diagonal. If we perform the reduction to tridiagonal form in parallel, the QR method will be faster even on highly parallel systems.     

Efficient approximate solution methods for the multi-commodity capacitated multi-facility Weber problem

The capacitated multi-facility Weber problem is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity. This is a nonconvex optimization problem and difficult to solve. In this work, we focus on a multi-commodity extension and consider the situation where K distinct commodities are shipped subject to capacity constraints between each customer and facility pair. Customer locations, demands and capacities for each commodity, and bundle restrictions are known a priori. The transportation costs, which are proportional to the distance between customers and facilities, depend on the commodity type. We address several location-allocation and discrete approximation heuristics using different strategies. Based on the obtained computational results we can say that the alternate solution of location and allocation problems is a very efficient strategy; but the discrete approximation has excellent accuracy.     

A method for the numerical solution of some elliptic boundary value problems for a strip

A boundary integral equation for the numerical solution of a class of elliptic boundary value problems for a strip is derived. The equation should be particularly useful for the solution of an important class of problems governed by Laplace's equation and also for the solution of relevant problems in anisotropic thermostatics and elastostatics     

A method for numerical solution of a multidimensional convection-diffusion problem

We propose a modification of the additive splitting algorithm to solve the convection-diffusion problem using an efficient finite-difference scheme. The modification decreases the number of data exchanges and their amount during the numerical solution of a system of multidimensional equations. Approximation, stability, and convergence are considered. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 100–107, January–February 2009.     

A multi-dimensional shooting algorithm for the two-facility location–allocation problem with dense demand

We develop an efficient allocation-based solution framework for a class of two-facility location–allocation problems with dense demand data. By formulating the problem as a multi-dimensional boundary value problem, we show that previous results for the discrete demand case can be extended to problems with highly dense demand data. Further, this approach can be generalized to non-convex allocation decisions. This formulation is illustrated for the Euclidean metric case by representing the affine bisector with two points. A specialized multi-dimensional shooting algorithm is presented and illustrated on an example. Comparisons with two alternative methods through a computational study confirm the efficiency of the proposed methodology.     

Cooperative control for target-capturing task based on a cyclic pursuit strategy

This paper studies a methodology for group coordination and cooperative control of n agents to achieve a target-capturing task in 3D space. The proposed approach is based on a cyclic pursuit strategy, where agent i simply pursues agent i+1 modulo n. The distinctive features of the proposed method are as follows. First, no communication mechanism between agents is necessary and thus it is inherently a distributed control strategy. Also, it is a simple robust memoryless control scheme which has self-stability property. Finally, it guarantees a global convergence of all agents to the desired formation. Further, it is also guaranteed that no collision occurs. Simulation examples are given to illustrate the efficacy of the proposed method and the achievement of a desired pursuit pattern in 3D space.     

Deriving a discrete approximate solution for a nonlinear dynamic system of two-phase soil media

A discrete approximate generalized solution is derived for a nonlinear differential model of the dynamics of two-phase soil media and its convergence is estimated for the corresponding generalized solution in the space W ₂ ¹ (Ω). Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 69–80, July–August 2009     

A new method for computing a solution of the Cauchy problem with polynomial data for the system of crystal optics

A new analytical method for solving an initial value problem (IVP) for the system of crystal optics with polynomial data and a polynomial inhomogeneous term is suggested. The found solution of the IVP is a polynomial. Theoretical and computational analysis of polynomial solutions and their comparison with non-polynomial solutions corresponding to smooth data are given. The applicability of polynomial solutions to physical processes is discussed. An implementation of this method has been made by symbolic computations in Maple 10.     

An approximate filter for a partially observed piecewise linear system with small observation noise

We propose a finite dimensional approximate filter for a piecewise linear system with small observation noise. The nonlinearity of our system depends only on state components that can be estimated quickly and accurately under a certain ‘detectability hypothesis’. Then we estimate the distance between our approximate filter and the state process to be filtered.     

An Efficient Computational Method for Solving Nonlinear Matrix Equation and Its Application in Queuing Analysis

1IntroductionTheBMAP(BatchMarkovianArrivalProcess)hasbeenstudiedbyD.M.Lu..nt..il1].ResultsforqueueswithSM(Semi-Markov)serviceshavebeenobtainedbyM.F.Neutsl2l.VaCationqueuesaresurveyedbyb.th[a].AmoregeneralqueueBMAP/SM/1whichcom-binedthesetlireeaspectsisstudiedin[4].Discretequeueisexploredin[5].ThebasisofforegoinganalysesisthatthereexistanembeddedMarkovchainatspecificobservinginstants.HerewegiveanewfastalgorithmforthesolutionofabovegeneralqueueswhichpossesssuchanembeddedMarkovchain.…