Search

In this paper, we propose a new kind of numerical simulation method for backward stochastic differential equations (BSDEs). We discretize the continuous BSDEs on time-space discrete grids, use the Monte Carlo method to approximate mathematical expectations, and use space interpolations to compute values at nongrid points. To demonstrate the accuracy and the effectiveness of our method, several numerical examples are given. [ABSTRACT FROM AUTHOR]

This paper has been conceived as an overview on the controllability properties of some relevant (linear and nonlinear) parabolic systems. Specifically, we deal with the null controllability and the exact controllability to the trajectories. We try to explain the role played by the observability inequalities in this context and the need of global Carleman estimates. We also recall the main ideas used to overcome the difficulties motivated by nonlinearities. First, we considered the classical heat equation with Dirichlet conditions and distributed controls. Then we analyze recent extensions to other linear and semilinear parabolic systems and/or boundary controls. Finally, we review the controllability properties for the Stokes and Navier—Stokes equations that are known to date. In this context, we have paid special attention to obtaining the necessary Carleman estimates. Some open questions are mentioned throughout the paper. We hope that this unified presentation will be useful for those researchers interested in the field. [ABSTRACT FROM AUTHOR]

In this paper we study a discrete version of the classical team decision problem. It has been shown previously that the general discrete team decision problem is NP-hard. Here we present an efficient approximation algorithm for this problem. For the maximization version of this problem with nonnegative rewards, this algorithm computes decision rules which are guaranteed to be within a fixed bound of optimal. [ABSTRACT FROM AUTHOR]

The paper presents a scheme to calculate approximations of reach sets and tubes for linear control systems with time-varying coefficients, bounds on the controls, and constraints on the state. The scheme provides tight external approximations by ellipsoid-valued tubes. The tubes touch the reach tubes from the outside at each point of their boundary so that the surface of the reach tube is totally covered by curves that belong to the approximating tubes. The result is an exact parametric representation of reach tubes through families of external ellipsoidal tubes. The parameters that characterize the approximating ellipsoids are solutions of ordinary differential equations with coefficients given partly in explicit analytical form and partly through the solution of a recursive optimization problem. The scheme combines the calculation of external approximations of infinite sums and intersections of ellipsoids, and suggests an approach to calculate reach sets of hybrid systems. [ABSTRACT FROM AUTHOR]

This paper considers a discrete analogue of a three-dimensional Bessel process—a certain discrete random process, which converges to a continuous Bessel process in the sense of the Donsker—Prokhorov invariance principle, and which has an elementary path structure such as in the case of a simple random walk. The paper introduces four equivalent definitions of a discrete Bessel process, which describe this process from different points of view. The study of this process shows that its relationship to the simple random walk repeats the well-known properties which connect the continuous three-dimensional Bessel process with the standard Brownian motion. Thus, hereby we state and prove discrete versions of Pitman's theorem, Williams theorem on Brownian path decomposition, and some other statements related to these two processes. [ABSTRACT FROM AUTHOR]

Necessary and sufficient conditions for the energy norm convergence of the classical iterative methods for semidefinite linear systems are obtained in this paper. These new conditions generalize the classic notion of the P-regularity introduced by Keller. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of minimization of a nonsmooth function under general nonsmooth constraints when no derivatives of the objective or constraint functions are available. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends the generalized pattern search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained. The main GPS convergence result is to identify limit points x0302;, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the general MADS framework is flexible enough to allow the generation of an asymptotically dense set of refining directions along which the Clarke derivatives are nonnegative. We propose an instance of MADS for which the refining directions are dense in the hypertangent cone at x0302; with probability 1 whenever the iterates associated with the refining directions converge to a single x0302;. The instance of MADS is compared to versions of GPS on some test problems. We also illustrate the limitation of our results with examples. [ABSTRACT FROM AUTHOR]

In [S. Safra, Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 319-327] an exponential determinization procedure for Búchi automata was shown, yielding tight bounds for decision procedures of some logics (see [A. E. Emerson and C. Jutla, Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 328-337; Safra (1988); S. Safra and M. Y. Vardi, Proceedings of the 21st ACM Symposium on Theory of Computing, 1989, pp. 127-137; and D. Kozen and J. Tiuryn, Logics of program, in Handbook of Theoretical Computer Science, Elsevier, Amsterdam, 1990, pp. 789-840]). In Safra and Vardi (1989) the complexity of determinization and complementation of ü-automata was further investigated, leaving as an open question the complexity of the determinization of a single class of ü-automata. For this class of ü-automata with strong fairness as an acceptance condition (Streett automata), Safra and Vardi (1989) managed to show an exponential complementation procedure; however, the blow-up of translating these automata—to any of the classes known to admit exponential determinization—is inherently exponential. This might suggest that the blow-up of the determinization of Streett automata is inherently doubly exponential. This paper shows an exponential determinization construction for Streett automata. In fact, the complexity of our construction is roughly the same as the complexity achieved in Safra (1988) for Búchi automata. Moreover, a simple observation extends this upper bound to the complementation problem. Since any ü-automaton that admits exponential determinization can be easily converted into a Streett automaton, we have obtained a single procedure that can be used for all of these conversions. Furthermore, this construction is optimal (up to a constant factor in the exponent) for all of these conversions. Our results imply that Streett automata (with strong fairness as an acceptance condition) can be used instead of Büchi automata (with the weaker acceptance condition) without any loss of efficiency. [ABSTRACT FROM AUTHOR]

This paper uses periodic matrix multiplication to improve the time complexities for a number of graph problems. The time for finding an asteroidal triple is reduced from O(nm) to O(n2.82), and the time for finding a star cutset, a two-pair, and a dominating pair is reduced from O(nm) to O(n2.79). It is also shown that each of these problems is at least as hard as one of three basic graph problems for which the best known algorithms run in times O(nm) and O(nα). We note that the fast matrix multiplication algorithms do not seem to be practical because of the enormous constants needed to achieve the asymptotic time bounds. These results are important theoretically for breaking the n³ barrier rather than giving efficient algorithms for a user. [ABSTRACT FROM AUTHOR]

We present multiscale models of cancer tumor invasion with components at the molecular, cellular, and tissue levels. We provide biological justifications for the model components, present computational results from the models, and discuss the scientific-computing methodology used to solve the model equations. The models and methodology presented in this paper form the basis for developing and treating increasingly complex, mechanistic models of tumor invasion that will be more predictive and less phenomenological. Because many of the features of the cancer models, such as taxis, aging, and growth, are seen in other biological systems, the models and methods discussed here also provide a template for handling a broader range of biological problems. [ABSTRACT FROM AUTHOR]

We establish conditions under which the strategy minimizing the expected value of a cost functional has a much stronger property; namely, it minimizes the random cost functional itself for all realizations of the controlled process belonging to a set, the probability of which is close to one for large time horizons. The main difference of the conditions mentioned from those obtained earlier is that the former do not deal with value function properties but concern a possibility of transition of the controlled process from one state to another in a time with a finite mean. It makes the verification of these conditions in a number of situations of the general form much easier. The first part of the paper concerns processes in discrete time; the second part will be devoted to processes in continuous time. [ABSTRACT FROM AUTHOR]

This paper proposes a thorough investigation of the convergence of the volume averaging method described by Whitaker [The Method of Volume Averaging, Kluwer Academic, Norwell, MA, 1999] as applied to convection-diffusion problems inside a cylinder. A spectral description of volume averaging brings to the fore new perspectives about the mathematical analysis of those approximations. This spectral point of view is complementary with the Lyapunov--Schmidt reduction technique and provides a precise framework for investigating convergence. It is shown for convection-diffusion inside a cylinder that the spectral convergence of the volume averaged description depends on the chosen averaging operator, as well as on the boundary conditions. A remarkable result states that only part of the eigenmodes among the infinite discrete spectrum of the full solution can be captured by averaging methods. This leads to a general convergence theorem (which was already examined with the use of the center manifold theorem [G. N. Mercer and A. J. Roberts, SIAM J. Appl. Math., 50 (1990), pp. 1547--1565] and investigated with Lyapunov--Schmidt reduction techniques [S. Chakraborty and V. Balakotaiah, Chem. Engrg. Sci., 57 (2002), pp. 2545--2564] in similar contexts). Moreover, a necessary and sufficient condition for an eigenvalue to be captured is given. We then investigate specific averaging operators, the convergence of which is found to be exponential. [ABSTRACT FROM AUTHOR]

This paper presents a new verified optimization method for the problem of finding the densest packings of nonoverlapping equal circles in a square. In order to provide reliable numerical results, the developed algorithm is based on interval analysis. As one of the most efficient parts of the algorithm, an interval-based version of a previous elimination procedure is introduced. This method represents the remaining areas still of interest as polygons fully calculated in a reliable way. Currently the most promising strategy of finding optimal circle packing configurations is to partition the original problem into subproblems. Still, as a result of the highly increasing number of subproblems, earlier computer-aided methods were not able to solve problem instances where the number of circles was greater than 27. The present paper provides a carefully developed technique resolving this difficulty by eliminating large groups of subproblems together. As a demonstration of the capabilities of the new algorithm the problems of packing 28, 29, and 30 circles were solved within very tight tolerance values. Our verified procedure decreased the uncertainty in the location of the optimal packings by more than 700 orders of magnitude in all cases. [ABSTRACT FROM AUTHOR]

In this paper, we analyze convergence rates of wavelet schemes for time-dependent convection-reaction equations within the framework of the Eulerian--Lagrangian localized adjoint method (ELLAM). Under certain minimal assumptions that guarantee $ H^1 $-regularity of exact solutions, we show that a generic ELLAM scheme has a convergence rate $ \mathcal{O}(h/\sqrt{\Delta t} + \Delta t) $ in $ L^2 $-norm. Then, applying the theory of operator interpolation, we obtain error estimates for initial data with even lower regularity. Namely, it is shown that the error of such a scheme is $ \mathcal{O}((h/\sqrt{\Delta t})^\theta + (\Delta t)^\theta) $ for initial data in a Besov space $ \displaystyle B^\theta_{2,q} (0 < \theta < 1, 0 < q <= infinity) $. The error estimates are {a priori} and optimal in some cases. Numerical experiments using orthogonal wavelets are presented to illustrate the theoretical estimates. [ABSTRACT FROM AUTHOR]

The aim of this work is to solve hyperbolic conservation laws by means of a finite volume method for both spatial and time discretization. We extend the ideas developed in [X.-D. Liu and S. Osher, SIAM J. Numer. Anal., 33 (1996), pp. 760--779; X.-D. Liu and E. Tadmor, Numer. Math., 79 (1998), pp. 397--425] to fourth-order upwind and central schemes. In order to do this, once we know the cell-averages of the solution, $\overline {u}_j ^n$, in cells $I_{j}$ at time $T=t^n$, we define a new three-degree reconstruction polynomial that in each cell, $I_{j}$, presents the same shape as the cell-averages $\{ {\overline {u}_{j-1} ^n,\overline {u}_j ^n,\overline {u}_{j+1} ^n}\}$. By combining this reconstruction with the nonoscillatory property and the maximum principle requirement described in [X.-D. Liu and S. Osher, SIAM J. Numer. Anal., 33 (1996), pp. 760--779] we obtain a fourth-order scheme that satisfies the total variation bounded (TVB) property. Extension to systems is carried out by componentwise application of the scalar framework. Numerical experiments confirm the order of the schemes presented in this paper and their nonoscillatory behavior in different test problems. [ABSTRACT FROM AUTHOR]

The paper contains a noniterative solver for the Helmholtz and the modified Helmholtz equations in a hexahedron. The solver is based on domain decomposition. The solution domain is divided into mostly parallelepiped subdomains. In each subdomain a particular solution of the nonhomogeneous Helmholtz equation is first computed by a fast spectral 3-D method which was developed in our earlier papers (see, for example, SIAM J. Sci. Comput., 20 (1999), pp. 2237--2260). This method is based on the application of the discrete Fourier transform accompanied by a subtraction technique. For high accuracy the subdomain boundary conditions must be compatible with the specified inhomogeneous right-hand side at the edges of all the interfaces. In the following steps the partial solutions are hierarchically matched. At each step pairs of adjacent subdomains are merged into larger units. The paper describes in detail the matching algorithm for two boxes which is a basis for the domain decomposition scheme. The hierarchical approach is convenient for parallelization and can minimize the global communication. The algorithm requires O (N3, log, N) operations, where N is the number of grid points in each direction. [ABSTRACT FROM AUTHOR]

Local mesh-refining algorithms known from adaptive finite element methods are adopted for locally conservative and monotone finite volume discretizations of boundary value problems for steady-state convection-diffusion-reaction equations. The paper establishes residual-type explicit error estimators and averaging techniques for a posteriori finite volume error control with and without upwind in global H1- and L2-norms. Reliability and efficiency are verified theoretically and confirmed empirically with experimental support for the superiority of the suggested adaptive mesh-refining algorithms over uniform mesh refining. A discussion of adaptive computations in the simulation of contaminant concentration in a nonhomogeneous water reservoir concludes the paper. [ABSTRACT FROM AUTHOR]

In this paper we establish an explicit asymptotic formula for the steady state voltage perturbations caused by closely spaced small conductivity inhomogeneities. Based on this new formula we design a very effective numerical method to identify the location and some geometric features of these inhomogeneities from a finite number of boundary measurements. The viability of our approach is documented by numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the inverse problem of identifying the connectivity and the conductivity of the links between adjacent pair of nodes in a network, in terms of an input-output map. To do this we deal with the weighted Laplacian $\Delta_{\omega}$ and an $\omega$-harmonic function on the graph, with its physical interpretation as a diffusion equation on the graph, which models an electric network. After deriving the basic properties of $\omega$-harmonic functions, we prove the solvability of (direct) problems such as the Dirichlet and Neumann BVPs. Our main result is the global uniqueness of the inverse conductivity problem for a network under a suitable monotonicity condition. [ABSTRACT FROM AUTHOR]

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties. [ABSTRACT FROM AUTHOR]

In this paper, we obtain three general reduction formulas to determine the orientable and nonorientable genera for complete tripartite graphs. As corollaries, we (1) reduce the determination of the orientable (nonorientable, respectively) genera of 75 percent (85 percent, respectively) of nonsymmetric (with respect to l, m, and n) Kl,m,n to that of Km,m,n, and (2) determine the orientable and nonorientable genera for several classes of complete tripartite graphs. [ABSTRACT FROM AUTHOR]

We study necessary and sufficient conditions that a nonsingular matrix A can be B-orthogonally reduced to upper Hessenberg form with small bandwidth. By this we mean the existence of a decomposition AV=VH, where H is upper Hessenberg with few nonzero bands, and the columns of V are orthogonal in an inner product generated by a hermitian positive definite matrix B. The classical example for such a decomposition is the matrix tridiagonalization performed by the hermitian Lanczos algorithm, also called the orthogonal reduction to tridiagonal form. Does there exist such a decomposition when A is nonhermitian? In this paper we completely answer this question. The related (but not equivalent) question of necessary and sufficient conditions on A for the existence of short-term recurrences for computing B-orthogonal Krylov subspace bases was completely answered by the fundamental theorem of Faber and Manteuffel [SIAM J. Numer. Anal.}, 21 (1984), pp. 352--362]. We give a detailed analysis of B-normality, the central condition in both the Faber--Manteuffel theorem and our main theorem, and show how the two theorems are related. Our approach uses only elementary linear algebra tools. We thereby provide new insights into the principles behind Krylov subspace methods, that are not provided when more sophisticated tools are employed. [ABSTRACT FROM AUTHOR]

In this paper we show how to construct the Evans function for traveling wave solutions of integral neural field equations when the firing rate function is a Heaviside. This allows a discussion of wave stability and bifurcation as a function of system parameters, including the speed and strength of synaptic coupling and the speed of axonal signals. The theory is illustrated with the construction and stability analysis of front solutions to a scalar neural field model, and a limiting case is shown to recover recent results of Zhang [Differential Integral Equations, 16 (2003), pp. 513–536]. Traveling fronts and pulses are considered in more general models possessing either a linear or piecewise constant recovery variable. We establish the stability of coexisting traveling fronts beyond a front bifurcation and consider parameter regimes that support two stable traveling fronts of different speeds. Such fronts may be connected, and depending on their relative speed the resulting region of activity can widen or contract. The conditions for the contracting case to lead to a pulse solution are established. The stability of pulses is obtained for a variety of examples, in each case confirming a previously conjectured stability result. Finally, we show how this theory may be used to describe the dynamic instability of a standing pulse that arises in a model with slow recovery. Numerical simulations show that such an instability can lead to the shedding of a pair of traveling pulses. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of constructing a reduced order system of minimal McMillan degree that satisfies a set of tangential interpolation conditions with respect to the original system under some mild conditions. The resulting reduced order transfer function appears to be generically unique and we present a simple and efficient technique to construct this interpolating reduced order system. This is a generalization of the multipoint Padé technique which is particularly suited to handle multiinput multioutput systems. [ABSTRACT FROM AUTHOR]

In this paper, we study an optimal singular stochastic control problem. By using a time transformation, this problem is shown to be equivalent to an auxiliary control problem defined as a combination of an optimal stopping problem and a classical control problem. For this auxiliary control problem, the controller must choose a stopping time (optimal stopping), and the new control variables belong to a compact set. This equivalence is obtained by showing that the (discontinuous) state process governed by a singular control is given by a time transformation of an auxiliary state process governed by a classical bounded control. it is proved that the value functions for these two problems are equal. For a general form of the cost, the existence of an optimal singular control is established under certain technical hypotheses. Moreover, the problem of approximating singular optimal control by absolutely continuous controls is discussed in the same class of admissible controls. [ABSTRACT FROM AUTHOR]

In this paper we study optimization problems with, equality and inequality constraints on a Banach space where the objective function and the binding constraints are either differentiable at the optimal solution or Lipschitz near the optimal solution. Necessary and sufficient optimality conditions and constraint qualifications in terms of the Michel-Penot subdifferential are given, and the results are applied to bilevel optimization problems. [ABSTRACT FROM AUTHOR]

Some inverse eigenvalue problems for matrices with Toeplitz-related structure are considered in this paper. In particular, the solutions of the inverse eigenvalue problems for Toeplitzplus- Hankel matrices and for Toeplitz matrices having all double eigenvalues are characterized, respectively, in close form. Being centrosymmetric itself, the Toeplitz-plus-Hankel solution can be used as an initial value in a continuation method to solve the more difficult inverse eigenvalue problem for symmetric Toeplitz matrices. Numerical testing results show a clear advantage of such an application. [ABSTRACT FROM AUTHOR]

We study second order sufficient optimality conditions (SSC) for optimal control problems with control appearing linearly. Specifically, time-optimal bang-bang controls will be investigated. In [N. P. Osmolovskii, Sov. Phys. Dokl., 33 (1988), pp. 883-885; Theory of HigherOrder Conditions in Optimal Control, Doctor of Sci. thesis, Moscow, 1988 (in Russian); Russian J. Math. Phys., 2 (1995), pp. 487-516; Russian J. Math. Phys., 5 (1997), pp. 373-388; Proceedings of the Conference "Calculus of Variations and Optimal Control," Chapman & Hall/CRC, Boca Raton, FL, 2000, pp. 198-216; A. A. Milyutin and N. P. Osmolovskii, Calculus of Variations and Optimal Control, Transl. Math. Monogr. 180, AMS, Providence, RI, 1998], SSC have been developed in terms of the positive definiteness of a quadratic form on a critical cone or subspace. No systematical numerical methods for verifying SSC are to be found in these papers. In the present paper, we study explicit representations of the critical subspace. This leads to an easily implementable test for SSC in the case of a bang-bang control with one or two switching points. In general, we show that the quadratic form can be simplified by a transformation that uses a solution to a linear matrix differential equation. Particular conditions even allow us to convert the quadratic form to perfect squares. Three numerical examples demonstrate the numerical viability of the proposed tests for SSC. [ABSTRACT FROM AUTHOR]

This paper studies first order conditions (Karush-Kuhn-Tucker conditions) for discretized optimal control problems with non smooth constraints. We present a simple condition which can be used to verify that a local optimal point satisfies the first order conditions and that a point satisfying the first order conditions is a global or local optimal solution of the optimal control problem. [ABSTRACT FROM AUTHOR]

A new fully variational approach is studied for elliptic grid generation (EGG). It is based on a general algorithm developed in a companion paper [A. L. Codd, T. A. Manteuffel, and S. F. McCormick, SIAM I Numer. Anal., 41 (2003), pp. 2197-2209] that involves using Newton's method to linearize an appropriate equivalent first-order system, first-order system least squares (FOSLS) to formulate and discretize the Newton step, and algebraic multigrid (AMG) to solve the resulting matrix equation. The approach is coupled with nested iteration to provide an accurate initial guess for finer levels using coarse-level computation. The present paper verifies the assumptions of the companion work and confirms the overall efficiency of the scheme with numerical experiments. [ABSTRACT FROM AUTHOR]

This paper contains a new convergence analysis for the Lewis and Torczon generalized pattern search (GPS) class of methods for unconstrained and linearly constrained optimization. This analysis is motivated by a desire to understand the successful behavior of the algorithm under hypotheses that are satisfied by many practical problems. Specifically, even if the objective function is discontinuous or extended-valued, the methods find a limit point with some minimizing properties. Simple examples show that the strength of the optimality conditions at a limit point depends not only on the algorithm, but also on the directions it uses and on the smoothness of the objective at the limit point in question. The contribution of this paper is to provide a simple convergence analysis that supplies detail about the relation of optimality conditions to objective smoothness properties and to the defining directions for the algorithm, and it gives previous results as corollaries. [ABSTRACT FROM AUTHOR]

The BFGS method is one of the most, famous quasi-Newton algorithms for unconstrained optimization. In 1984, Powell presented an example of a function of two variables that shows that the Polak Ribi[egrave;]re Polyak (PRP) conjugate gradient method and the BFGS quasi-Newt, on method may cycle around eight nonstationary points if each line search picks a local minimum that provides a reduction in the objective function. In this paper, a new technique of choosing parameters is introduced, and an example with only six cyclic points is provided. It is also noted through the examples that the BFGS method with Wolfe line searches need not converge for nonconvex objective functions. [ABSTRACT FROM AUTHOR]

Electromagnetic waveguides in integrated optics are propagation structures which are invariant under translation in one space direction and whose cross section is a local perturbation of a stratified medium. In this paper, we propose a new method for computing the guided modes of such devices under the weak guiding assumption. The method results from a combination of analytical techniques which take into account the unbounded and stratified character of the propagation medium so that numerical computations can be reduced to a neighborhood of the perturbation. [ABSTRACT FROM AUTHOR]

This paper is a continuation of [A. A. Borovkov and A. A. Mogulskii, Theory Probab. Appl., 43 (1998), pp. 1-12] and [A. A. Borovkov and A. A. Mogulskii, Siberian Math. J., 37 (1996), pp. 647-682]. Let S(n) =ξ(1)+…+ξ(n) be the sum of independent nondegenerate random vectors in R[SUPd] having the same distribution as a random vector ξ. It is assumed that &script;(λ) = E[SUBe],λξ is finite in a vicinity of a point λξ R[SUPd]. We obtain asymptotic representations for the probability P{S(n) ξ Δ(x)} and the renewal function H(Δ(x)) = [This equation cannot be converted into ASCII Text.], where Δ(x) is a cube in R[SUPd] with a vertex at point x and the edge length Δ. In contrast to the above-mentioned papers, the obtained results are valid, in essence, either without any additional assumptions or under very weak restrictions. [ABSTRACT FROM AUTHOR]

This paper presents several applications of (local) Fourier basis combined with corrector techniques via the superposition principle to compute solutions of boundary value problems. Our methodology is inspired by the well-known corrector technique used in asymptotic singular perturbation theory--see, for example, [W. Eckhaus, Asymptotic Analysis of Singular Perturbations, North-Holland, Amsterdam, 1979]. We build solvers for time dependent boundary value problems and/or singular perturbation problems using Fourier expansions combined to additional convenient set of time independent basis functions to enforce the boundary conditions. The algorithms are very well suited for parallel computing because they rely mainly on FFTs and basis functions given analytically or computed (in parallel) once and for all. Our method can be spectral accurate for simple geometry. We obtain in addition interesting new results for boundary value problems with complex geometry. We describe in this paper the implementation of the method and the numerical results for many linear and nonlinear problems: our goal is to test the advantages and the limits of our approach in order to motivate further theoretical investigations. Our method applied to steady one-dimensional problems is similar to the work of Israeli, Vozovoi, and Averbuch [J. Sci. Comput., 8 (1993), pp. 135–149] on domain decomposition with local Fourier basis for the Helmotz problem. However our methodology for time-dependent problem and/or two space dimensions geometry is rather different in its spirit and complements previous investigations of Israeli, Vozovoi, and Averbuch. [ABSTRACT FROM AUTHOR]

In this paper, we construct second-order central schemes for multidimensional Hamilton­Jacobi equations and we show that they are nonoscillatory in the sense of satisfying the maximum principle. Thus, these schemes provide the first examples of nonoscillatory second-order Godunov-type schemes based on global projection operators. Numerical experiments are performed; L1/L∞-errors and convergence rates are calculated. For convex Hamiltonians, numerical evidence confirms that our central schemes converge with second-order rates, when measured in the L1-norm advocated in our recent paper [Numer. Math, to appear]. The standard L∞-norm, however, fails to detect this second-order rate. [ABSTRACT FROM AUTHOR]

Minimization is a recurring theme in many mathematical disciplines ranging from pure to applied. Of particular importance is the minimization of integral functionals, which is studied within the calculus of variations. Proofs of the existence of minimizers usually rely on a fine property of the functional called weak lower semicontinuity. While early studies of lower semicontinuity go back to the beginning of the 20th century, the milestones of the modern theory were established by C. B. Morrey, Jr. [Pacific J. Math., 2 (1952), pp. 25-53] in 1952 and N. G. Meyers [Trans. Amer. Math. Soc., 119 (1965), pp. 125-149] in 1965. We recapitulate the development of this topic from these papers onwards. Special attention is paid to signed integrands and to applications in continuum mechanics of solids. In particular, we review the concept of polyconvexity and special properties of (sub-)determinants with respect to weak lower semicontinuity. In addition, we emphasize some recent progress in lower semicontinuity of functionals along sequences satisfying differential and algebraic constraints that can be used in elasticity to ensure injectivity and orientation-preservation of deformations. Finally, we outline generalizations of these results to more general first-order partial differential operators and make some suggestions for further reading. [ABSTRACT FROM AUTHOR]

We present and analyze a new space-time finite element method for the solution of neural field equations with transmission delays. The numerical treatment of these systems is rare in the literature and currently has several restrictions on the spatial domain and the functions involved, such as connectivity and delay functions. The use of a space-time discretization, with basis functions that are discontinuous in time and continuous in space (dGcG-FEM), is a natural way to deal with space-dependent delays, which is important for many neural field applications. In this paper we provide a detailed description of a space-time dGcG-FEM algorithm for neural delay equations, including an a priori error analysis. We demonstrate the application of the dGcG-FEM algorithm on several neural field models, including problems with an inhomogeneous kernel. [ABSTRACT FROM AUTHOR]

The RKFIT algorithm outlined in [M. Berljafa and S. Güttel, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 894-916] is a Krylov-based approach for solving nonlinear rational least squares problems. This paper puts RKFIT into a general framework, allowing for its extension to nondiagonal rational approximants and a family of approximants sharing a common denominator. Furthermore, we derive a strategy for the degree reduction of the approximants, as well as methods for their conversion to partial fraction form, for the efficient evaluation, and for root-finding. We also discuss similarities and differences between RKFIT and the popular vector fitting algorithm. A MATLAB implementation of RKFIT is provided, and numerical experiments, including the fitting of a multiple-input/multiple-output (MIMO) dynamical system and an optimization problem related to exponential integration, demonstrate its applicability. [ABSTRACT FROM AUTHOR]

This paper presents the mathematical conditions and the associated design methodology of an active fault diagnosis technique for continuous-time linear systems. Given a set of faults known a priori, the system is modeled by a finite family of linear time-invariant systems, accounting for one healthy and several faulty configurations. By assuming bounded disturbances and using a residual generator, an invariant set and its projection in the residual space (i.e., its limit set) are computed for each system configuration. Each limit set, related to a single system configuration, is parameterized with respect to the system input. Thanks to this design, active fault isolation can be guaranteed by the computation of a test input, either constant or periodic, such that the limit sets associated with different system configurations are separated, and the residual converges toward one limit set only. In order to alleviate the complexity of the explicit computation of the limit set, an implicit dual representation is adopted, leading to efficient procedures, based on quadratic programming, for computing the test input. The developed methodology offers a competent continuous-time solution to the optimization-based computation of the test input via Hahn-Banach duality. Simulation examples illustrate the application of the proposed active fault diagnosis methods and its efficiency in providing a solution, even in relatively large state-dimensional problems. [ABSTRACT FROM AUTHOR]

This paper is devoted to a study of the numerical solution of elliptic hemivariationalinequalities with or without convex constraints by the nite element method. For a general family of elliptic hemivariational inequalities that facilitates error analysis for numerical solutions. the solution existence and uniqueness are proved. The Galerkin approximation of the general elliptic hemivariational inequality is shown to converge. and Cea's inequality is derived for error estimation. For various elliptic hemivariational inequalities arising in contact mechanics, we provide error estimates of their numerical solutions, which are of optimal order for the linearnite element method, under appropriate solution regularity assumptions. Numerical examples are reported on using linear elements to solve sample contact problems, and the simulation results are in good agreement with the theoretically predicted linear convergence. [ABSTRACT FROM AUTHOR]

In biomedical imaging reliable segmentation of objects (e.g., from small cells up to large organs) is of fundamental importance for automated medical diagnosis. New approaches for multiscale segmentation can considerably improve performance in case of natural variations in intensity, size, and shape. This paper aims at segmenting objects of interest based on shape contours and automatically finding multiple objects with different scales. The overall strategy of this work is to combine nonlinear segmentation with scales spaces and spectral decompositions. We generalize a variational segmentation model based on total variation using Bregman distances to construct an inverse scale space. This offers the new model to be accomplished by a scale analysis approach based on a spectral decomposition of the total variation. As a result we obtain a very efficient, (nearly) parameter-free multiscale segmentation method that comes with an adaptive regularization parameter choice. To address the variety of shapes and scales present in biomedical imaging we analyze synthetic cases clarifying the role of scale and the relationship of Wulff shapes and eigenfunctions. To underline the potential of our approach and to show its wide applicability we address three different experimental biomedical applications. In particular, we demonstrate the added benefit for identifying and classifying circulating tumor cells and present interesting results for network analysis in retina imaging. Due to the nature of underlying nonlinear diffusion, the mathematical concepts in this work offer promising extensions to nonlocal classification problems. [ABSTRACT FROM AUTHOR]

This paper provides a mathematical analysis of ultrafast ultrasound imaging. This newly emerging modality for biomedical imaging uses plane waves instead of focused waves in order to achieve very high frame rates. We derive the point spread function of the system in the Born approximation for wave propagation and study its properties. We consider dynamic data for blood flow imaging, and introduce a suitable random model for blood cells. We show that a singular value decomposition method can successfully remove the clutter signal by using the different spatial coherences of tissue and blood signals, thereby providing high-resolution images of blood vessels, even in cases when the clutter and blood speeds are comparab le in magnitude. Several numerical simulations are presented to illustrate and validate the approach. [ABSTRACT FROM AUTHOR]

This paper is devoted to a seawater intrusion model in free aquifers, including rock and fluid compressibility effects. This original model is based on the superimposition of a phase-field model on sharp front tracking. It leads to the analysis of a two-dimensional strongly coupled system of PDEs of parabolic type describing the evolution of the depth s of the two free surfaces. The main difficulty is dealing with the strong nonlinearity occurring in the time derivative due to the fluid storage coefficient. This point yields to the manipulation of very weak solutions--solutions of an alternative variational formulation focusing on the structural weakness of the problem. [ABSTRACT FROM AUTHOR]

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we introduce an overlapping mortar finite element method for solving two-dimensional elliptic problems discretized on overlapping nonmatching grids. We prove an optimal error bound and estimate the condition numbers of certain overlapping Schwarz preconditioned systems for the two-subdomain case. We show that the error bound is independent of the size of the overlap and the ratio of the mesh parameters. In the second part, we introduce three additive Schwarz preconditioned conjugate gradient algorithms based on the trivial and harmonic extensions. We provide estimates for the spectral bounds on the condition numbers of the preconditioned operators. We show that although the error bound is independent of the size of the overlap, the condition number does depend on it. Numerical examples are presented to support our theory. [ABSTRACT FROM AUTHOR]

We present in this paper numerical simulations of reactive flows interacting with shock waves. We argue that spectral methods are suitable for these problems and review the recent developments in spectral methods that have made them a powerful numerical tool appropriate for long-term integrations of complicated flows, even in the presence of shock waves. A spectral code is described in detail, and the theory that leads to each of its components is explained. Results of interactions of hydrogen jets with shock waves are presented and analyzed, and comparisons with ENO finite difference schemes are carried out. [ABSTRACT FROM AUTHOR]

This paper gives a quantitative result that if A is a substochastic matrix and has r eigenvalues which are sufficiently close to 1, then A has r disjoint principal submatrices which are nearly stochastic. [ABSTRACT FROM AUTHOR]

Families of matrices smoothly depending on a vector of parameters are considered. Arnold [Russian Math. Surveys, 26 (1971), pp. 29–43] and Galin [Uspekhi Mat. Nauk, 27 (1972),pp. 241–242] have found and listed normal forms of families of complex and real matrices (miniversal deformations), to which any family of matrices can be transformed in the vicinity of a point in the parameter space by a change of basis, smoothly dependent on a vector of parameters, and by a smooth change of parameters. In this paper a constructive method of determining functions describing a change of basis and a change of parameters, transforming an arbitrary family to the miniversal deformation, is suggested. Derivatives of these functions with respect to parameters are determined from a recurrent procedure using derivatives of the functions of lower orders and derivatives of the family of matrices. Then the functions are found as Taylor series. Examples are given. The suggested method allows using efficiently miniversal deformations for investigation of different properties of matrix families. This is shown in the paper where tangent cones (linear approximations) to the stability domain at the singular boundary points are found. [ABSTRACT FROM AUTHOR]

In the first part of this paper, the mathematical analysis is presented in detail for the single-phase, miscible displacement of one fluid by another in a porous medium. It is shown that initial boundary value problems with various boundary conditions for this miscible displacement possess a weak solution under physically reasonable hypotheses on the data. In the second part of this paper, it is proven how the analysis can be extended to two-phase fluid flow and transport equations in a porous medium. The flow equations are written in a fractional flow formulation so that a degenerate elliptic-parabolic partial differential system is produced for a global pressure and a saturation. This degenerate system is coupled to a parabolic transport equation which models the concentration of one of the fluids. The analysis here does not utilize any regularized problem; a weak solution is obtained as a limit of solutions to discrete time problems. [ABSTRACT FROM AUTHOR]