An algorithmic approach for a special class of Markov chains

In this paper, we develop an algorithmic method for the evaluation of the steady state probability vector of a special class of finite state Markov chains. For the class of Markov chains considered here, it is assumed that the matrix associated with the set of linear equations for the steady state probabilities possess a special structure, such that it can be rearranged and decomposed as a sum of two matrices, one lower triangular with nonzero diagonal elements, and the other an upper triangular matrix with only very few nonzero columns. Almost all Markov chain models of queueing systems with finite source and/or finite capacity and first-come-first-served or head of the line nonpreemptive priority service discipline belongs to this special class.     

Perturbed steepest-descent technique in multiextremal problems

The steepest-descent technique dealing with the perturbed values of the objective function and its gradients and with nonexact line searches is considered. Attention is given to the case where the perturbations do not decrease on the algorithm trajectories; the aim is to investigate how perturbations at every iteration of the algorithm perturb its original attractor set.Based on the Liapunov direct method for attraction analysis of discrete-time processes, a sharp estimation of the attractor set generated by a perturbed steepest-descent technique with respect to the perturbation magnitudes is obtained. Some global optimization properties of finite-difference analogues of the gradient method are discovered. These properties are not inherent in methods which use exact gradients.The author is grateful to the referees for many useful suggestions.     

On parallel asynchronous high-order solutions of parabolic PDEs

In achieving significant speed-up on parallel machines, a major obstacle is the overhead associated with synchronizing the concurrent processes. This paper presents high-orderparallel asynchronous schemes, which are schemes that are specifically designed to minimize the associated synchronization overhead of a parallel machine in solving parabolic PDEs. They are asynchronous in the sense that each processor is allowed to advance at its own speed. Thus, these schemes are suitable for single (or multi) user shared memory or (message passing) MIMD multiprocessors. Our approach is demonstrated for the solution of the multidimensional heat equation, of which we present a spatial second-order Parametric Asynchronous Finite-Difference (PAFD) scheme. The well-known synchronous schemes are obtained as its special cases. This is a generalization and expansion of the results in [5] and [7]. The consistency, stability and convergence of this scheme are investigated in detail. Numerical tests show that although PAFD provides the desired order of accuracy, its efficiency is inadequate when performed on each grid point.In an alternative approach that uses domain decomposition, the problem domain is divided among the processors. Each processor computes its subdomain mostly independently, while the PAFD scheme provides the solutions at the subdomains' boundaries. We use high-order finite-difference implicit scheme within each subdomain and determine the values at subdomains' boundaries by the PAFD scheme. Moreover, in order to allow larger time-step, we use remote neighbors' values rather than those of the immediate neighbors. Numerical tests show that this approach provides high efficiency and in the case which uses remote neighbors' values an almost linear speedup is achieved. Schemes similar to the PAFD can be developed for other types of equations [3].This research was supported by the fund for promotion of research at the Technion.     

A composition law for Runge-Kutta methods applied to index-2 differential-algebraic equations

This paper presents a new composition law for Runge-Kutta methods when applied to index-2 differential-algebraic systems. Applications of this result to the study of the order of composite methods and of symmetric methods are given.     

Optimal filter design subject to output sidelobe constraints: Computational algorithm and numerical results

An algorithm is presented for the design of optimal detection filters in radar and communications systems, subject to inequality constraints on the maximum output sidelobe levels. This problem was reduced in an earlier paper (Ref. 1) to an unconstrained one in the dual space of regular Borel measures, with a nondifferentiable cost functional. Here, the dual problem is solved via steepest descent, using the directional Gateaux differential. The algorithm is shown to be convergent, and numerical results are presented.This research was supported by the Australian Research Grants Committee.     

Extensions of Lemke's algorithm for the linear complementarity problem

Lemke's algorithm for the linear complementarity problem fails when a desired pivot is not blocked. A projective transformation overcomes this difficulty. The transformation is performed computationally by adjoining a new row to a schema of the problem and pivoting on the element in this row and the unit constant column. Two new algorithms result; some conditions for their success are discussed.This research was partially supported by National Science Foundation, Grant GK-42092.     

Quantum field methods in the theory of diffusion-controlled reactions

The diagrammatic perturbation technique for the kinetic theory of classical reacting systems with diffusion is developed. It is further applied to investigation of recombination-type reactions in media of one, two, and three dimensions. The effective rates of this reaction are calculated, covering the whole range from the slow to the fast (diffusion-controlled) regimes.     

Properties of updating methods for the multipliers in augmented Lagrangians

The convergence properties of different updating methods for the multipliers in augmented Lagrangians are considered. It is assumed that the updating of the multipliers takes place after each line search of a quasi-Newton method. Two of the updating methods are shown to be linearly convergent locally, while a third method has superlinear convergence locally. Modifications of the algorithms to ensure global convergence are considered. The results of a computational comparison with other methods are presented.This work was supported by the Swedish Institute of Applied Mathematics.