Applied Mathematics Commons^™

Graphs, Maneuvers, And Turnpikes, Arthur T. Benjamin

All HMC Faculty Publications and Research

We address the problem of moving a collection of objects from one subset of Z^m to another at minimum cost. We show that underfairly natural rules for movement assumptions, if the origin and destination are far enough apart, then a near optimal solution with special structure exists: Our trajectory from the originto the destination accrues almost all of its cost repeatingat most m different patterns of movement. Directions for related research are identified.

Nonnegative Solutions For A Class Of Radially Symmetric Nonpositone Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

We consider the existence of radially symmetric non-negative solutions for the boundary value problem

\begin{displaymath}\begin{array}{*{20}{c}} { - \Delta u(x) = \lambda f(u(x))\qua... ...\\ {u(x) = 0\quad \left\Vert x \right\Vert = 1} \\ \end{array} \end{displaymath}

where $ \lambda > 0,f(0) < 0$ (non-positone), $ f' \geq 0$ and $ f$ is superlinear. We establish existence of non-negative solutions for $ \lambda $ small which extends some work of our previous paper on non-positone problems, where we considered the case $ N = 1$. Our work also proves a recent conjecture by Joel Smoller and Arthur Wasserman.

Viscous Cross-Waves: An Analytical Treatment, Andrew J. Bernoff, L. P. Kwok, Seth Lichter

All HMC Faculty Publications and Research

Viscous effects on the excitation of cross‐waves in a semi‐infinite box of finite depth and width are considered. A formalism using matched asymptotic expansions and an improved method of computing the solvability condition is used to derive the relative contributions of the free‐surface, sidewall, bottom, and wavemaker viscous boundary layers. This analysis yields an expression for the damping coefficient previously incorporated on heuristic grounds. In addition, three new contributions are found: a viscous detuning of the resonant frequency, a slow spatial variation in the coupling to the progressive wave, and a viscous correction to the wavemaker boundary condition. The wavemaker …

Turnpike Structures For Optimal Maneuvers, Arthur T. Benjamin

All HMC Faculty Publications and Research

This dissertation is concerned with problems of optimally maneuvering a collection of objects ("pieces") from one location to another, subject to various restrictions on the allowable movements. We illustrate and prove that when the "distance" from the origin to the destination is large, and the movement rules and environment satisfy certain "homogeneity" properties, there exist near-optimal trajectories with very special (turnpike) structure.

These results are obtained by representing the problem through a configuration graph. Here, we have a node for each configuration and an arc for every "different" legal move. Each arc is endowed with a scalar weight …

Nonnegative Solutions To A Semilinear Dirichlet Problem In A Ball Are Positive And Radially Symmetric, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

We prove that nonnegative solutions to a semilinear Dirichlet problem in a ball are positive, and hence radially symmetric. In particular, this answers a question in [3] where positive solutions were proven to be radially symmetric. In section 4 we provide a sufficient condition on the geometry of the domain which ensures that nonnegative solutions are positive in the interior.

Multiple Solutions For A Dirichlet Problem With Jumping Nonlinearities Ii, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

No abstract provided for this article.

Stability Of Steady Cross-Waves: Theory And Experiment, Seth Lichter, Andrew J. Bernoff

All HMC Faculty Publications and Research

A bifurcation analysis is performed in the neighborhood of neutral stability for cross waves as a function of forcing, detuning, and viscous damping. A transition is seen from a subcritical to a supercritical bifurcation at a critical value of the detuning. The predicted hysteretic behavior is observed experimentally. A similarity scaling in the inviscid limit is also predicted. The experimentally observed bifurcation curves agree with this scaling.

Nonnegative Solutions For A Class Of Nonpositone Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

In the recent past many results have been established on non-negative solutions to boundary value problems of the form

-u''(x) = λf(u(x)); 0 < x < 1,

u(0) = 0 = u(1)

where λ>0, f(0)>0 (positone problems). In this paper we consider the impact on the non-negative solutions when f(0)<0. We find that we need f(u) to be convex to guarantee uniqueness of positive solutions, and f(u) to be appropriately concave for multiple positive solutions. This is in contrast to the case of positone problems, where the roles of convexity and concavity were interchanged to obtain similar results. We further establish the existence of non-negative solutions with interior zeros, which did not exist in positone problems.

Reliable Computation By Formulas In The Presence Of Noise, Nicholas Pippenger

All HMC Faculty Publications and Research

It is shown that if formulas are used to compute Boolean functions in the presence of randomly occurring failures then: (1) there is a limit strictly less than 1/2 to the failure probability per gate that can be tolerated, and (2) formulas that tolerate failures must be deeper (and, therefore, compute more slowly) than those that do not. The heart of the proof is an information-theoretic argument that deals with computation and errors in very general terms. The strength of this argument is that it applies with equal ease no matter what types of gate are available. Its weaknesses is …

Infinitely Many Radially Symmetric Solutions To A Superlinear Dirichlet Problem In A Ball, Alfonso Castro, Alexandra Kurepa

All HMC Faculty Publications and Research

In this paper we show that a radially symmetric superlinear Dirichlet problem in a ball has infinitely many solutions. This result is obtained even in cases of rapidly growing nonlinearities, that is, when the growth of the nonlinearity surpasses the critical exponent of the Sobolev embedding theorem. Our methods rely on the energy analysis and the phase-plane angle analysis of the solutions for the associated singular ordinary differential equation.

Wavenumber Selection Of Convection Rolls In A Box, Wayne Arter, Andrew J. Bernoff, A. C. Newell

All HMC Faculty Publications and Research

The dynamics of two‐dimensional Rayleigh–Bénard convection rolls are studied in a finite layer with no‐slip, fixed temperature upper and lower boundaries and no‐slip insulating side walls. The dominant mechanism controlling the number of rolls seen in the layer is an instability concentrated near the side walls. This mechanism significantly narrows the band of stable wavenumbers although it can take a time comparable to the long (horizontal) diffusion time scale to operate.

Alphabetic Minimax Trees Of Degree At Most T*, D. Coppersmith, Maria M. Klawe, Nicholas Pippenger

All HMC Faculty Publications and Research

Problems in circuit fan-out reduction motivate the study of constructing various types of weighted trees that are optimal with respect to maximum weighted path length. An upper bound on the maximum weighted path length and an efficient construction algorithm will be presented for trees of degree at most t, along with their implications for circuit fan-out reduction.

Reliable Computation In The Presence Of Noise, Nicholas Pippenger

All HMC Faculty Publications and Research

This talk concerns computation by systems whose components exhibit noise (that is, errors committed at random according to certain probabilistic laws). If we aspire to construct a theory of computation in the presence of noise, we must possess at the outset a satisfactory theory of computation in the absence of noise.

A theory that has received considerable attention in this context is that of the computation of Boolean functions by networks (with perhaps the strongest competition coming from the theory of cellular automata; see [G] and [GR]). The theory of computation by networks associates with any two sets Q and …

Some Graph-Colouring Theorems With Applications To Generalized Connection Networks, David G. Kirkpatrick, Maria M. Klawe, Nicholas Pippenger

All HMC Faculty Publications and Research

With the aid of a new graph-colouring theorem, we give a simple explicit construction for generalized n-connectors with 2k - 1 stages and O( n^{1 + 1 / k} (log n )^{( k - 1)/ 2} ) edges. This is asymptotically the best explicit construction known for generalized connectors.

Uniqueness Of Positive Solutions For A Class Of Elliptic Boundary Value Problems, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

Uniqueness of non-negative solutions conjectured in an earlier paper by Shivaji is proved. Our methods are independent of those of that paper, where the problem was considered only in a ball. Further, our results apply to a wider class of nonlinearities.

Bounds On The Performance Of Protocols For A Multiple-Access Broadcast Channel, Nicholas Pippenger

All HMC Faculty Publications and Research

A general model is presented for synchronous protocols that resolve conflicts among message transmissions to a multiple-access broadcast channel. An information-theoretic method is used now to show that if only finitely many types of conflicts can be distinguished by the protocol, utilization of the channel at rates approaching capacity is impossible. A random-coding argument is used to show that if the number of conflicting transmissions can be determined (which requires distinguishing infinitely many types of conflicts) then utilization of the channel at rates arbitrarily close to capacity can be achieved.

Existence And Uniqueness For A Variational Hyperbolic System Without Resonance, Peter W. Bates, Alfonso Castro

All HMC Faculty Publications and Research

In this paper, we study the existence of weak solutions of the problem

□u + ∇G(u) = f(t,x) ; (t,x) є Ω ≡ (0,π)x(0,π)

u(t,x) = 0 ; (t,x) є ∂Ω

where □ is the wave operator ∂²/∂t² - ∂²/∂x², G: Rⁿ→R is a function of class C² such that ∇G(0) = 0 and f:Ώ→R^n is a continuous function having first derivative with respect to t in (L₂,(Ω))ⁿ and satisfying

f(0,x) = f(π,x) = 0

for all x є [0,π].

A New Lower Bound For The Number Of Switches In Rearrangeable Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

For the commonest model of rearrangeable networks with $n$ inputs and $n$ outputs, it is shown that such a network must contain at least $6n \log _6 n + O( n )$ switches. Similar lower bounds for other models are also presented.

Critical Point Theory And The Number Of Solutions Of A Nonlinear Dirichlet Problem, Alfonso Castro, A. C. Lazer

All HMC Faculty Publications and Research

No abstract provided.

A Semilinear Dirichlet Problem, Alfonso Castro

All HMC Faculty Publications and Research

Let Ω be a bounded region in R^n. In this note we discuss the existence of weak solutions (see [4, Section 2]) of the Dirichlet problem:

Δu(x) + g(x, u(x)) + f(x, u(x), ∇u(x)) = 0 ; x є Ω

u(x) = 0 ; x є ∂Ω

where Δ is the Laplacian operator, g : Ω x R → R and f : Ω x Rⁿ⁺¹ → R are functions satisfying the Caratheodory condition (see [2, Section 3]), and ∇ is the gradient operator.

Superconcentrators, Nicholas Pippenger

All HMC Faculty Publications and Research

An $n$-superconcentrator is an acyclic directed graph with $n$ inputs and $n$ outputs for which, for every $r \leqq n$, every set of $r$ inputs, and every set of $r$ outputs, there exists an $r$-flow (a set of $r$ vertex-disjoint directed paths) from the given inputs to the given outputs. We show that there exist $n$-superconcentrators with $39n + O(\log n)$ (in fact, at most $40n$) edges, depth $O(\log n)$, and maximum degree (in-degree plus out-degree) 16.

Toeplitz Operators On Locally Compact Abelian Groups, Henry A. Krieger, C.A. Schaffner

All HMC Faculty Publications and Research

The problem of global optimization of M incoherent phase signals in N complex dimensions is formulated. Then, by using the geometric approach of Landau and Slepian, conditions for optimality are established for $N = 2$, and the optimal signal sets are determined for $M = 2,3,4,6$ and 12.

The method is the following: The signals are assumed to be equally probable and to have equal energy, and thus are represented by points ${\bf s}_j $, $j = 1,2, \cdots ,M$, on the unit sphere $S_1 $ in $C^N $. If $W_{jk} $ is the half space determined by ${\bf s}_j …