Search

The matrix chain ordering problem is to find the cheapest way to multiply a chain of n matrices, where the matrices are pairwise compatible but of varying dimensions. Here we give several new parallel algorithms including $O(\lg^3 n)$-time and $n/\!\lg n$-processor algorithms for solving the matrix chain ordering problem and for solving an optimal triangulation problem of convex polygons on the common CRCW PRAM model. Next, by using efficient algorithms for computing row minima of totally monotone matrices, this complexity is improved to $O(\lg^2 n)$ time with $n$ processors on the EREW PRAM and to $O(\lg^2 n \lg \lg n)$ time with $n/ \! \lg \lg n$ processors on a common CRCW PRAM\@. A new algorithm for computing the row minima of totally monotone matrices improves our parallel MCOP algorithm to $O(n \lg^{1.5} n)$ work and polylog time on a CREW PRAM\@. Optimal log-time algorithms for computing row minima of totally monotone matrices will improve our algorithm and enable it to have the same work as the sequential algorithm of Hu and Shing [SIAM J. Comput., 11 (1982), pp. 362--373; SIAM J. Comput., 13 (1984), pp. 228--251].

An interior point (IP) method is proposed to solve variational inequality problems for monotone functions and polyhedral sets. The method has the following advantages: 1. Given an initial interior feasible solution with duality gap $\mu_0$, the algorithm requires at most $O[n\log(\mu_0/\ep)]$ iterations to obtain an ep-optimal solution. 2. The rate of convergence of the duality gap is q-quadratic. 3. At each iteration, a long-step improvement is allowed. 4. The algorithm can automatically transfer from a linear mode to a quadratic mode to accelerate the local convergence.

This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy.

We study a biodegradation model for the time evolution of concentrations of con- taminant, nutrient, and bacteria. The bacteria has a natural concentration which will increase when the nutrient reaches the substrate (contaminant). The growth utilizes nutrients and degrades the substrate. Eventually, such a process removes all the substrate and can be described by traveling wave solutions. The model consists of advection-reaction-diusion equations for the substrate and nutrient concentrations and a rate equation (ODE) for the bacteria concentration. We rst show the existence of approximate traveling wave solutions to an elliptically regularized system posed on a nite domain using degree theory and the elliptic maximum principle. To prove that the approximate solutions do not converge to trivial solutions, we construct comparison functions for each component and employ integral identities of the governing equations. This way, we derive a priori estimates of solutions independent of the length of the nite domain and the regularization parameter. The integral identities take advantage of the forms of coupling in the system and help us obtain optimal bounds on the traveling wave speed. We then extend the domain to the innite line limit, remove the regularization, and construct a traveling wave solution for the original set of equations satisfying the prescribed boundary conditions at spatial innities. The contaminant and nutrient proles of the traveling waves are strictly monotone functions, while the biomass prole has a pulse shape.

This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision $\cal S$. The main approach is based on the maintenance of two interlaced spanning trees, one for $\cal S$ and one for the graph-theoretic planar dual of $\cal S$. Queries are answered by using a centroid decomposition of the dual tree to drive searches in the primal tree. These trees are maintained via the link-cut trees structure of Sleator and Tarjan [J. Comput. System Sci., 26 (1983), pp. 362--381], leading to a scheme that achieves vertex insertion/deletion in O(log n) time, insertion/deletion of k-edge monotone chains in O(log n + k) time, and answers queries in O(log2 n) time, with O(n) space, where n is the current size of subdivision $\cal S$. The techniques described also allow for the dual operations expand and contract to be implemented in O(log n) time, leading to an improved method for spatial point location in a 3-dimensional convex subdivision. In addition, the interlaced-tree approach is applied to on-line point location (where one builds $\cal S$ incrementally), improving the query bound to $O(\log n\log\log n)$ time and the update bounds to O(1)amortized time in this case. This appears to be the first on-line method to achieve a polylogarithmic query time and constant update time.

In this paper, we consider a competition model between n species in a chemostat that incorporates both monotone and nonmonotone general response functions and distinct removal rates. We show that only the species with the lowest break-even concentration survives, provided that the variation of distinct removal rates relative to the flow rate of the chemostat can be controlled by either the difference between the two lowest break-even concentrations or by a parameter based on the structure of response functions. LaSalle's extension theorem of the Lyapunov stability theory and fluctuation lemma are the main tools.

We are interested in the rate of convergence in L1 of the approximate solution of a conservation law generated by a monotone finite difference scheme. Kuznetsov has proved that this rate is 1/2 [USSR Comput. Math. Math. Phys., 16 (1976), pp. 105--119 and Topics Numer. Anal. III, in Proc. Roy. Irish Acad. Conf., Dublin, 1976, pp. 183--197], and recently Teng and Zhang have proved this estimate to be sharp for a linear flux [SIAM J. Numer. Anal., 34 (1997), pp. 959--978]. We prove, by constructing appropriate initial data for the Cauchy problem, that Kuznetsov's estimates are sharp for a nonlinear flux as well.

We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally monotone $n \times n$ matrix whose entries represent shortest-path distances between pairs of vertices in a simple polygon. We apply this result to derive improved algorithms for several well-known problems in computational geometry. Most prominently, we obtain linear-time algorithms for computing the geodesic diameter, all farthest neighbors, and external farthest neighbors of a simple polygon, improving the previous best result by a factor of O(log n) in each case.

We consider a mixed problem composed in part of finding a zero of a maximal monotone operator and in part of solving a monotone variational inequality problem. We propose a solution method for this problem that alternates between a proximal step (for the maximal monotone operator part) and a projection-type step (for the monotone variational inequality part) and analyze its convergence and rate of convergence. This method extends a decomposition method of Chen and Teboulle [Math. Programming, 64 (1994), pp. 81--101] for convex programming and yields, as a by-product, new decomposition methods.

Consider the problem of identifying $\min T(f)$ and $\max F(f)$ of a positive (i.e., monotone) Boolean function $f$ by using membership queries only, where $\min T(f)\,(\max F(f))$ denotes the set of minimal true vectors (maximal false vectors) of $f$. It is known that an incrementally polynomial algorithm exists if and only if there is a polynomial time algorithm to check the existence of an unknown vector $u$ for given sets $MT \subseteq \min T(f)$ and $MF \subseteq \max F(f)$; that is, $u \in \{0,1\}^n \setminus (\{v | v \geq w {\rm for some } w \in MT \} \cup \{v | v \leq w {\rm for some } w \in MF \})$. This paper introduces a measure for the difficulty to find an unknown vector, which is called the maximum latency. If the maximum latency is constant, then an unknown vector can be found in polynomial time and there is an incrementally polynomial algorithm for identification. Several subclasses of positive functions are shown to have constant maximum latency, e.g., $2$-monotonic positive functions, $\Delta$-partial positive threshold functions, and matroid functions, while the class of general positive functions has $\lfloor n/4 \rfloor +1$ maximum latency and the class of positive $k$-DNF functions has $\Omega (\sqrt{n})$ maximum latency.

It is demonstrated that monotonicity is a sufficient condition to ensure that no new nonphysical local maxima and minima can be produced in the discrete nonlinear unsaturated flow equation. Monotonicity conditions are derived for various types of weighting for the mobility term. The basic discretization is of finite element type, but the results can be extended to finite volume discretizations. Central weightings are only conditionally monotone, while upstream weightings are unconditionally monotone. Sample computations are given for highly heterogeneous problems.

This paper studies the global asymptotic behavior of an exploitative competition model between n species in a chemostat. The model incorporates discrete time delays to describe the delay in the conversion of nutrient consumed to viable biomass and hence includes delays simultaneously in variables of nutrient and species concentrations. In the case where only two species are engaged in competition, it is shown that competitive exclusion holds for any monotone growth response functions. Sufficient conditions are also obtained for the model to exhibit competitive exclusion in the n-species case. In regard to the delay effects on the qualitative outcome of competition, it is demonstrated that when the delays are relatively small, the predictions of the model are identical with the predictions given by corresponding models without time delays. However, including large delays in the model may alter the predicted outcome of competition. The techniques used also work when different removal rates are permitted, an...

We derive optimal error bounds for the viscosity method and monotone difference schemes to an initial-value problem of scalar conservation laws with initial data being a finite number of piecewise constants, subject to the initial discontinuities satisfying the entropy conditions. It is known that the entropy solution of the problem is piecewise constant with a finite number of interacting shocks satisfying the entropy conditions. A rigorous analysis shows that both the viscosity method and monotone schemes to approach the initial-value problem have uniform $L^1$-error bounds of $O(\epsilon)$ and $O(\Delta x)$ for the time $+\infty>t>0$, respectively, where $\epsilon$ and $\Delta x $ are their corresponding viscosity coefficient and discrete mesh length. The results are improvements over the half-order rates of $L^1$-convergence. Numerical experiments for the Lax--Friedrichs scheme are presented and numerical results justify the theoretical analysis.

We propose an infeasible path-following method for solving the monotone complementarity problem. This method maintains positivity of the iterates and uses two Newton steps per iteration---one with a centering term for global convergence and one without the centering term for local superlinear convergence. We show that every cluster point of the iterates is a solution, and if the underlying function is affine or is sufficiently smooth and a uniform nondegenerate function on $\Re_{++}^n$, then the convergence is globally Q-linear. Moreover, if every solution is strongly nondegenerate, the method has local quadratic convergence. The iterates are guaranteed to be bounded when either a Slater-type feasible solution exists or when the underlying function is an R0-function.

A large-step infeasible-interior-point method is proposed for solving $P_*(\k)$-matrix linear complementarity problems. It is new even for monotone LCP. The algorithm generates points in a large neighborhood of an infeasible central path. Each iteration requires only one matrix factorization. If the problem is solvable, then the algorithm converges from arbitrary positive starting points. The computational complexity of the algorithm depends on the quality of the starting point. If a well-centered starting point is feasible or close to being feasible, then it has $O((1+\k)\sqrt{n}\ln(\eps_0/\eps))$-iteration complexity. With appropriate initialization, a modified version of the algorithm terminates in $O((1+\k)^2n\ln(\eps_0/\eps))$ steps either by finding a solution or by determining that the problem is not solvable. High-order local convergence is proved for problems having a strictly complementary solution. We note that while the properties of the algorithm (e.g., computational complexity) depend on $\k$, the algorithm itself does not.

A predictor--corrector algorithm is proposed for solving monotone linear complementarity problems (LCPs) from infeasible starting points. The algorithm terminates in $O(nL)$ steps either by finding a solution or by determining that the problem has no solution of norm less than a given number. The complexity of the algorithm depends on the quality of the starting point. If the problem is solvable and if a certain measure of feasibility at the starting point is small enough, then the algorithm finds a solution in $O(\sqrt{n}L)$ iterations. The algorithm requires two matrix factorizations and two backsolves per iteration. If the problem has a strictly complementary solution, then the algorithm is quadratically convergent, and, therefore, its asymptotic efficiency index is $\sqrt{2}$.

In this paper we are concerned with a finite element method for multidimensional scalar conservation laws: we describe a general formulation of the Euler characteristic Galerkin (ECG) scheme, motivated by key features of the one-dimensional ECG scheme. The method is defined by projecting the transport collapse operator onto a finite element space spanned by piecewise constant basis functions. The ECG scheme is {\em TVD, monotone, maximum norm nonincreasing and unconditionally stable in the $L^{1}$-norm}. To the best of our knowledge, there is no other method which has all these properties. However, with piecewise constant basis functions, the ECG scheme is at most first-order accurate; greater accuracy can be obtained through a recovery procedure. Unlike conventional dimension-by-dimension methods, multidimensional ECG schemes contain important terms which describe corner effects. Nonuniform meshes and large time steps can be used with this class of schemes.

We derive sufficient conditions on the Bezier net of a Bernstein--Bezier polynomial defined on a triangle in the plane to insure that the corresponding surface is monotone. We then apply these conditions to construct a new algorithm for fitting a monotone surface to gridded data. The method uses C1 cubic splines defined on the triangulation obtained by drawing both diagonals of each subrectangle. In addition, we present an algorithm for the monotone scattered data interpolation problem which is based on a method for creating gridded data from the scattered data. Numerical results for several test examples are presented.

Moore and Shannon have shown that relays with arbitrarily high reliability can be built from relays with arbitrarily poor reliability. Valiant used similar methods to construct monotone read-once formulas of size $O(n^{\alpha+2})$ (where $\alpha=\log_{\sqrt{5}-1}2\simeq 3.27$) that amplify $(\psi-\frac{1}{n},\psi+\frac{1}{n})$ (where $\psi=(\sqrt{5}-1)/2\simeq0.62$) to $(2^{-n},1-2^{-n})$ and deduced as a consequence the existence of monotone formulas of the same size that compute the majority of $n$ bits. Boppana has shown that any monotone read-once formula that amplifies $(p-\frac{1}{n},p+\frac{1}{n})$ to $(\frac{1}{4},\frac{3}{4})$ (where $0We extend Boppana's results in two ways. We first show that his two lower bounds hold for general read-once formulas, not necessarily monotone, that may even include exclusive-or gates. We are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies $(p-\frac{1}{n},p+\frac{1}{n})$ to $(2^{-n},1-2^{-n})$ has size $\Omega(n^{\alpha+2})$. This result does not follow from Boppana's arguments, and it shows that the amount of amplification achieved by Valiant is the maximal achievable using read-once formulas. In a companion paper we construct monotone read-once contact networks of size $O(n^{2.99})$ that amplify $(\frac{1}{2}-\frac{1}{n},\frac{1}{2}+\frac{1}{n})$ to $(\frac{1}{4},\frac{3}{4})$. This shows that Boppana's lower bound for the first amplification stage does not apply to contact networks, even if they are required to be both monotone and read-once.

The SDLCP (semidefinite linear complementarity problem) in symmetric matrices introduced in this paper provides a unified mathematical model for various problems arising from systems and control theory and combinatorial optimization. It is defined as the problem of finding a pair $(\X,\Y)$ of $n \times n$ symmetric positive semidefinite matrices which lies in a given $n(n+1)/2$ dimensional affine subspace $\FC$ of $\SC^2$ and satisfies the complementarity condition $\X \bullet \Y = 0$, where $\SC$ denotes the $n(n+1)/2$-dimensional linear space of symmetric matrices and $\X \bullet \Y$ the inner product of $\X$ and $\Y$. The problem enjoys a close analogy with the LCP in the Euclidean space. In particular, the central trajectory leading to a solution of the problem exists under the nonemptiness of the interior of the feasible region and a monotonicity assumption on the affine subspace $\FC$. The aim of this paper is to establish a theoretical basis of interior-point methods with the use of Newton directions toward the central trajectory for the monotone SDLCP.

We consider the problem of identifying an unknown Boolean function $f$ by asking an oracle the functional values $f(a)$ for a selected set of test vectors $a \in \{0,1\}^{n}$. Furthermore, we assume that $f$ is a positive (or monotone) function of $n$ variables. It is not yet known whether or not the whole task of generating test vectors and checking if the identification is completed can be carried out in polynomial time in $n$ and $m$, where $m=|\min T(f)| + |\max F(f)|$ and $\min T(f)$ (respectively, $\max F(f))$ denotes the set of minimal true (respectively, maximal false) vectors of $f$. To partially answer this question, we propose here two polynomial-time algorithms that, given an unknown positive function $f$ of $n$ variables, decide whether or not $f$ is 2-monotonic and, if $f$ is 2-monotonic, output both sets $\min T(f)$ and $\max F(f)$. The first algorithm uses $O(nm^{2} + n^{2}m)$ time and $O(nm)$ queries, while the second one uses $O(n^{3}m)$ time and $O(n^{3}m)$ queries.

We consider a sequence of independent random variables whose probability distributions differ only by a one-dimensional parameter of the density and investigate the maximum likelihood estimate of a monotone trend of the parameter. Using the decomposability property of the estimate, we obtain new results on the distribution of the number of steps of this estimate in the case of discrete distributions. These results are given in a convenient form in terms of formal power series.

We prove that all of Karp's 21 original $NP$-complete problems have a version that is hard to approximate. These versions are obtained from the original problems by adding essentially the same simple constraint. We further show that these problems are absurdly hard to approximate. In fact, no polynomial-time algorithm can even approximate $\log^{(k)}$ of the magnitude of these problems to within any constant factor, where $\logk$ denotes the logarithm iterated $k$ times, unless $NP$ is recognized by slightly superpolynomial randomized machines. We use the same technique to improve the constant $\epsilon$ such that MAX CLIQUE is hard to approximate to within a factor of $n^\epsilon$. Finally, we show that it is even harder to approximate two counting problems: counting the number of satisfying assignments to a monotone 2SAT formula and computing the permanent of $-1$, $0$, $1$ matrices.

This paper is concerned with the asymptotic behavior as $\epsilon \to 0$ of solutions of the reaction-diffusion equation $u_t = \epsilon ^2 u_{xx} - (u + a)(u^2 - 1)$ defined in $( - 1,1)$ with Neumann boundary conditions. For $a = 0$, this equation has a monotone equilibrium solution $u^\epsilon $ with the property that $u^\epsilon (x) \to - 1$ (resp. $ + 1$) on $[ { - 1,0} )$ (resp. $( {0,1} ]$) as $\epsilon \to 0$; that is, the solution has a sharp transition layer if $a = 0$. Also, it is known that $u^\epsilon $ has a one-dimensional unstable manifold $\mathcal{M}(u^\epsilon )$. Solutions near $\mathcal{M}(u^\epsilon )$ decrease exponentially to $\mathcal{M}(u^\epsilon )$ and move with a speed $O(e^{{{ - c} / \epsilon }} )$ along $\mathcal{M}(u^\epsilon )$.This paper considers the case where a is small and fixed. For each fixed $\epsilon $, $a \ne 0$, small, there is an equilibrium solution $u^{\epsilon a} $ with unstable manifold of dimension one, but $u^{\epsilon a} $ approaches either the function ...

Karmarkar's partial updating scheme is applied to a polynomial superlinearly convergent algorithm for the monotone linear complementarity problem (LCP). This modification reduces the bound on the number of arithmetic operations required to achieve $\epsilon $-optimality by a factor of $\sqrt{n}$. The complementarity gap sequence generated by the resulting algorithm converges $q$-quadratically to zero if the LCP is nondegenerate and has a strictly complementary optimal solution. In general, the convergence rate is $q$-superlinear if the iterates are assumed to converge to a strictly complementary optimal solution.

In this paper we derive new necessary and sufficient conditions for an affine map to be quasimonotone on a convex set.

We propose new methods for solving the variational inequality problem where the underlying function $F$ is monotone. These methods may be viewed as projection-type methods in which the projection direction is modified by a strongly monotone mapping of the form $I - \alpha F$ or, if $F$ is affine with underlying matrix $M$, of the form $I+ \alpha M^T$, with $\alpha \in (0,\infty)$. We show that these methods are globally convergent, and if in addition a certain error bound based on the natural residual holds locally, the convergence is linear. Computational experience with the new methods is also reported.

A class of parabolic systems for which the maximum principle is valid is investigated. When two stable rest points can be connected by a traveling front, any solution of the Cauchy problem which initially has these two rest points as spatial limits will become monotone in finite time on every compact interval and converge to a traveling front. As an application, convergence to stacked waves is discussed.

This paper stresses the role of co-coercivity and related notions in the convergence of iterative schemes for solving monotone but not necessarily strongly or even strictly monotone variational inequalities. The analysis will be conducted within the conceptual framework of the ``auxiliary problem principle.''

Boundary value problems for singularly perturbed semilinear elliptic equations are considered. Special piecewise-uniform meshes are constructed which yield accurate numerical solutions irrespective of the value of the small parameter. Numerical methods composed of standard monotone finite difference operators and these piecewise-uniform meshes are shown theoretically to be uniformly (with respect to the singular perturbation parameter) convergent. Numerical results are also presented, which indicate that in practice the method is first-order accurate.

A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR gates. Goldschlager, Dymond, Cook, and others have developed $NC^2$ algorithms to evaluate a special layered form of a PMC. These algorithms require a large number of processors ($\Omega(n^6)$, where $n$ is the size of the input circuit). Yang and, more recently, Delcher and Kosaraju have given NC algorithms for the general planar monotone circuit value problem. These algorithms use at least as many processors as the algorithms for the layered case. This paper gives an efficient parallel algorithm that evaluates a general PMC of size $n$ in polylog time using only a linear number of processors on an exclusive read exclusive write parameter random-access machine (EREW PRAM). This parallel algorithm is the best possible to within a polylog factor and is a substantial improvement over the earlier algorithms for the problem. The algorithm uses several novel techniques to perform the evaluation, including the use of the dual of the plane embedding of the circuit to determine the propagation of values within the circuit.

In this paper we examine the continuous piecewise linear finite element approximation of the following system: given ${\bf f} \equiv (f_j )$ and ${\bf g} \equiv (g_j )$, find ${\bf u} \equiv (u_j )$($(j = 1 \to r$ with $r = 1$ or 2) such that $ - \nabla \cdot (K(z,\nabla {\bf u}(z))\nabla {\bf u}(z)) = {\bf f}(z),\quad z \in \Omega \subset R^2 ,\quad {\bf u} |_{\partial \Omega } = {\bf g} |_{\partial \Omega } ,$ where $(\nabla {\bf u}) \equiv {{\partial u_j } / {\partial z_i }}\, 1 \leq i \leq 2,\, 1 \leq j \leq r$ and K is a given matrix on $\Omega \times R^{2 \times r} $. We characterize a class of matrices K for which we prove error bounds for this discretization. For sufficiently regular solutions ${\bf u}$, achievable at least for some model problems, our bounds improve on existing results in the literature. It is shown that for a notable subclass of K, for which only suboptimal error bounds have been previously derived, the piecewise linear finite element approximation of this problem will converge ...

We present an infeasible-interior-point algorithm for monotone linear complementarity problems in which the search directions are affine scaling directions and the step lengths are obtained from simple formulae that ensure both global and superlinear convergence. By choosing the value of a parameter in appropriate ways, polynomial complexity and convergence with Q-order up to (but not including) two can be achieved. The only assumption made to obtain the superlinear convergence is the existence of a solution satisfying strict complementarily.

Exact error analyses for two implicit approximation schemes to the Cauchy problem ${{du(t)} / {dt}} + \mathcal {A}(u(t)) \mathrel\backepsilon 0,u(0) = u_0 \in D(\mathcal {A})$ are presented. The operator $\mathcal {A}$ is required to be maximal monotone on a Hilbert space $\mathcal {H}$. The approximations considered are $u_h (kh) = (I + h\mathcal {A})^{ - k} u_0 $ and solutions $u_\lambda $ to the approximating problems ${{du_\lambda (t)} / {dt}} + \mathcal {A}_\lambda (u_\lambda ) = 0,u_\lambda (0) = u_0 $, where $A_\lambda $ is the Yosida approximation of $\mathcal A$ The special case of A being a subgradient is considered, and tight estimates of the convergence of both $u_h $ and $\mathcal {A}_h (u_h )$ (or $u_h $, and $A_h (u_h )$) are given. The new results in this case are the linear rates of convergence of $u_h $ in $L^\infty (0,\infty ;\mathcal {H})$ and in the “energy norm,” and the sublinear rate of convergence of .$A_h (u_h )$ in $L^2 (0,\infty ;\mathcal {H})$. Applications to both linear and ...

The importance of eliminating randomness in insuring that renewable systems satisfy all necessary conditions is well known. In this paper, groups of standby renewable systems with a repair facility (RF) which form a symmetric “complex-RF” are considered. Return rules are obtained which maximize (in probability) the time up to the first failure of the complex over the class of rules of returns of the element to the complex which depend on the state of the complex and the failure times of the elements renewed at the RF. If the renewal is carried out by a sequential and monotone RF, then in this subclass of return rules, the maximum of the mean number of renewed elements is obtained for any finite time interval. In the case of the ordinary flow of element failures and ergodicity of the random process indicating the number of working elements in the complex, it is proved that the subclass of return rules obtained maximizes the steady-state mean of the working systems.

Lattice Boltzmann methods are numerical schemes derived as a kinetic approximation of an underlying lattice gas. A numerical convergence theory for nonlinear convective–diffusive lattice Boltzmann methods is established. Convergence, consistency, and stability are defined through truncated Hilbert expansions. In this setting it is shown that consistency and stability imply convergence. Monotone lattice Boltzmann methods are defined and shown to be stable, and hence convergent when consistent. Examples of diffusive and convective–diffusive lattice Boltzmann methods that are both consistent and monotone are presented.

In this paper we discuss the necessary and sufficient conditions for the existence of smooth monotone shock profiles for viscoelastic materials with memory. We also discuss the uniqueness. We consider both convex and nonconvex constitutive relations. In the case of nonconvex constitutive relations, we include a degenerate case where the speed of the shock profile is equal to the speed of the equilibrium characteristics at one of the end states. This was not discussed in previous literature.

Goldschlager first established that a special case of the monotone planar circuit problem can be solved by a Turing machine in $O(\log^2 n)$ space. Subsequently, Dymond and Cook refined the argument and proved that the same class can be evaluated in $O(\log^2 n)$ time with a polynomial number of processors. In this paper, we prove that the general monotone planar circuit value problem can be evaluated in $O(\log^4 n)$ time with a polynomial number of processors, settling an open problem posed by Goldschlager and Parberry.

We consider an extension of the horizontal linear complementarity problem, which we call the extended linear complementarity problem (XLCP). With the aid of a natural bilinear program, we establish various properties of this extended complementarity problem; these include the convexity of the bilinear objective function under a monotonicity assumption, the polyhedrality of the solution set of a monotone XLCP, and an error bound result for a nondegenerate XLCP. We also present a finite, sequential linear programming algorithm for solving the nonmonotone XLCP.

In this paper, travelling wave solutions for certain competition-diffusion equations are considered, and the monotone dependence of their propagation speed on parameters which appear in the equation are established. To do this, the maximum principle and the bifurcation theory for heteroclinic orbits are employed.

The existence and stability of stable rotating solutions (spiral waves) in a discrete system of coupled phase models is proven. Monotone methods are used to obtain existence and qualitative features of the solutions. An application of Fenichel's results for singular perturbation implies the existence for a one variable model for excitability. Numerical comparisons with the phase model and a realistic membrane model are made. A numerically computed Hopf bifurcation shows the existence of the “wobbling core” observed in spatially continuous models.

The authors present an $O(mn^2 \log m)$ algorithm for solving feasibility in linear programs with up to two variables per inequality which is derived directly from the Fourier--Motzkin elimination method. (The number of variables and inequalities are denoted by $n$ and $m$, respectively.) The running time of the algorithm dominates that of the best known algorithm for the problem, and is far simpler. Integer programming on monotone inequalities, i.e., inequalities where the coefficients are of opposite sign, is then considered. This problem includes as a special case the simultaneous approximation of a rational vector with specified accuracy, which is known to be NP-complete. However, it is shown that both a feasible solution and an optimal solution with respect to an arbitrary objective function can be computed in pseudo-polynomial time.

This paper addresses a prediction problem occurring frequently in practice. The problem consists in predicting the value of a function on the basis of discrete observational data that are incomplete in two senses. Only certain arguments of the function are observed, and the function value is observed only for certain combinations of values of these arguments. The problem is considered under a monotonicity condition that is natural in many applications. Applications to tax auditing, medicine, and real estate valuation are discussed. In particular, a special class of problems is identified for which the best monotone prediction can be found in polynomial time.

Monotonicity of primal and dual objective values in the framework of primal-dual interior-point methods is studied. The primal-dual affine-scaling algorithm is monotone in both objectives. A condition is derived under which a primal-dual interior-point algorithm with a centering component is monotone. Primal-dual algorithms that are monotone in both primal and dual objective values are then proposed, and polynomial time bounds are achieved. Some arguments are also provided that show that several existing primal-dual algorithms use parameters close to one that almost always improves both objectives.

This research concerns the conditions that ensure the quasimonotonicity of the separable operator \[ F ( x_1 ,x_2 , \ldots , x_p ) = ( F_1 ( x_1 ), F_2 ( x_2 ), \ldots , F_p ( x_p ) ) \], where for $i = 1, 2, \ldots , p, C_i $ is an open convex subset of $\mathbb{R}^{n_i} $ and $F_i :C_i \to \mathbb{R}^{n_i} $ is a continuous nonnull operator. It is shown, in particular, that all $F_i $, except perhaps one, are monotone. The conditions are given in terms of the monotonicity indices of the operators $F_i $, a concept introduced in this paper.

The present paper shows that one cannot expect the Jackson type estimates to hold for higher degree moduli of smoothness in monotone (or comonotone) spline approximation. This result gives a complete negative answer to a question raised by DeVore for $m \geq 2$ in monotone spline approximation. It also indicates that an equivalence between monotone polynomial approximation and monotone spline approximation claimed by Wang is wrong in one direction. There are corresponding results in $L^p $ spaces.

Simple necessary and sufficient conditions that a quartic polynomial f(z) be non-negative for z greater than or equal to 0 or a is less than or equal to z and z is less than or equal to b are derived, and illustrated geometrically. The geometry provides considerable insight and suggests various approximations and computational simplifications. The theory is applied to monotone quintic spline interpolations, giving necessary and sufficient conditions and an algorithm for monotone Hermite quintic interpolation.

This paper proves the convergence of a general class of monotone finite volume methods for numerical schemes of scalar conservation laws in two dimensions on unstructured meshes. There are convergence results for fractional step methods on cartesian grids and for finite element algorithms on unstructured grids. Even for finite volume methods there are some recent results concerning the Lax–Friedrichs and the Godunov finite volume method. The proof in this paper considers a general class including the Lax–Friedrichs and the Engquist–Osher finite volume schemes, and uses a completely different idea than in previous papers to control the entropy dissipation.

This paper investigates the boundedness and stability of solutions to the affine variational inequality problem. The concept of a solution ray to a variational inequality defined by an affine, mapping and on a closed convex set is introduced and characterized; the connection of such a ray with the boundedness of the solution set of the given problem is explained. In the case of the monotone affine variational inequality, a complete description of the solution set is obtained which leads to a simplified characterization of the boundedness of this set as well as to a new error bound result for approximate solutions to such a variational problem. The boundedness results are then combined with certain degree- theoretic arguments to establish the stability of the solution set of an affine variational inequality problem.

An iterative method for solving a linear system $Ax = b$ produces iterates $\{ x_k \} $ with associated residual norms that, in general, need not decrease “smoothly” to zero. “Residual smoothing” techniques are considered that generate a second sequence $\{ y_k \} $ via a simple relation $y_k = (1 - \eta _k )y_{k - 1} + \eta _k x_k $. The authors first review and comment on a technique of this form introduced by Schonauer and Weiss that results in $\{ y_k \} $ with monotone decreasing residual norms; this is referred to as minimal residual smoothing Certain relationships between the residuals and residual norms of the biconjugate gradient (BCG) and quasi-minimal residual (QMR) methods are then noted, from which it follows that QMR can be obtained from BCG by a technique of this form; this technique is extended to generally applicable quasi-minimal residual smoothing. The practical performance of these techniques is illustrated in a number of numerical experiments.