Search

In this paper, we propose a new approach to deformable image registration that captures sliding motions. The large deformation diffeomorphic metric mapping (LDDMM) registration method faces challenges in representing sliding motion since it per construction generates smooth warps. To address this issue, we extend LDDMM by incorporating both zeroth- and first-order momenta with a nondifferentiable kernel. This allows us to represent both discontinuous deformation at switching boundaries and diffeomorphic deformation in homogeneous regions. We provide a mathematical analysis of the proposed deformation model from the viewpoint of discontinuous systems. To evaluate our approach, we conduct experiments on both artificial images and the publicly available DIR-Lab 4DCT dataset. Results show the effectiveness of our approach in capturing plausible sliding motion. [ABSTRACT FROM AUTHOR]

The article highlights two papers published within the issue titled "Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm," by Steven Brams, Michael Jones and Christian Klamler, and "Impossibility of Fast Stable Approximation of Analytic Functions from Equispaced Samples," by Rodrigo Platte, Lloyd Trefethen and Arno Kuijlaars. The first paper discussed the mathematical problem of proportional division. The second one talked about potential theory, matrix iterations in the form of Krylov space methods and quadrature formulae.

Phages are ubiquitous in nature, but many essential factors of host-phage biology have not yet been integrated into mathematical models. In this paper, we investigate a spatial phage-bacteria model to describe the propagation of phages and bacteria in different types of nutrient media. Unlike existing models, we construct a more realistic reaction-diffusion model that incorporates inoculum and bacterial growth and movement, then rigorous mathematical analysis is challenging. We study traveling wave solutions and obtain complete information about the existence and nonexistence of nontrivial traveling wave solutions. The threshold conditions for the existence and nonexistence of traveling wave solutions are obtained by using Schauder's fixed point theorem, limiting argument, and one-sided Laplace transform. Considering different propagation media, we extend the existence of traveling wave solutions from liquid nutrition model to agar model. Moreover, in the absence of bacterial mortality, we obtain the existence of a new traveling wave solution describing phage invasion. We attempt to explain the occurrence of co-transport by the existence and nonexistence of traveling waves, and screen out the key parameters affecting the co-transport of phages and bacteria according to the definition of critical wave speed. Finally, we provide numerical simulations to verify the theoretical results and reveal the effects of key parameters on the propagation of phages and bacteria. [ABSTRACT FROM AUTHOR]

This article is concerned with a class of prey-predator systems with indirect preytaxis, which means the stimulus released by the prey causes the directional movement of the predator. Under homogeneous Neumann boundary conditions, the dynamics of such systems have been studied extensively. However, the corresponding Dirichlet problem remains largely unexplored. The purpose of this paper is to discuss the existence and nonexistence of positive steady-state solutions and make a detailed description for the global bifurcation structure of the set of positive steady-state solutions. Compared with the original systems without indirect prey-taxis, our mathematical analysis shows that the introduction of indirect prey-taxis not only makes mathematical analysis more difficult, but also affects the bifurcation structure of the set of positive steady-state solutions. We hope this work will inspire further research on prey-predator systems with indirect prey-taxis. [ABSTRACT FROM AUTHOR]

Just when modern computers (digital, electronic, and programmable) were being invented, John von Neumann and Herman Goldstine wrote a paper to illustrate the mathematical analyses that they believed would be needed to use the new machines effectively and to guide the development of still faster computers. Their foresight and the congruence of historical events made their work the first modern paper in numerical analysis. Von Neumann once remarked that to found a mathematical theory one had to prove the first theorem, which he and Goldstine did for the accuracy of mechanized Gaussian elimination--but their paper was about more than that. Von Neumann and Goldstine described what they surmised would be the significant questions once computers became available for computational science, and they suggested enduring ways to answer them. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the energy minimization model arising in the ensemble Kohn--Sham density functional theory for metallic systems, in which a pseudo-eigenvalue matrix and a general smearing approach are involved. We study the invariance of the energy functional and the existence of the minimizer of the ensemble Kohn--Sham model. We propose an adaptive twoparameter step size strategy and the corresponding preconditioned conjugate gradient methods to solve the energy minimization model. Under some mild but reasonable assumptions, we prove the global convergence for the gradients of the energy functional produced by our algorithms. Numerical experiments show that our algorithms are efficient, especially for large scale metallic systems. In particular, our algorithms produce convergent numerical approximations for some metallic systems, for which the traditional self-consistent field iterations fail to converge. [ABSTRACT FROM AUTHOR]

Magnetic resonance electrical impedance tomography (MREIT) aims to recover the electrical conductivity distribution of an object using partial information of magnetic flux densities inside the tissue which can be measured using a magnetic resonance imaging scanner, with the advantage that a higher spatial resolution of conductivity image can be provided than existing EIT techniques involving surface measurements. Traditional MREIT reconstruction algorithms use two data sets obtained with two linearly independent injected currents. However, injection of two currents is often not possible in applications such as transcranial electrical stimulation. Recently, we proposed an iterative conductivity reconstruction algorithm called the single-current harmonic Bz algorithm that demonstrated satisfactory performance in numerical and phantom tests. In this paper, we provide a rigorous mathematical analysis of the convergence of the iterative sequence for realizing this algorithm. We prove that, applying some mild conditions on the exact conductivity, the iterative sequence converges to the true solution within an explicit error bound. Such theoretical results substantiate the reasonability and efficiency of the proposed algorithm. We also provide more numerical evidence to validate these theoretical results. [ABSTRACT FROM AUTHOR]

We propose a mathematical theory of acoustic wave scattering in one-dimensional finite high-contrast media. The system considered is constituted of a finite alternance of high-contrast segments of arbitrary lengths and interdistances, called the "resonators," and a background medium. We prove the existence of subwavelength resonances, which are the counterparts of the well-known Minnaert resonances in three-dimensional systems. One of the main contribution of the paper is to show that the resonant frequencies as well as the transmission and reflection properties of the system can be accurately predicted by a "capacitance" eigenvalue problem, analogously to the threedimensional setting. Moreover, we discover new properties which are peculiar to the one-dimensional setting, notably the tridiagonal structure of the capacitance matrix as well as the fact that the first resonant frequency is always exactly zero, implying a low-pass filtering property of a one-dimensional chain of resonators. Numerical results considering different situations with N = 1 to N = 6 resonators are provided to support our mathematical analysis and to illustrate the various possibilities offered by high-contrast resonators to manipulate waves at subwavelength scales. [ABSTRACT FROM AUTHOR]

This paper establishes a posteriori error analysis for the Stokes equations discretized by an interior penalty type method using H(div) finite elements. The a posteriori error estimator is then employed for designing two grid refinement strategies; one is locally based and the other is globally based. The locally based refinement technique is believed to be able to capture local singularities in the numerical solution. The numerical formulations for the Stokes problem make use of H(div) conforming elements of Raviart-Thomas type. Therefore, the finite element solution features a full satisfaction of the continuity equation (mass conservation). The result of this paper provides a rigorous analysis for the method's reliability and efficiency. In particular, an H¹ norm a posteriori error estimator is obtained, together with upper and lower bound estimates. Numerical results are presented to verify the new theory of a posteriori error estimators. [ABSTRACT FROM AUTHOR]

The focal point of this paper is the probabilistically constrained linear program (PCLP) and how it can be applied to control system, design under risk constraints. The PCLP is the counterpart of the classical linear program, where it is assumed that there is random uncertainty in the constraints and, therefore, the deterministic constraints are replaced by probabilistic ones. It is shown that for a wide class of probability density functions, called log-concave symmetric densities, the PCLP is a convex program. An equivalent formulation of the PCLP is also presented which provides insight into numerical implementation. This concept is applied to control system design. It is shown how the results in this paper can be applied to the design of controllers for discrete-time systems to obtain a closed loop system with a well-defined risk of violating the so-called property of svperstability. Furthermore, we address the problem of risk-adjusted pole placement. [ABSTRACT FROM AUTHOR]

The goal of this paper is to relate the capacitance matrix formalism to the tightbinding approximation. By doing so, we open the way to the use of mathematical techniques and tools from condensed matter theory in the mathematical and numerical analysis of metamaterials, in particular for the understanding of their topological properties. We first study how the capacitance matrix formalism, both when the material parameters are static and modulated, can be posed in a Hamiltonian form. Then, we use this result to compare this formalism to the tight-binding approximation. We prove that the correspondence between the capacitance formulation and the tight-binding approximation holds only in the case of dilute resonators. On the other hand, the tight-binding model is often coupled with a nearest-neighbor approximation, whereby long-range interactions are neglected. Even in the dilute case, we show that long-range interactions between subwavelength resonators are relatively strong and nearest-neighbor approximations are not generally appropriate. [ABSTRACT FROM AUTHOR]

In the first part of the paper we provide a new classification of incompressible fluids characterized by a continuous monotone relation between the velocity gradient and the Cauchy stress. The considered class includes Euler fluids, Navier--Stokes fluids, classical power-law fluids as well as stress power-law fluids, and their various generalizations including the fluids that we refer to as activated fluids, namely, fluids that behave as an Euler fluid prior activation and behave as a viscous fluid once activation takes place. We also present a classification concerning boundary conditions that are viewed as the constitutive relations on the boundary. In the second part of the paper, we develop a robust mathematical theory for activated Euler fluids associated with different types of the boundary conditions ranging from no-slip to free-slip and include Navier's slip as well as stick-slip. Both steady and unsteady flows of such fluids in three-dimensional domains are analyzed. [ABSTRACT FROM AUTHOR]

Image deblurring under Rician noise has attracted considerable attention in imaging science. Frequently appearing in medical imaging, Rician noise leads to an interesting nonconvex optimization problem, termed as the MAP-Rician model, which is based on the Maximum a Posteriori (MAP) estimation approach. As the MAP-Rician model is deeply rooted in Bayesian analysis, we want to understand its mathematical analysis carefully. Moreover, one needs to properly select a suitable algorithm for tackling this nonconvex problem to get the best performance. This paper investigates both issues. Indeed, we first present a theoretical result about the existence of a minimizer for the MAP-Rician model under mild conditions. Next, we aim to adopt an efficient boosted difference of convex functions algorithm (BDCA) to handle this challenging problem. Basically, BDCA combines the classical difference of convex functions algorithm (DCA) with a backtracking line search, which utilizes the point generated by DCA to define a search direction. In particular, we apply a smoothing scheme to handle the nonsmooth total variation (TV) regularization term in the discrete MAP-Rician model. Theoretically, using the Kurdyka--Lojasiewicz (KL) property, the convergence of the numerical algorithm can be guaranteed. We also prove that the sequence generated by the proposed algorithm converges to a stationary point with the objective function values decreasing monotonically. Numerical simulations are then reported to clearly illustrate that our BDCA approach outperforms some state-of-the-art methods for both medical and natural images in terms of image recovery capability and CPU-time cost. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with the recovery of the geometric shapes of inhomogeneous inclusions from the associated far field data in electrostatics and acoustic scattering. We present a local resolution analysis and show that the local shape around a boundary point with a mean curvature of high magnitude can be reconstructed more easily and stably. In proving this, we develop a novel mathematical scheme by analyzing the generalized polarization tensors (GPTs) and the scattering coefficients (SCs) coming from the associated scattered fields, which in turn boils down to the analysis of the layer potential operators that sit inside the GPTs and SCs via microlocal analysis. In a delicate and subtle manner, we decompose the reconstruction process into several steps, where all but one step depends on the global geometry, and one particular step depends on the mean curvature at the given boundary point. Then by a sensitivity analysis with respect to local perturbations of the curvature of the boundary surface, we establish the local resolution effects. Our study opens up a new field of mathematical analysis on wave superresolution imaging. [ABSTRACT FROM AUTHOR]

This paper is mainly concerned with a two-species competition model in open advective environments, where individuals cannot pass through the upstream boundary and do not return to the habitat after leaving the downstream boundary. By the theory of principal eigenvalue, we first obtain two critical curves (Γ1 and Γ2) in the plane of bifurcation parameters that sharply determine the local stability of the two semitrivial steady states. Then under various conditions on given parameters, we discuss the global dynamics via different techniques, including the comparison principle for eigenvalues and perturbation and compactness arguments, and show that both competitive exclusion and coexistence are possible. For general values of parameters, we take both analytic and numerical approaches to further understand the potential behaviors of Γ1 and Γ2, and we numerically observe that in addition to the competitive exclusion and coexistence, the bistable phenomenon is also possible, which is different from the known results of competitive ODE and reaction-diffusion systems (where bistability is impossible). The implication of our numerical results on future work is also discussed. [ABSTRACT FROM AUTHOR]

In this paper we characterize the regularity structure, as well as show the global-in-time existence and uniqueness, of (energy) conservative solutions to the Hunter--Saxton equation by using the method of characteristics. The major difference between the current work and previous results is that we are able to characterize the singularities of energy measure and their nature in a very precise manner. In particular, we show that singularities, whose temporal and spatial locations are also explicitly given in this work, may only appear at at most countably many times, and are completely determined by the absolutely continuous part of initial energy measure. Our mathematical analysis is based on using the method of characteristics in a generalized framework that consists of the evolutions of solutions to the Hunter--Saxton equation and the energy measure. This method also provides a clear description of the semigroup property for the solution and energy measure for all times. [ABSTRACT FROM AUTHOR]

In this paper, we prove the global existence and uniqueness of a mild solution to the relativistic Boltzmann equation both in the whole space and in torus for a class of initial data with bounded velocity-weighted L∞-norm and some smallness on Lx¹Lp∞ -norm as well as on defect mass, energy, and entropy. Moreover, the asymptotic stability of the solutions is also investigated in the case of torus. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to investigate mathematically the fundamental mechanism of gas discharge. Townsend discovered that α- and γ-mechanisms are essential for a gas ionization process. Morrow, Degond, and Lucquin-Desreux derived a mathematical model taking these two mechanisms into account. This model consists of nonlinear hyperbolic, parabolic, and elliptic partial differential equations. In this paper, we establish a framework for analyzing this model rigorously, because no mathematical result has been announced. More precisely, we show the unique existence of a time-local solution to an initial-boundary value problem over an unbounded domain. The main difficulty of this problem lies in the fact that the direction of boundary characteristics of a hyperbolic equation degenerates at infinite distance. Generally speaking, the regularity of solutions to linearized hyperbolic equations with degenerate boundary characteristics may be lost near the boundary. This implies the possibility that loss on the derivatives arises at each step of the inductive scheme to solve the nonlinear problem. We first use the weighted Sobolev spaces in the construction of solutions to make clear the direction of characteristics. Furthermore, we reduce the initial-boundary value problem for the hyperbolic equation to an initial value problem by applying several extension operators. This reduction enables us to avoid the loss on the derivatives. [ABSTRACT FROM AUTHOR]

The paper considers the problem of absolute stability of systems with time-periodic nonlinear blocks. The approach presented in this paper is based on the so-called quadratic criterion and relies on integral-quadratic inequalities (constraints), which also involve time delays. The results are given in the frequency domain. The paper also includes geometric interpretation and numerical treatment of the new stability criteria. [ABSTRACT FROM AUTHOR]

The blade element momentum (BEM) theory introduced by Lock et al. and formulated in its modern form by Glauert provides a framework to model the aerodynamic interaction between a turbine and a fluid flow. This theory is used either to estimate turbine efficiency or as a design aid. However, a lack of mathematical interpretation limits the understanding of some of its issues. The aim of this paper is to propose an analysis of BEM equations. Our approach is based on a reformulation of Glauert's model which enables us to identify criteria to guarantee the existence of solutions, analyze the convergence of usual and new (and more efficient) solution algorithms, and study turbine design procedures. The mathematical analysis is completed by numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, combining the ideas of exponential integrators and discrete gradients, we propose and analyze a new structure-preserving exponential scheme for the conservative or dissipative system ẏ = Q(My +∇U(y)), where Q is a d×d skew-symmetric or negative semidefinite real matrix, M is a d×d symmetric real matrix, and U : ℝd → ℝ is a differentiable function. We present two properties of the new scheme. The paper is accompanied by numerical results that demonstrate the remarkable superiority of our new scheme in comparison with other structure-preserving schemes in the scientific literature. [ABSTRACT FROM AUTHOR]

Dynamical low-rank algorithms are a class of numerical methods that compute lowrank approximations of dynamical systems. This is accomplished by projecting the dynamics onto a low-dimensional manifold and writing the solution directly in terms of the low-rank factors. The approach has been successfully applied to many types of differential equations. Recently, efficient dynamical low-rank algorithms have been proposed in [L. Einkemmer, A Low-Rank Algorithm for Weakly Compressible Flow, arXiv:1804.04561, 2018; L. Einkemmer and C. Lubich, SIAM J. Sci. Comput., 40 (2018), pp. B1330-B1360] to treat kinetic equations, including the Vlasov-Poisson and the Boltzmann equation. There it was demonstrated that the methods are able to capture the lowrank structure of the solution and significantly reduce numerical cost, while often maintaining high accuracy. However, no numerical analysis is currently available. In this paper, we perform an error analysis for a dynamical low-rank algorithm applied to the multiscale linear Boltzmann equation (a classical model in kinetic theory) to showcase the validity of the application of dynamical lowrank algorithms to kinetic theory. The equation, in its parabolic regime, is known to be rank 1 theoretically, and we will prove that the scheme can dynamically and automatically capture this low-rank structure. This work thus serves as the first mathematical error analysis for a dynamical low-rank approximation applied to a kinetic problem. [ABSTRACT FROM AUTHOR]

We prove the existence of large-data global-in-time weak solutions to an evolutionary PDE system describing flows of incompressible heat-conducting viscoelastic rate-type fluids with stress-diffusion, subject to a stick-slip boundary condition for the velocity and a homogeneous Neumann boundary condition for the extra stress tensor. In the introductory section we develop the thermodynamic foundations of the proposed model, and we document the role of thermodynamics in obtaining critical structural relations between the quantities of interest. These structural relations are then exploited in the mathematical analysis of the governing equations. In particular, the definition of weak solution is motivated by the thermodynamic basis of the model. The extra stress tensor describing the elastic response of the fluid is in our case purely spherical, which is a simplification from the physical point of view. The model nevertheless exhibits features that require novel mathematical ideas in order to deal with the technically complex structure of the associated internal energy and the more complicated forms of the corresponding entropy and energy fluxes. The paper provides the first rigorous proof of the existence of large-data global-in-time weak solutions to the governing equations for coupled thermo-mechanical processes in viscoelastic rate-type fluids. [ABSTRACT FROM AUTHOR]

This paper presents the first detailed mathematical analysis of the ripple compensation technique for reducing audio distortion in a class-D amplifier with negative feedback. The amplifier converts a relatively low-frequency audio signal to a high-frequency train of rectangular pulses whose widths are slowly modulated according to the audio signal (pulse-width modulation, PWM). Distortion manifests itself through unwanted audio-frequency harmonics that arise in the output due to nonlinearities inherent in the design. In this paper, we first develop a small-signal model, which describes the fate of small-amplitude perturbations to a constant input, and demonstrate how this traditional engineering tool may be extended to allow one to infer the most significant contributions to the full output in response to a general audio input. We then compute the audio output of the amplifier through a perturbation expansion based on the ratio between audio and switching frequencies. Our results explicitly demonstrate how the ripple compensation technique significantly linearizes the output, thereby reducing the distortion. [ABSTRACT FROM AUTHOR]

The paper studies the convergence properties of (continuous-time) best-response dynamics from game theory. Despite their fundamental role in game theory, best-response dynamics are poorly understood in many games of interest due to the discontinuous, set-valued nature of the best-response map. The paper focuses on elucidating several important properties of best-response dynamics in the class of multiagent games known as potential games--a class of games with fundamental importance in multiagent systems and distributed control. It is shown that in almost every potential game and for almost every initial condition, the best-response dynamics (i) have a unique solution, (ii) converge to pure-strategy Nash equilibria, and (iii) converge at an exponential rate. [ABSTRACT FROM AUTHOR]

The continuum limit of coupled dynamical systems is an approximate procedure, by which the dynamical problem on a sequence of large graphs is replaced by an evolution integral equation on a continuous spatial domain. While this method has been widely used in the analysis of pattern formation in nonlocally coupled networks, its mathematical basis remained little understood. In this paper, we use the combination of ideas and results from the theory of graph limits and nonlinear evolution equations to provide a rigorous mathematical justification for taking the continuum limit and to extend this method to cover many complex networks, for which it has not been applied before. Specifically, for dynamical networks on convergent sequences of simple and weighted graphs, we prove convergence of solutions of the initial-value problems for discrete models to those of the limiting continuous equations. In addition, for sequences of simple graphs converging to {0, 1}-valued graphons, it is shown that the convergence rate depends on the fractal dimension of the boundary of the support of the graph limit. These results are then used to study the coexistence of coherence and incoherence in chimera states and the attractors of the nonlocal Kuramoto equation on certain multipartite graphs. Furthermore, the analytical tools developed in this work are used in the rigorous justification of the continuum limit for networks on random graphs that we undertake in a companion paper [Arch. Ration. Mech. Anal., 21 (2014), pp. 781-803]. As a by-product of the analysis of the continuum limit on deterministic and random graphs, we identify the link between this problem and the convergence analysis of several classical numerical schemes: the collocation, Galerkin, and Monte Carlo methods. Therefore, our results can be used to characterize convergence of these approximate methods of solving initial-value problems for nonlinear evolution equations with nonlocal interactions. [ABSTRACT FROM AUTHOR]

This paper proposes, for wave propagating in a globally perturbed half-plane with a perfectly conducting step-like surface, a sharp Sommerfeld radiation condition (SRC) for the first time, an analytic formula of the far field pattern, and a high-accuracy numerical solver. We adopt the Wiener--Hopf method to compute the Green function for a cracked half-plane, a special background for the perturbed half-plane. We rigorously show that the Green function asymptotically satisfies a universal-direction SRC (uSRC) and is purely outgoing at infinity. This helps to propose an implicit transparent boundary condition for the scattered wave, produced by either a cylindrical incident wave due to a line source or a plane incident wave. Then, a well-posedness theory is established via an associated variational formulation. The theory reveals that the scattered wave, after subtracting a known wave field, satisfies the same uSRC so that its far field pattern is accessible theoretically. For a plane-wave incidence, asymptotic analysis shows that merely subtracting reflected plane waves from the scattered wave in respective regions, due to nonuniform heights of the step-like surface, is sufficient to produce an outgoing wave satisfying the uSRC. Numerically, we adopt a previously developed perfectly matched layer (PML) boundary integral equation method to solve the problem. Numerical results demonstrate that the PML truncation error decays exponentially fast as thickness or absorbing power of the PML increases. Such an exponential convergence relies heavily on the fact that the background Green function exponentially decays in the PML. [ABSTRACT FROM AUTHOR]

In this paper we investigate a passivity approach to collective coordination and synchronization problems in the presence of quantized measurements and show that coordination tasks can be achieved in a practical sense for a large class of passive systems. [ABSTRACT FROM AUTHOR]

This paper considers stability and harmonic analysis of a general class of pulse-modulated systems. The systems are modeled using the dynamic phasor model, which explores the cyclic nature of the modulation functions by representing the system state as a Fourier series expansion defined over a moving time window. The contribution of the paper is to show that a special type of periodic Lyapunov function can be used to analyze the system and that the analysis conditions become tractable for computation after truncation. The approach provides a trade-off between complexity and accuracy that includes standard state space averaged models as a special case. The paper also shows how the dynamic phasor model can be used to derive a frequency domain input-to-state map which is analogous to the harmonic transfer function. [ABSTRACT FROM AUTHOR]

A random vector X is called R+-weakly stable if for all (nonnegative) random variables Θ1 and Θ2 independent of X, X′ there exists a (nonnegative) random variable Θ independent of X such that Θ1X + Θ2X′ d= ΘX. In this paper, as an answer to the open question given in [J. K. Misiewicz, K. Oleszkiewicz, and K. Urbanik, Studia Math., 167 (2005), pp. 195–213] we show that R+-weakly stable distributions have the same properties and stochastic structure as weakly stable distributions. [ABSTRACT FROM AUTHOR]

A neighbor system, introduced in this paper, is a collection of integral vectors in ℝn with some special structure. Such collections (slightly) generalize jump systems, which, in turn, generalize integral bisubmodular polyhedra, integral polymatroids, delta-matroids, matroids, and other structures. We show that neighbor systems provide a systematic and simple way to characterize these structures. One of our main results is a simple greedy algorithm for optimizing over (finite) neighbor systems starting from any feasible vector. The algorithm is (essentially) identical to the usual greedy algorithm on matroids and integral polymatroids when the starting vector is zero. But in all other cases, from matroids through jump systems, it appears to be a new greedy algorithm. We end the paper by introducing another structure, which is more general than neighbor systems, and indicate that essentially the same greedy algorithm also works for this structure. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n3 log3 log n/ log2 n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n3-(3-ω)/(2d+4)), where ω < 2.376; in two dimensions, this is O(n2.922). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n3-(3-ω)/4) = O(n2.844) time) for APSP in real- vertex-weighted graphs, as well as an improved result (near O(n(3+ω)/2) = O(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs. [ABSTRACT FROM AUTHOR]

Let X = (x1,x2,…,xn) be a sample consisting of n independent observations in an arbitrary measurable space X such that the first θ observations have a distribution F while the remaining n - θ ones follow G ≠ F, the distributions F and G being unknown and quantities n and θ large. In [A. A. Borovkov and Yu. Yu. Linke, Math. Methods Statist., 14 (2005), pp. 404-430] there were constructed estimators θ* of the change-point 0 that have proper error (i.e., such that Pθ{∣θ* -θ∣ > k} tends to zero ask grows to infinity), under the assumption that we know a function h for which the mean values of h(xj) under the distributions F and G are different from each other. Sequential procedures were also presented in that paper. In the present paper, we obtain similar results under a weakened form of the above assumption or even in its absence. One such weaker version assumes that we have functions h1, h2,… , h1 on X such that for at least one of them the mean values of hj (xi) are different under F and C. Another version does not assume the existence of known to us functions hj, but allows the possibility of estimating the unknown distributions F and C from the initial and terminal segments of the sample X. Sequential procedures are also dealt with. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we reexamine the all-pairs shortest path (APSP) problem and present a new algorithm with running time O(n³ log³ log n/ log² n), which improves all known algorithms for general real-weighted dense graphs. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n3-(3-ω)/(2d+4)), where logω < 2.376; in two dimensions, this is O(n2.922). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n3-(3-logω)/4) = O(n2.844) time) for APSP in real- vertex-weighted graphs, as well as an improved result (near O(n(3+logω)/2) = O(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs. [ABSTRACT FROM AUTHOR]

A common thread in all of the recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653-750] in the paper that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable. [ABSTRACT FROM AUTHOR]

The current paper proposes a parametric eigenvalue problem for the Helmholtz equation on the plane based on two well-known physical models of emission from two-dimensional (2-D) microcavity lasers. The first model has been developed for passive, either lossy or lossless, open cavities and is usually referred to as the Complex-Frequency Eigenvalue Problem. The second model, named the Lasing Eigenvalue Problem (LEP), has been tailored to characterize emission from open cavities, filled in with gain material, on the threshold of nonattenuating in time radiation. Our generalized model contains both of them as special cases. We reduce the original problem to a nonlinear eigenvalue problem for a set of boundary integral equations with weakly singular kernels and formulate it as a parametric eigenvalue problem for a holomorphic Fredholm operator-valued function, which is convenient for mathematical and numerical analysis. Using this formulation and fundamental results of the theory of holomorphic operator-valued functions, we study the properties of the spectrum. For numerical solution of the problem, we propose a Nyström method, prove its convergence, and derive error estimates in the eigenvalue approximation. Combining this discretization with the residual inverse iteration technique, we compute approximate solutions of LEP and compare them with the exact ones and with the results obtained using other numerical methods. [ABSTRACT FROM AUTHOR]

Abstract. In this paper we consider a general hyperbolic branching diffusion on a Lobachevsky space Hd. The question is to evaluate the Hausdorif dimension of the limiting set on the boundary (i.e., absolute) ∂Hd. In the case of a homogeneous branching diffusion, an elegant formula for the Hausdorif dimension was obtained by Lalley and Sellke [Probab. Theory Related Fields, 108 (1997), pp. 171-192] for d = 2 and by Karpelevich, Pechersky, and Suhov [Commun. Math. Phys., 195 (1998), pp. 627-642] for a general d. Later on, Kelbert and Suhov [Probab. Theory AppI., 51 (2007), pp. 155-167] extended the formula to the case where the branching diffusion was in a sense asymptotically homogeneous (i.e., its main relevant parameter, the fission potential, approached a constant limiting value near the absolute). In this paper we show that the Hausdorif dimension of the limiting set can be bounded from above and below in terms of the maximum and minimum points of the fission potential. As in [M. Kelbert and Y. M. Suhov, Probab. Theory AppI., 51(2007), pp. 155-167], the method is based on properties of the minimal solution to a Sturm-Liouville problem with general potential and elements of the harmonic analysis on Hd. We also relate the Hausdorff dimension with properties of recurrence and transience of a branching diffusion, as was defined by Grigoryan and Kelbert [Ann. Probab., 31(2003), pp. 244-284] on a general-type manifold. [ABSTRACT FROM AUTHOR]

Dissipative systems have played an important role in the analysis and synthesis of dynamical systems. The commonly used definition of dissipativity often requires an assumption on the controllability of the system. In this paper we use a definition of dissipativity that is slightly different (and less often used in the literature) to study a linear, time-invariant, possibly uncontrollable dynamical system. We provide a necessary and sufficient condition for an uncontrollable system to be strictly dissipative with respect to a supply rate under the assumption that the uncontrollable poles are not "mixed"; i.e., no pair of uncontrollable poles is symmetric about the imaginary axis. This condition is known to be related to the solvability of a Lyapunov equation; we link Lyapunov functions for autonomous systems to storage functions of an uncontrollable system. The set of storage functions for a controllable system has been shown to be a convex bounded polytope in the literature. We show that for an uncontrollable system the set of storage functions is unbounded, and that the unboundedness arises precisely due to the set of Lyapunov functions for an autonomous linear system being unbounded. Further, we show that stabilizability of a system results in this unbounded set becoming bounded from below. Positivity of storage functions is known to be very important for stability considerations because the maximum stored energy that can be drawn out is bounded when the storage function is positive. In this paper we establish the link between stabilizability of an uncontrollable system and existence of positive definite storage functions. In most of the results in this paper, we assume that no pair of the uncontrollable poles of the system is symmetric about the imaginary axis; we explore the extent of necessity of this assumption and also prove some results for the case of single output systems regarding this necessity. [ABSTRACT FROM AUTHOR]

This paper presents applications of an optimization-based multigrid method to state constrained aerodynamic shape optimization problems. The one-shot simultaneous pseudo-timestepping method has been applied successfully to such problems, reducing the cost of computation up to 70% from that of a traditional gradient method. However, the number of optimization iterations is comparatively large in this method since we update the design parameters in each time-step of state and costate runs. In this paper we use an optimization-based multigrid strategy to reduce the total number of optimization iterations while keeping the idea of the one-shot pseudo-time-stepping method. Design examples of drag reduction with constant lift, together with geometrical constraints, for an RAE2822 airfoil are included. The total effort required for convergence of the optimization problem is between four and six times that of forward simulation runs depending on computational grid size. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of sensitivity analysis in calculus of variations. A perturbation technique is applied to derive the boundary value problem and the system of equations that allow us to obtain the partial derivatives (sensitivities) of the objective function value and the primal and dual optimal solutions with respect to all parameters. Two examples of applications, a simple mathematical problem and a slope stability analysis problem, are used to illustrate the proposed method. [ABSTRACT FROM AUTHOR]

We study high order numerical quadratures to one dimensional delta function integrals in this paper. This is motivated by the fact that traditional numerical quadratures give only first order accuracy in general. We provide criteria on discrete delta functions and support size formulas which ensure any desired accuracy of the numerical quadratures. Discrete delta functions and support size formulas satisfying these criteria are designed. Numerical examples are presented to verify the performed analysis and the high order accuracy of the proposed numerical quadratures. [ABSTRACT FROM AUTHOR]

In the present paper, the notion of a weak solution of a general backward stochastic differential equation (BSDE), which was introduced by the authors and A. Răşcanu in [Theory Probab. Appl., 49 (2005), pp. 16-50], will be discussed. The relationship between continuity of solutions, pathwise uniqueness, uniqueness in law, and existence of a pathwise unique strong solution is investigated. The main result asserts that if all weak solutions of a BSDE are continuous, then the solution is pathwise unique. One should notice that this is a specific result for BSDEs and there is of course no counterpart for (forward) stochastic differential equations (SDEs). As a consequence, if a weak solution exists and all solutions are continuous, then there exists a pathwise unique solution and this solution is strong. Moreover, if the driving process is a continuous local martingale satisfying the previsible representation property, then the converse is also true. In other words, the existence of discontinuous solutions to a BSDE is a natural phenomenon, whenever pathwise uniqueness or, in particular, uniqueness in law is not satisfied. Examples of discontinuous solutions of a certain BSDE were already given in [R. Buckdahn and H.-J. Engelbert, Proceedings of the Fourth Colloquium on Backward Stochastic Differential Equations and Their Applications, to appear]. This was the motivation for the present paper which is aimed at exploring the general situation. [ABSTRACT FROM AUTHOR]

This paper considers an extension of the Merton optimal investment problem to the case where the risky asset is subject to transaction costs and capital gains taxes. We derive the dynamic programming equation in the sense of constrained viscosity solutions. We next introduce a family of functions (Vϵ)ϵ>0, which converges to our value function uniformly on compact subsets, and which is characterized as the unique constrained viscosity solution of an approximation of our dynamic programming equation. In particular, this result justifies the numerical results reported in the accompanying paper [I. Ben Tahar, H. M. Soner, and N. Touzi (2005), Modeling Continuous-Time Financial Markets with Capital Gains Taxes, preprint, http://www.cmap.polytechnique.fr/~touzi/bst06.pdf]. [ABSTRACT FROM AUTHOR]

This paper deals with a problem of guaranteed (robust) financial decision-making under model uncertainty. An efficient method is proposed for determining optimal robust portfolios of risky financial instruments in the presence of ambiguity (uncertainty) on the probabilistic model of the returns. Specifically, it is assumed that a nominal discrete return distribution is given, while the true distribution is only known to lie within a distance d from the nominal one, where the distance is measured according to the Kullback-Leibler divergence. The goal in this setting is to compute portfolios that are worst-case optimal in the mean-risk sense, that is, to determine portfolios that minimize the maximum with respect to all the allowable distributions of a weighted risk-mean objective. The analysis in the paper considers both the standard variance measure of risk and the absolute deviation measure. [ABSTRACT FROM AUTHOR]

In this paper we discuss stability and stabilization of continuous and discrete multidimensional input/output (IO) behaviors (of dimension r) which are described by linear systems of complex partial differential (resp., difference) equations with constant coefficients, where the signals are taken from various function spaces, in particular from those of polynomial-exponential functions. Stability is defined with respect to a disjoint decomposition of the r-dimensional complex space into a stable and an unstable region, with the standard stable region in the one-dimensional continuous case being the set of complex numbers with negative real part. A rational function is called stable if it has no poles in the unstable region. An IO behavior is called stable if the characteristic variety of its autonomous part has no points in the unstable region. This is equivalent to the stability of its transfer matrix and an additional condition. The system is called stabilizable if there is a compensator IO system such that the output feedback system is well-posed and stable. We characterize stability and stabilizability and construct all stabilizing compensators of a stabilizable IO system (parametrization). The theorems and proofs are new but essentially inspired and influenced by and related to the stabilization theorems concerning multidimensional IO maps as developed, for instance, by Bose, Guiver, Shankar, Sule, Xu, Lin, Ying, Zerz, and Quadrat and, of course, the seminal papers of Vidyasagar, Youla, and others in the one-dimensional case. In contrast to the existing literature, the theorems and proofs of this paper do not need or employ the so-called fractional representation approach, i.e., various matrix fraction descriptions of the transfer matrix, thus avoiding the often lengthy matrix computations and seeming to be of interest even for one-dimensional systems (at least to the author). An important mathematical tool, new in systems theory, is Gabriel's localization theory which, only in the case of ideal-convex (Shankar, Sule) unstable regions, coincides with the usual one. Algorithmic tests for stability, stabilizability, and ideal-convexity, and the algorithmic construction of stabilizing compensators, are addressed but still encounter many difficulties; see in particular the open problems listed by Xu et al. [ABSTRACT FROM AUTHOR]

This paper introduces the use of topological models and methods, formerly used to analyze computability, as tools for the quantification and classification of asynchronous complexity. We present the first asynchronous complexity theorem, applied to decision tasks in the iterated immediate snapshot (IIS) model of Borowsky and Gafni. We do so by introducing a novel form of topological tool called the nonuniform chromatic subdivision. Building on the framework of Herlihy and Shavit's topological computability model, our theorem states that the time complexity of any asynchronous algorithm is directly proportional to the level of nonuniform chromatic subdivisions necessary to allow a simplicial map from a task's input complex to its output complex. To show the power of our theorem, we use it to derive a new tight bound on the time to achieve n process approximate agreement in the IIS model: [logd(Multiple line equation(s) cannot be represented in ASCII text)], where d = 3 for two processes and d = 2 for three or more. This closes an intriguing gap between the known upper and lower bounds implied by the work of Aspnes and Herlihy. More than the new bounds themselves, the importance of our asynchronous complexity theorem is that the algorithms and lower bounds it allows us to derive are intuitive and simple, with topological proofs that require no mention of concurrency at all. [ABSTRACT FROM AUTHOR]

The ultimate objective of this paper is to develop new techniques that can be used for the analysis of performance degradation due to statistical uncertainty for a wide class of linear stochastic systems. For this we need new technical tools similar to those used in [L. Gerencsér, Statist. Plann. Inference, 41 (1994), pp. 303–325]. The immediate technical objective is to extend the previous technical results to the Djereveckii-Fradkov-Ljung scheme with enforced boundedness. Our starting point is a standard approximation of the estimation error used in the asymptotic theory of recursive estimation. Tight control of the difference between the estimation error and its standard approximation, referred to as residuals, is a crucial point in our applications. The main technical advance of the present paper is a set of strong approximation theorems for three closely related recursive estimation algorithms in which, for any q ≥ 1, the Lq-norms of the residual terms are shown to tend to zero with rate N-1/2-ϵ with some ϵ > 0. This is a significant extension of previous results for the recursive prediction error or RPE estimator of ARMA processes given in [L. Gerencsér, Systems Control Lett., 21 (1993), pp. 347–351]. Two useful corollaries will be derived. In the first a standard transform of the estimation-error process for the basic recursive estimation method, Algorithm CR, will be shown to be L-mixing, while in the second the asymptotic covariance matrix of the estimator for the same method will be given. Applications to multivariable adaptive prediction and the minimum-variance self-tuning regulator for ARMAX systems will be described. [ABSTRACT FROM AUTHOR]

The paper describes the set of solutions of the discrete-time algebraic Riccati equation. It is shown that each solution is a combination of a pair of opposite unmixed solutions. There is a one-to-one correspondence between solutions and invariant subspaces of the closed loop matrix of an unmixed solution. The results of the paper provide an extended counterpart of the parametrization theory of continuous-time algebraic Riccati equations by Willems, Coppel, and Shayman. [ABSTRACT FROM AUTHOR]

We consider crossbar switching networks with base b (that is, constructed from b×b crossbar switches), scale k (that is, with bk inputs, bk outputs, and bk links between each consecutive pair of stages), and depth l (that is, with l stages). We assume that the crossbars are interconnected according to the spider-web pattern, whereby two diverging paths reconverge only after at least k stages. We assume that each vertex is independently idle with probability q, the vacancy probability. We assume that b ≥ 2 and the vacancy probability q are fixed, and that k and l = ck tend to infinity with ratio a fixed constant c > 1. We consider the linking probability Q (the probability that there exists at least one idle path between a given idle input and a given idle output). In a previous paper [Discrete Appl. Math., 37/38 (1992), pp. 437-450] it was shown that if c ≤ 2, then the linking probability Q tends to 0 if 0 < q < qc (where qc = 1/b(c-1)/c is the critical vacancy probability) and tends to (1 - ξ)² (where ξ is the unique solution of the equation 1 - q(1 - x))b = x in the range 0 < x < 1) if qc < q < 1. In this paper we extend this result to all rational c > 1. This is done by using generating functions and complex-variable techniques to estimate the second moments of various random variables involved in the analysis of the networks. [ABSTRACT FROM AUTHOR]

In this paper we use the penalty approach to study three constrained minimization problems. A penalty function is said to have the exact penalty property [J.-B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms, 2 vols., Springer-Verlag, Berlin, 1993] if there exists a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish a very simple sufficient condition for the exact penalty property. [ABSTRACT FROM AUTHOR]