Congestion control for asynchronous parallel computing on workstation networks

Asynchronous parallel computing can result in high message generation rates, thus triggering network congestion. We characterize the communication requirements of a large class of supercomputing applications falling under the category of fixed-point problems amenable to solution by parallel iterative methods. In particular, we concentrate on asynchronous iterative algorithms whose communication/computation ratio is especially high resulting in degraded effective throughput if communication is not managed properly. Second, we show the effects of network contention and asynchrony on application performance in a local-area network environment and investigate methods of solution. Our approach is based on a congestion control algorithm called ‘warp control’ whose adaptive properties are exploited to yield significant performance enhancements when network contention is high. Although tested in a LAN environment for experimental control purposes, our solution follows the end-to-end paradigm and refrains from exploiting special MAC-layer properties to achieve applicability to general WAN environments. Third, we provide a framework wherein efficient congestion control can be facilitated, encompassing methods acting at the application layer as well as the transport/network layer, with emphasis on application-driven control. We conclude with a discussion of our experimental results and special issues arising in high-bandwidth ATM networks.     

Solving Stable Sylvester Equations via Rational Iterative Schemes

We investigate the numerical solution of stable Sylvester equations via iterative schemes proposed for computing the sign function of a matrix. In particular, we discuss how the rational iterations for the matrix sign function can efficiently be adapted to the special structure implied by the Sylvester equation. For Sylvester equations with factored constant term as those arising in model reduction or image restoration, we derive an algorithm that computes the solution in factored form directly. We also suggest convergence criteria for the resulting iterations and compare the accuracy and performance of the resulting methods with existing Sylvester solvers. The algorithms proposed here are easy to parallelize. We report on the parallelization of those algorithms and demonstrate their high efficiency and scalability using experimental results obtained on a cluster of Intel Pentium Xeon processors     

Using symmetries in the eigenvalue method for polynomial systems

One way of solving polynomial systems of equations is by computing a Gröbner basis, setting up an eigenvalue problem and then computing the eigenvalues numerically. This so-called eigenvalue method is an excellent bridge between symbolic and numeric computation, enabling the solution of larger systems than with purely symbolic methods. We investigate the case that the system of polynomial equations has symmetries. For systems with symmetry, some matrices in the eigenvalue method turn out to have special structure. The exploitation of this special structure is the aim of this paper. For theoretical development we make use of SAGBI bases of invariant rings. Examples from applications illustrate our new approach.     

Analysis of a dynamic lot‐sizing problem with production capacity constraint

We study a capacitated dynamic lot‐sizing problem with special cost structure involving setup cost, freight cost, production cost, and inventory holding cost. We investigate two cases of the problem categorized by whether the maximal production capacity in one period is an integral multiple of the capacity of a container and reveal the special structure of an optimal solution for each case. In the case where the maximal production capacity is an integral multiple of a container's capacity, the T‐period problem is solved using polynomial effort by a network algorithm. For the other case, the problem is transformed into a shortest path problem, and a network‐based algorithm combining dynamic programming is proposed to solve it in polynomial time. Numerical examples are presented to illustrate application of the algorithms to solve the two cases of the problem.     

Special boundary approximation methods for laplace equation problems with boundary singularities— Applications to the motz problem

We investigate the convergence of special boundary approximation methods (BAMs) used for the solution of Laplace problems with a boundary singularity. In these methods, the solution is approximated in terms of the leading terms of the asymptotic solution around the singularity. Since the approximation of the solution satisfies identically the governing equation and the boundary conditions along the segments causing the singularity, only the boundary conditions along the rest of the boundary need to be enforced. Four methods of imposing the essential boundary conditions are considered: the penalty, hybrid, and penalty/hybrid BAMs and the BAM with Lagrange multipliers. A priori error analyses and numerical experiments are carried out for the case of the Motz problem, and comparisons between all methods are made.     

Passivity-preserving splitting methods for rigid body systems

A rigid body model for the dynamics of a marine vessel, used in simulations of offshore pipe-lay operations, gives rise to a set of ordinary differential equations with controls. The system is input–output passive. We propose passivity-preserving splitting methods for the numerical solution of a class of problems which includes this system as a special case. We prove the passivity-preservation property for the splitting methods, and we investigate stability and energy behaviour in numerical experiments. Implementation is discussed in detail for a special case where the splitting gives rise to the subsequent integration of two completely integrable flows. The equations for the attitude are reformulated on \(\mathit{SO}(3)\) using rotation matrices rather than local parameterisations with Euler angles.     

The second-order cone eigenvalue complementarity problem

The eigenvalue complementarity problem (EiCP) differs from the traditional eigenvalue problem in that the primal and dual variables belong to a closed and convex cone K and its dual, respectively, and satisfy a complementarity condition. In this paper we investigate the solution of the second-order cone EiCP (SOCEiCP) where K is the Lorentz cone. We first show that the SOCEiCP reduces to a special Variational Inequality Problem on a compact set defined by K and a normalization constraint. This guarantees that SOCEiCP has at least one solution, and a new enumerative algorithm is introduced for finding a solution to this problem. The method is based on finding a global minimum of an appropriate nonlinear programming (NLP) formulation of the SOCEiCP using a special branching scheme along with a local nonlinear optimizer that computes stationary points on subsets of the feasible region of NLP associated with the nodes generated by the algorithm. A semi-smooth Newton's method is combined with this enumerative algorithm to enhance its numerical performance. Our computational experience illustrates the efficacy of the proposed techniques in practice.     

Characteristics of optimal workload allocation for closed queueing networks

We consider the problem of allocating a given workload among the stations in a multi-server product-form closed queueing network to maximize the throughput. We first investigate properties of the throughput function and prove that it is pseudoconcave for some special cases. Some other characteristics of the optimal workload and its physical interpretation are also provided. We then develop two computational procedures to find the optimum workload allocation under the assumption that the throughput function is pseudoconcave in general. The primary advantage of assuming pseudoconcavity is that, under this assumption, satisfaction of first order necessary conditions is sufficient for optimality. Computational experience with these algorithms provides additional support for the validity of this assumption. Finally, we generalize the solution procedure to accommodate bounds on the workloads at each station.     

Joint optimisation of price,warranty and recovery planning in remanufacturing of used products under linear and non-linear demand,return and cost functions

We investigate joint optimisation of remanufacturing, pricing and warranty decision-making for end-of-life products. A novel mathematical–statistical model is proposed where decisions involve pricing of returned used products (cores), degree of their remanufacturing, selling price and the warranty period for the final remanufactured products. The virtual age reliability improvement approach is chosen to model the upgrading of the cores to higher quality levels. We consider price- and warranty-dependent demand, price- and age-dependent return, and age-dependent remanufacturing cost in the model development. Both linear and non-linear forms of these functions are investigated. First, under some restrictive conditions of upgrade level and age distribution of received cores, special cases of the problem, which can be solved using a recently developed non-linear optimisation solver, are presented. We also implement a particle swarm optimisation algorithm for the solution of the original problem when all the restrictive assumptions are dropped. Finally, numerical experiments and sensitivity analysis are presented to address different aspects of the model and the solution approaches.     

Data exchange: semantics and query answering

Data exchange is the problem of taking data structured under a source schema and creating an instance of a target schema that reflects the source data as accurately as possible. In this paper, we address foundational and algorithmic issues related to the semantics of data exchange and to the query answering problem in the context of data exchange. These issues arise because, given a source instance, there may be many target instances that satisfy the constraints of the data exchange problem.We give an algebraic specification that selects, among all solutions to the data exchange problem, a special class of solutions that we call universal. We show that a universal solution has no more and no less data than required for data exchange and that it represents the entire space of possible solutions. We then identify fairly general, yet practical, conditions that guarantee the existence of a universal solution and yield algorithms to compute a canonical universal solution efficiently. We adopt the notion of the “certain answers” in indefinite databases for the semantics for query answering in data exchange. We investigate the computational complexity of computing the certain answers in this context and also address other algorithmic issues that arise in data exchange. In particular, we study the problem of computing the certain answers of target queries by simply evaluating them on a canonical universal solution, and we explore the boundary of what queries can and cannot be answered this way, in a data exchange setting.     

A note on proper projective collineation in special Bianchi type I space-times

We investigate proper projective collineations in special Bianchi type I space-times using direct integration and algebraic techniques. We have found that when the above space-time admits a proper projective collineation, it turns out to be a special class of Friedmann Robertson—Walker k=0 model.     

Learning Radial Basis Function Networks with the Trust Region Method for Boundary Problems

We consider the solution of boundary value problems of mathematical physics with neural networks of a special form, namely radial basis function networks. This approach does not require one to construct a difference grid and allows to obtain an approximate analytic solution at an arbitrary point of the solution domain. We analyze learning algorithms for such networks. We propose an algorithm for learning neural networks based on the method of trust region. The algorithm allows to significantly reduce the learning time of the network.     

Maximum Singular Value of Matrix and its Economic Interpretation

We prove that the maximum singular value of the matrix and the corresponding singular vectors are the optimal solution for a special quadratic optimization problem. We consider the economic interpretation of the optimal solution for the linear model of production and for the productive Leontief model. We relate the optimal solution to the Frobenius number and vectors and compare the Frobenius numbers and maximum singular values for Leontief inverse matrix in the 15-sectoral balance of Ukraine for 2003–2009.     

Discrete maximum principle for finite element parabolic models in higher dimensions

When we construct continuous and/or discrete mathematical models in order to describe a real-life problem, these models should have various qualitative properties, which typically arise from some basic principles of the modelled phenomena. In this paper we investigate this question for the numerical solution of initial-boundary problems for the parabolic problems in higher dimensions, with the first boundary condition, using the linear finite elements. We give the conditions for the geometry of the mesh and for the choice of the discretization parameters, i.e., for the step sizes under which the discrete qualitative properties hold. For the special regular uniform simplicial mesh we define the conditions for the discretization step-sizes.     

Storing continuous-media data on a compact disc

We consider the problem of storing a given set of files containing continuous-media data on a compact disc by interleaving them so that the required total area is minimal. We show that the problem is NP-hard and consider a number of special cases. The fact that these special cases are related to well-known combinatorial optimization problems has been used in solution techniques developed to handle such cases. We propose an approximation algorithm based on these techniques for the general case.     

Quantum solution to a class of two-party private summation problems

In this paper, we define a class of special two-party private summation (S2PPS) problems and present a common quantum solution to S2PPS problems. Compared to related classical solutions, our solution has advantages of higher security and lower communication complexity, and especially it can ensure the fairness of two parties without the help of a third party. Furthermore, we investigate the practical applications of our proposed S2PPS protocol in many privacy-preserving settings with big data sets, including private similarity decision, anonymous authentication, social networks, secure trade negotiation, secure data mining.     

On the extrapolation for a singularly perturbed boundary value problem

We consider the non-linear boundary value problem with small perturbation parameter ε. We find its numerical solution by using Richardson extrapolation on a special non-uniform discretization mesh. Both, high accuracy and uniformity in ε, are obtained. Numerical examples are provided.     

The effects of input rate and synchrony on a coincidence detector: analytical solution

We derive analytically the solution for the output rate of the ideal coincidence detector. The solution is for an arbitrary number of input spike trains with identical binomial count distributions (which includes Poisson statistics as a special case) and identical arbitrary pairwise cross-correlations, from zero correlation (independent processes) to complete correlation (identical processes).     

Conditional displacement interaction in transversal direction from the quantum Rabi model

We investigate the realization of conditional displacement interaction in transversal direction from the quantum Rabi model by adjusting parameters of external magnetic fields. The special interaction is derived in the system of qubit(s) coupled to a resonator. We explore the implementation of quantum gates and the generation of superposed coherent states based on the transversal conditional displacement interaction, and consolidate the investigations numerically. We also show the special interaction can be realized by using the quantum Rabi model with qubit–qubit coupling.     

Single-machine due-window assignment and scheduling with resource allocation,aging effect,and a deteriorating rate-modifying activity

We consider single-machine scheduling with a common due-window and a deteriorating rate-modifying activity. We assume that the processing time of a job is a function of the amount of a resource allocated to it, its position in the processing sequence, and its aging effect. The objective is to minimize the total cost, which is a function of earliness, tardiness, due-window starting time, due-window size, and resource consumption. We consider two models of the job processing time function and provide polynomial-time solution algorithms for the corresponding problems. We also give a more efficient solution algorithm for a special case of the second problem.