Search

This paper continues the convergence analysis in [M. Giles and S. Ulbrich, SIAM J. Numer. Anal., 48 (2010), pp. 882-904] of discrete approximations to the linearized and adjoint equations arising from an unsteady one-dimensional hyperbolic equation with a convex flux function. We consider a simple modified Lax-Friedrichs discretization on a uniform grid, and a key point is that the numerical smoothing increases the number of points across the nonlinear discontinuity as the grid is refined. It is proved that there is convergence in the discrete approximation of linearized output functionals even for Dirac initial perturbations and pointwise convergence almost everywhere for the solution of the adjoint discrete equations. In particular, the adjoint approximation converges to the correct uniform value in the region in which characteristics propagate into the discontinuity. Moreover, it is shown that the results of [M. Giles and S. Ulbrich, SIAM J. Numer. Anal., 48 (2010), pp. 882-904] and the present paper hold also for quite general nonlinear initial data which contain multiple shocks and for which shocks form at a later time and/or merge. [ABSTRACT FROM AUTHOR]

The distribution of the eigenvalues of a Hermitian matrix (or of a Hermitian matrix pencil) reveals important features of the underlying problem, whether a Hamiltonian system in physics or a social network in behavioral sciences. However, computing all the eigenvalues explicitly is prohibitively expensive for real-world applications. This paper presents two types of methods to efficiently estimate the spectral density of a matrix pencil (A,B) where both A and B are sparse Hermitian and B is positive definite. The methods are targeted at the situation when the matrix B scaled by its diagonal is very well conditioned, as is the case when the problem arises from some finite element discretizations of certain partial differential equations. The first method is an adaptation of the kernel polynomial method (KPM) and the second is based on Gaussian quadrature by the Lanczos procedure. By employing Chebyshev polynomial approximation techniques, we can avoid direct factorizations in both methods, making the resulting algorithms suitable for large matrices. Under some assumptions, we prove bounds that suggest that the Lanczos method converges twice as fast as the KPM method. Numerical examples further indicate that the Lanczos method can provide more accurate spectral densities when the eigenvalue distribution is highly nonuniform. As an application, we show how to use the computed spectral density to partition the spectrum into intervals that contain roughly the same number of eigenvalues. This procedure, which makes it possible to compute the spectrum by parts, is a key ingredient in the new breed of eigensolvers that exploit "spectrum slicing." [ABSTRACT FROM AUTHOR]

As is well known, the smallest possible ratio between the spectral norm and the Frobenius norm of an m x n matrix with m x n is 1= p m and is (up to scalar scaling) attained only by matrices having pairwise orthonormal rows. In the present paper, the smallest possible ratio between spectral and Frobenius norms of n1 find tensors of order d, also called the best rank-one approximation ratio in the literature, is investigated. The exact value is not known for most configurations of n1 nd. Using a natural definition of orthogonal tensors over the real field (resp., unitary tensors over the complex field), it is shown that the obvious lower bound 1= p n1 nd1 is attained if and only if a tensor is orthogonal (resp., unitary) up to scaling. Whether or not orthogonal or unitary tensors exist depends on the dimensions n1; : : : ; nd and the field. A connection between the (non)existence of real orthogonal tensors of order three and the classical Hurwitz problem on composition algebras can be established: existence of orthogonal tensors of size ` x m x n is equivalent to the admissibility of the triple [`; m; n] to the Hurwitz problem. Some implications for higher-order tensors are then given. For instance, real orthogonal n n tensors of order d x 3 do exist, but only when n = 1; 2; 4; 8. In the complex case, the situation is more drastic: unitary tensors of size ` x m x n with ` x m x n exist only when `m x n. Finally, some numerical illustrations for spectral norm computation are presented. [ABSTRACT FROM AUTHOR]

In this paper we present a new method to solve differential inclusions in Hilbert spaces. This method is a Galerkin-like method where we approach the original problem by project- ing the state into a n-dimensional Hilbert space but not the velocity. We prove that the approached problem always has a solution and that, under some compactness conditions, the approached prob- lems have a subsequence which converges strongly pointwisely to a solution of the original differential inclusion. We apply this method to the generalized perturbed sweeping process governed by nonregu- lar sets (equi-uniformly subsmooth or positively α-far). This differential inclusion includes Moreau's sweeping process, the state-dependent sweeping process, and second-order sweeping process for which we give very general existence results. [ABSTRACT FROM AUTHOR]

This paper analyzes the convergence of discrete approximations to the linearized equations arising from an unsteady one-dimensional hyperbolic equation with a convex flux function. A simple modified Lax-Friedrichs discretization is used on a uniform grid, and a key point is that the numerical smoothing increases the number of points across the nonlinear discontinuity as the grid is refined. It is proved that this gives pointwise convergence almost everywhere for the solution to the linearized discrete equations with smooth initial data, and also convergence in the discrete approximation of linearized output functionals. In Part 2 [M. Giles and S. Ulbrich, SIAM J. Numer. Anal., 48 (2010), pp. 905-921] we extend the results to Dirac initial data for the linearized equation and will prove the pointwise convergence almost everywhere for the solution of the adjoint discrete equations. In addition, we present numerical results illustrating the asymptotic behavior which is analyzed. [ABSTRACT FROM AUTHOR]

In this paper compressible, stationary Navier--Stokes equations are considered. A framework for analysis of such equations is established. In particular, the well-posedness for inhomogeneous boundary value problems of elliptic-hyperbolic type is shown. Analysis is performed for small perturbations of the so-called approximate solutions that take form (1.12). The approximate solutions are determined from Stokes problem (1.11). The small perturbations are given by solutions to (1.13). The uniqueness of solutions for problem (1.13) is proved, and, in addition, the differentiability of solutions with respect to the coefficients of differential operators is shown. The results on the well-posedness of nonlinear problems are interesting on their own and are used to obtain the shape differentiability of the drag functional for incompressible Navier--Stokes equations. The shape gradient of the drag functional is derived in the classical and useful for computations form; an appropriate adjoint state is introduced to this end. The material derivatives of solutions to the Navier--Stokes equations are given by smooth functions; however, the shape differentiability is shown in a weak norm. The method of analysis proposed in this paper is general and can be used to establish the well-posedness for distributed and boundary control problems as well as for inverse problems in the case of the state equations in the form of compressible Navier--Stokes equations. The differentiability of solutions to the Navier--Stokes equations with respect to the data leads to the first order necessary conditions for a broad class of optimization problems. [ABSTRACT FROM AUTHOR]

This paper provides a multiscale analytical study of steady incompressible turbulent flow through a channel of either Couette or pressure-driven Poiseuille type. Mathematically, the paper's two most novel features are that (1) the analysis begins with an underdetermined singular perturbation problem, namely the Reynolds averaged mean momentum balance equation, and (2) it leads to the existence of an infinite number of length scales. (These two features are probably linked, but the linkage will not be pursued.) The paper develops a credible assumption of a mathematical nature which, when added to the initial underdetermined problem, results in a knowledge of almost the complete layer (scaling) structure of the mean velocity and Reynolds stress profiles. This structure in turn provides a lot of other important information about those profiles. The possibility of almost-logarithmic sections of the mean velocity profile is given special attention. The sense in which the length scales are asymptotically proportional to the distance from the wall is determined. Most traditional theoretical analyses of these wall-bounded flows are based ultimately on either the classical overlap hypothesis, mixing length concepts, or similarity arguments. The present paper avoids those approaches and their attendant assumptions. Empirical data are also not used, except that the Reynolds stress takes on positive values. Instead, reasonable criteria are proposed for recognizing scaling layers in the flow, and they are then used to determine the scaling structure and much more information. [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]

The computational singular perturbation (CSP) method of Lam and Goussis is an iterative method to reduce the dimensionality of systems of ordinary differential equations with multiple time scales. In [J. Nonlinear Sci., 14 (2004), pp. 59-91], the authors of this paper showed that each iteration of the CSP algorithm improves the approximation of the slow manifold by one order. In this paper, it is shown that the CSP method simultaneously approximates the tangent spaces to the fast fibers along which solutions relax to the slow manifold. Again, each iteration adds one order of accuracy. In some studies, the output of the CSP algorithm is postprocessed by linearly projecting initial data onto the slow manifold along these approximate tangent spaces. These projections, in turn, also become successively more accurate. [ABSTRACT FROM AUTHOR]

In this paper, we consider a singularly perturbed control system involving differential inclusions in Banach spaces with slow and fast solutions. Using the averaging approach, we obtain sufficient conditions for the Hausdorff convergence of the set of slow solutions in the supremum norm. We present applications of the theorem to prove convergence of the fast solutions in terms of invariant measures and convergence of equi-Lipschitz solutions. [ABSTRACT FROM AUTHOR]

In this paper we study the stability of integrable Hamiltonian systems under small perturbations, proving a weak form of the KAM/Nekhoroshev theory for viscosity solutions of Hamilton Jacobi equations. The main advantage of our approach is that, only a finite number of terms in an asymptotic expansion are needed in order to obtain uniform control. Therefore there are no convergence issues involved. An application of these results is to show thai Diophantine invariant tori and Aubry-Mather sets are stable under small perturbations. [ABSTRACT FROM AUTHOR]

In this paper, we study the portfolio optimization problem with general utility functions and when the return and volatility of the underlying asset are slowly varying. An asymptotic optimal strategy is provided within a specific class of admissible controls under this problem setup. Specifically, we establish a rigorous first order approximation of the value function associated to a fixed zeroth order suboptimal trading strategy, which is derived heuristically in [J.-P. Fouque, R. Sircar, and T. Zariphopoulou, Math. Finance, 2016]. Then, we show that this zeroth order suboptimal strategy is asymptotically optimal in a specific family of admissible trading strategies. Finally, we show that our assumptions are satisfied by a particular fully solvable model. [ABSTRACT FROM AUTHOR]

Many idealized problems in signal processing, machine learning, and statistics can be reduced to the problem of finding the symmetric canonical decomposition of an underlying symmetric and orthogonally decomposable (SOD) tensor. Drawing inspiration from the matrix case, the successive rank-one approximation (SROA) scheme has been proposed and shown to yield this tensor decomposition exactly, and a plethora of numerical methods have thus been developed for the tensor rank-one approximation problem. In practice, however, the inevitable errors (say) from estimation, computation, and modeling necessitate that the input tensor can only be assumed to be a nearly SOD tensor--i.e., a symmetric tensor slightly perturbed from the underlying SOD tensor. This paper shows that even in the presence of perturbation, SROA can still robustly recover the symmetric canonical decomposition of the underlying tensor. It is shown that when the perturbation error is small enough, the approximation errors do not accumulate with the iteration number. Numerical results are presented to support the theoretical findings. [ABSTRACT FROM AUTHOR]

The uniqueness of the best rank-one approximation of a tensor under the Frobenius norm is a basic and important studying subject in the tensor theory. By introducing the quasisingular value of a tensor, we present a new sufficient condition under which the best rank-one approximation of a nonzero tensor X ∈ ℝd¹×d2×d3 is unique and obtain that the set consisting of all tensors satisfying the sufficient condition is an open and dense set in ℝd1×d2×d3 . In addition, we present a necessary and sufficient condition under which the best rank-one approximation of the sum tensor X = X+E under some assumption on the tensor X ∈ ℝd1×d2×d3 is equal to the best rank-one approximation of X. Meanwhile, a numerical algorithm is proposed for computing the quasi-singular value of a tensor. Finally, several testing examples are presented to illustrate the feasibility of the computational process and the correctness of the theoretical results obtained in the paper. [ABSTRACT FROM AUTHOR]

In this paper we consider resolution estimates for a linearized inverse conductivity problem with partial data. Our purpose is to precisely describe the effect of the limited-view aspect on the resolving power of the measurements in the presence of measurement noise. We first show that in the shallow probing regime, where the inclusion is close to the boundary of the background medium, we can resolve for any signal-to-noise ratio a sufficiently shallow perimeter perturbation of a conductivity inclusion on the overlap of the source and receiver apertures. Then we provide explicit formulas for the modes that can be resolved and the resolution measure for a given signal-to-noise ratio in the deep probing regime, where the radius of the inclusion is small. [ABSTRACT FROM AUTHOR]

A quasiconvex function is a function which has convex sublevel sets. This paper studies robustly quasiconvex functions, that is, quasiconvex functions which remain quasiconvex under small linear perturbations. Relations to pseudoconvexity and other generalized convexity concepts and necessary and sufficient first-order conditions for robust quasiconvexity of smooth functions are presented. Convex-analytic properties and convexification of robustly quasiconvex functions are studied. Supporting robustly quasiconvex functions by simpler functions is discussed, with duality theory as motivation. Through the use of a second-order condition for robust quasiconvexity of nonsmooth functions, nontrivial examples of such functions are given. [ABSTRACT FROM AUTHOR]

This paper was motivated by the need to establish some new characterizations of the metric regularity of set-valued mappings. Through these new characterizations it was possible to investigate the global/local perturbation stability of the metric regularity and to extend a result by Ioffe [Set-Valued Anal., 9 (2001), pp. 101-109] on the perturbation stability of the global metric regularity when the image space is not necessarily complete. It was also possible to give a characterization of the local metric regularity and to derive a local version of the perturbation stability of the metric regularity. In this work we also describe an application of this perturbation stability and give a simple proof of a result on the error bound of 2-regular mappings established by Izmailov and Solodov [Math. Program., 89 (2001), pp. 413-435] and generalized by He and Sun [Math. Oper. Res., 30 (2005), pp. 701-717]. [ABSTRACT FROM AUTHOR]

In this paper we present a rigorous derivation of the effective model for enhanced diffusion through a narrow and long 2D pore. The analysis uses a singular perturbation technique. The starting point is a local pore scale model describing the transport by convection and diffusion of a reactive solute. The solute particles undergo a first-order reaction at the pore surface. The transport and reaction parameters are such that we have large, dominant Peclet and Damkohler numbers with respect to the ratio of characteristic transversal and longitudinal lengths (the small parameter ε). We give a rigorous mathematical justification of the effective behavior for small ε. Error estimates are presented in the energy norm as well as in L∞ and L¹ norms of the space variable. They guarantee the validity of the upscaled model. As a special case, we recover the well-known Taylor dispersion formula. [ABSTRACT FROM AUTHOR]

This paper investigates both the convexity and elasticity of the growth rate of size-classsified population models. For an irreducible population projection matrix, we discuss the convexity properties of its Perron eigenvalue under perturbation of the vital rates, extending work of Kirkland and Neumann on Leslie matrices. We also provide nonnegative attainable lower bounds on the derivatives of the elasticity of the Perron eigenvalue under perturbation of the vital rates, sharpening, in the context of population projection matrices, the main result of Kirkland, Neumann, Ormes, and Xu. [ABSTRACT FROM AUTHOR]

Flow of a two component fluid in a capillary is studied analytically and numerically to obtain an understanding of the basic parameters and their effect on the advection-diffusion flow process. One fluid (the solvent) is Newtonian, and the other is a dilute polymer plug (the solution) introduced into the flowing solvent. The polymer plug is modeled as a Maxwell fluid. The ultimate goal is characterization of industrially manufactured polymers in real time, at-line. Experimentally, the evolution of a dilute plug introduced into a fully developed capillary solvent flow is tracked by observing the pressure drop downstream. The volumetric flow rate is held constant. While the pressure plateau has been identified with the intrinsic viscosity of the polymer, in this work, we relate the leading edge behavior of the plug/plateau to the elasticity and diffusivity of the polymer. The combination of these three parameters should unambiguously characterize the polymer chains in solution. In this paper, asymptotic expansions of the equations governing the flow and advection-diffusion are carried out in terms of a dilution parameter ∊(&Le; 1). The resulting initial-boundary value problems are solved numerically in order to characterize the effect of polymer properties on the observed pressure profile. [ABSTRACT FROM AUTHOR]

At each iteration step for solving mathematical programming and constrained optimization problems by using interior-point methods, one often needs to solve the weighted least squares (WLS) problem minx∈Rn ¦¦W½(Ax - b)¦¦, or the weighted and constrained least squares (WLSE) problem minx∈Rn ¦¦W½(Kx - g)¦¦ subject to Lx = h, where W = diag(w1,…,wl) > 0 in which some wi → +∝ and some wi → 0. In this paper we will derive upper perturbation bounds of weighted projections associated with the WLS and WLSE problems when W ranges over the set D of positive diagonal matrices. We then apply these bounds to deduce upper perturbation bounds of solutions of WLS and WLSE problems when W ranges over D. We also extend the estimates to the cases when W ranges over a subset of real symmetric positive semidefinite matrices. [ABSTRACT FROM AUTHOR]

In this paper we consider the problems of maximizing the spectral radii of (i) A + X and (ii) A + D, where X is a real n × n matrix whose Frobenius norm is restricted to be 1 and where D is as X but is further constrained to be a diagonal matrix. For both problems the maximums occur at nonnegative X and D, and we use tools of nonnegative matrices, most notably due to Levinger and Fiedler, as well as the Kuhn­Tucker criterion for constrained optimization, to find upper and lower bounds on the maximums, and, when A is additionally assumed to be irreducible, to characterize cases of equalities in these bounds. In the case of the first problem, when A is irreducible, we characterize a matrix which gives the global maximum. A matrix which yields a global maximum to the second problem is more complicated to characterize as, depending on A, the problem admits local maximums within the nonnegative diagonal matrices of Frobenius norm. [ABSTRACT FROM AUTHOR]

In this paper, we study the mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with a parametric generalized equation involving the regular normal cone. Compared with the usual way of formulating MPEC through a KKT condition, this formulation has the advantage that it does not involve extra multipliers as new variables, and it usually requires weaker assumptions on the problem data. Using the so-called first-order sufficient condition for metric subregularity, we derive verifiable sufficient conditions for the metric subregularity of the involved set-valued mapping, or equivalently the calmness of the perturbed generalized equation mapping. [ABSTRACT FROM AUTHOR]

Normalized cut is a widely used measure of separation between clusters in a graph. In this paper we provide a novel probabilistic perspective on this measure. We show that for a partition of a graph into two weakly connected sets, V = A ⊌ B, the multiway normalized cut is approximately MN cut ≈ 1/τA→B + 1/τB→A, where τA→B is the unidirectional characteristic exit time of a random walk from subset A to subset B. Using matrix perturbation theory, we show that this approximation is exact to first order in the connection strength between the two subsets A and B, and we derive an explicit bound for the approximation error. Our result implies that for a Markov chain composed of a reversible subset A that is weakly connected to an absorbing subset B, the easy-to-compute normalized cut measure is a reliable proxy for the chain's spectral gap. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the Cauchy problem for the rotating shallow water equations with physical viscosity. We obtain the local existence of classical solutions without assuming the initial height is small or a small perturbation of some constant status. Moreover, the initial vacuum is allowed and the spatial measure of the set of vacuum can be arbitrarily large. In particular, the initial height can even have compact support; in this case, a blow-up example is given. [ABSTRACT FROM AUTHOR]

In this paper we analyze wave propagation in three-dimensional random media. We consider a source with limited spatial and temporal support that generates spherically diverging waves. The waves propagate in a random medium whose fluctuations have small amplitude and correlation radius larger than the typical wavelength but smaller than the propagation distance. In a regime of separation of scales we prove that the wave is modified in two ways by the interaction with the random medium: first, its time profile is affected by a deterministic diffusive and dispersive convolution; second, the wave fronts are affected by random perturbations that can be described in terms of a Gaussian process whose amplitude is of the order of the wavelength and whose correlation radius is of the order of the correlation radius of the medium. Both effects depend on the two-point statistics of the random medium. [ABSTRACT FROM AUTHOR]

Regularization is used in order to obtain a reasonable estimate of the solution to an ill-posed inverse problem. One common form of regularization is to use a filter to reduce the influence of components corresponding to small singular values, perhaps using a Tikhonov least squares formulation. In this work, we break the problem into subproblems with narrower bands of singular values using spectrally defined windows, and we regularize each subproblem individually. We show how to use standard parameter-choice methods, such as the discrepancy principle and generalized cross-validation, in a windowed regularization framework. A perturbation analysis gives sensitivity estimates. We demonstrate the effectiveness of our algorithms on deblurring images and on the backward heat equation. [ABSTRACT FROM AUTHOR]

A collection of typical examples shows the exotic behavior of numerical methods when applied to singular perturbation problems. While standard meshes are used in the first six examples, even on layer-adapted meshes several surprising phenomena are shown to occur. [ABSTRACT FROM AUTHOR]

In this work, we address the convergence of a finite element approximation of the minimizer of the Freidlin-Wentzell (F-W) action functional for nongradient dynamical systems perturbed by small noise. The F-W theory of large deviations is a rigorous mathematical tool to study small-noise-induced transitions in a dynamical system. The central task in the application of F-W theory of large deviations is to seek the minimizer and minimum of the F-W action functional. We discretize the F-W action functional using linear finite elements and establish the convergence of the approximation through Γ-convergence. [ABSTRACT FROM AUTHOR]

We consider a class of reaction-diffusion equations with a stochastic perturbation on the boundary. We show that in the limit of fast diffusion, one can rigorously approximate solutions of the system of PDEs with stochastic Neumann boundary conditions by the solution of a suitable stochastic/deterministic differential equation for the average concentration that involves reactions only. An interesting effect occurs in case the noise on the boundary does not change the averaging concentration but is sufficiently large. Here due to the presence of noise surprising new effective reaction terms may appear in the limit. To study this phenomenon we focus on systems with polynomial nonlinearities and illustrate it with simplified, somewhat artificial, examples, namely, a two-dimensional nonlinear heat equation and the cubic autocatalytic reaction between two chemicals. [ABSTRACT FROM AUTHOR]

We present a superfast divide-and-conquer method for finding all the eigenvalues as well as all the eigenvectors (in a structured form) of a class of symmetric matrices with off-diagonal ranks or numerical ranks bounded by r, as well as the approximation accuracy of the eigenvalues due to off-diagonal compression. More specifically, the complexity is O(r²n log n) + O(rn log² n), where n is the order of the matrix. Such matrices are often encountered in practical computations with banded matrices, Toeplitz matrices (in Fourier space), and certain discretized problems. They can be represented or approximated by hierarchically semiseparable (HSS) matrices. We show how to preserve the HSS structure throughout the dividing process that involves recursive updates and how to quickly perform stable eigendecompositions of the structured forms. Various other numerical issues are discussed, such as computation reuse and deation. The structure of the eigenvector matrix is also shown. We further analyze the structured perturbation, i.e., how compression of the off-diagonal blocks impacts the accuracy of the eigenvalues. They show that rank structured methods can serve as an effective and efficient tool for approximate eigenvalue solutions with controllable accuracy. The algorithm and analysis are very useful for finding the eigendecomposition of matrices arising from some important applications and can be modified to find SVDs of nonsymmetric matrices. The efficiency and accuracy are illustrated in terms of Toeplitz and discretized matrices. Our method requires significantly fewer operations than a recent structured eigensolver, by nearly an order of magnitude. [ABSTRACT FROM AUTHOR]

The method of multiple timescales is widely used in engineering and mathematical physics. In this article we draw attention to the literature on the comparison of various perturbation methods. We indicate where we can obtain an advantage from the concept of timescales, and we present examples where the anticipation of timescales makes sense and cases where, because of resonances or bifurcations, the analysis is less straightforward. In a number of problems second order approximations are essential to understand the phenomena. We will conclude from these examples that the anticipation of timescales as in the multiple timescales method may give misleading results; methods that do not anticipate timescales a priori such as averaging and renormalization should be used in research problems. [ABSTRACT FROM AUTHOR]

We propose splitting methods for the computation of the exponential of perturbed matrices which can be written as the sum A = D+εB of a sparse and efficiently exponentiable matrix D with sparse exponential eD and a dense matrix εB which is of small norm in comparison with D. The predominant algorithm is based on scaling the large matrix A by a small number 2−s, which is then exponentiated by efficient Pad'e or Taylor methods and finally squared in order to obtain an approximation for the full exponential. In this setting, the main portion of the computational cost arises from dense-matrix multiplications and we present a modified squaring which takes advantage of the smallness of the perturbed matrix B in order to reduce the number of squarings necessary. Theoretical results on local error and error propagation for splitting methods are complemented with numerical experiments and show a clear improvement over existing methods when medium precision is sought. [ABSTRACT FROM AUTHOR]

Results on stability of both local and global metric regularity under set-valued perturbations are presented. As an application, we study (super)linear convergence of a Newton-type iterative process for solving generalized equations. We investigate several iterative schemes such as the inexact Newton's method, the nonsmooth Newton's method for semismooth functions, the inexact proximal point algorithm, etc. Moreover, we also cover a forward-backward splitting algorithm for finding a zero of the sum of two multivalued (not necessarily monotone) operators. Finally, a globalization of the Newton's method is discussed. [ABSTRACT FROM AUTHOR]

A combinatorial simplex algorithm is an instance of the simplex method in which the pivoting depends on certain combinatorial data only. We show that any algorithm of this kind admits a tropical analogue which can be used to solve mean payoff games. Moreover, any combinatorial simplex algorithm with a strongly polynomial complexity (the existence of such an algorithm is open) would provide in this way a strongly polynomial algorithm solving mean payoff games. Mean payoff games are known to be in NP ⋂ co-NP; whether they can be solved in polynomial time is an open problem. Our algorithm relies on a tropical implementation of the simplex method over a real closed field of Hahn series. One of the key ingredients is a new scheme for symbolic perturbation which allows us to lift an arbitrary mean payoff game instance into a nondegenerate linear program over Hahn series. [ABSTRACT FROM AUTHOR]

We propose an exponential wave integrator sine pseudospectral (EWI-SP) method for the nonlinear Schrödinger equation (NLS) with wave operator (NLSW), and carry out rigorous error analysis. The NLSW is NLS perturbed by the wave operator with strength described by a dimensionless parameter ε ∈ (0, 1]. As ε → 0+, the NLSW converges to the NLS and for the small perturbation, i.e., 0 < ε ≪ 1, the solution of the NLSW differs from that of the NLS with a function oscillating in time with O(ε²) wavelength at O(ε²) and O(ε4) amplitudes for ill-prepared and well-prepared initial data, respectively. This rapid oscillation in time brings significant difficulties in designing and analyzing numerical methods with error bounds uniformly in ε. In this work, we show that the proposed EWI-SP possesses the optimal uniform error bounds at O(τ²) and O(τ) in τ (time step) for well-prepared initial data and ill-prepared initial data, respectively, and spectral accuracy in h (mesh size) for both cases, in the L² and semi-H¹ norms. This result significantly improves the error bounds of the finite difference methods for the NLSW. Our approach involves a careful study of the error propagation, cut-off of the nonlinearity, and the energy method. Numerical examples are provided to confirm our theoretical analysis. [ABSTRACT FROM AUTHOR]

This work is concerned with a singularly perturbed stochastic nonlinear wave equation with a random dynamical boundary condition. A splitting is used to establish the approximating equation of the system for a sufficiently small singular perturbation parameter. The approximating equation is a stochastic parabolic equation when the power exponent of the singular perturbation parameter is in [1/2, 1) but is a deterministic wave equation when the power exponent is in (1,+∞). Moreover, if the power exponent of a singular perturbation parameter is bigger than or equal to 1/2, the same limiting equation of the system is derived in the sense of distribution, as the perturbation parameter tends to zero. This limiting equation is a deterministic parabolic equation. [ABSTRACT FROM AUTHOR]

How does GMRES convergence change when the coefficient matrix is perturbed? Using spectral perturbation theory and resolvent estimates, we develop simple, general bounds that quantify the lag in convergence such a perturbation can induce. This analysis is particularly relevant to preconditioned systems, where an ideal preconditioner is only approximately applied in practical computations. To illustrate the utility of this approach, we combine our analysis with Stewart's invariant subspace perturbation theory to develop rigorous bounds on the performance of approximate deflation preconditioning using Ritz vectors. [ABSTRACT FROM AUTHOR]

This work is motivated by the desire to develop a method that allows for easy and accurate calculation of complex resonances of a one-dimensional Schröodinger's equation whose potential is a low-energy well surrounded by a thick barrier. The resonance is calculated as a perturbation of the bound state associated with a barrier of infinite thickness. We show that the corrector to the bound-state energy is exponentially small in the barrier thickness. A simple computational strategy that exploits this smallness is devised and numerically verified to be very accurate. We also provide a study of high-frequency resonances and show how they can be approximated. Numerical examples are given to illustrate the main ideas in this work. [ABSTRACT FROM AUTHOR]

This work addresses input-to-state stability (ISS) for hybrid dynamical systems, which combine continuous-time dynamics on a flow set and discrete-time dynamics on a jump set. The main result entails equivalent characterizations of ISS when the right-hand side of the differential equation for the continuous-time dynamics is locally Lipschitz but the set of admissible derivative values, generated by considering all possible input values, is not necessarily convex. Under some mild assumptions, we show that existence of an ISS-Lyapunov function is equivalent to various types of robust ISS for these hybrid systems. As an application, we demonstrate how a hybrid system framework can be used to study some stability properties for continuous-time systems; in particular, we use the derived equivalent characterization results of ISS for hybrid systems to recover and generalize Lyapunov and asymptotic characterizations of input-output-to-state stability for continuous-time systems. [ABSTRACT FROM AUTHOR]

We study the propagation, observation, and control properties of the quadratic P2-classical finite element semidiscretization of the one-dimensional wave equation on a bounded interval. A careful Fourier analysis of the discrete wave dynamics reveals two different branches in the spectrum: the acoustic one, of physical nature, and the optic one, related to the perturbations that this second-order finite element approximation introduces with respect to the P1 one. On both modes there are high frequencies with vanishing group velocity as the mesh size tends to zero. This shows that the classical property of continuous waves of being observable from the boundary fails to be uniform for this discretization scheme. As a consequence of this, the controls of the discrete waves may blow up as the mesh size tends to zero. To remedy these high-frequency pathologies, we design filtering mechanisms based on the Fourier truncation method or on a bi-grid algorithm, for which one can recover the uniformity of the observability constant in a finite time and, consequently, the possibility to control with uniformly bounded L²-controls appropriate projections of the solutions. This also allow us to show that, by relaxing the control requirement, the controls are uniformly bounded and converge to the continuous ones as the mesh size tends to zero. [ABSTRACT FROM AUTHOR]

The article offers information on a study conducted by Sebastian Franz and Hans-Görg Roos about the behavior of numerical schemes when solving singularly perturbed problems. Singularly perturbed problems are a core topic in major graduate applied mathematics program since they are common in many application domains like circuit design and fluid dynamics. A discussion of more advanced layer-adaptive mesh schemes is also presented.

We analyze the one-dimensional velocity-jump process, where a particle moves at a constant velocity determined by the particle's internal velocity state that randomly fluctuates with exponentially distributed waiting times. The transition rates between the internal velocity states depend on the location of the particle, leading to a spatially inhomogeneous random process. An asymptotic analysis is applied to obtain the stationary distribution of the random process. The result is compared to the often-used quasi-steady-state diffusion approximation, and it is found that the diffusion approximation breaks down in the presence of a turning point, where the average velocity of the particle changes sign. We extend the analysis to approximate the first-exit time density for the particle to escape the confining effect of the turning point, and we find the diffusion approximation also fails to accurately describe the long-time behavior of the process. The accuracy of the two approximations is explored for a simple model of molecular-motor transport by comparing results to Monte Carlo simulations. [ABSTRACT FROM AUTHOR]

We give a rigorous proof of the approximability of the so-called Helfrich's functional via diffuse interfaces under a constraint on the ratio between the bending rigidity and the Gaussian rigidity. [ABSTRACT FROM AUTHOR]

The article presents a study related to the optimal control problem of the heat equation in the presence of a state constraint. It discusses a technique of alternative optimality systems where both the control and multiplier are continuous in time, in the area of optimal control of partial differential equations. It informs that an expansion of the value function and of approximate solutions can be calculated for a directional perturbation of the right-hand side of the state equation.

For electrical impedance tomography (EIT), the linearized reconstruction method using the Fréchet derivative of the Neumann-to-Dirichlet map with respect to the conductivity has been widely used in the last three decades. However, few rigorous mathematical results are known regarding the errors caused by the linear approximation, hi this work we prove that linearizing the inverse problem of EIT does not lead to shape errors for piecewise-analytic conductivities. If a solution of the linearized equations exists, then it has the same outer support as the true conductivity change, no matter how large the latter is. Under an additional definiteness condition we also show how to approximately solve the linearized equation so that the outer support converges toward the right one. Our convergence result is global and also applies for approximations by noisy finite- dimensional data. Furthermore, we obtain bounds on how well the linear reconstructions and the true conductivity difference agree on the boundary of the outer support. [ABSTRACT FROM AUTHOR]

We consider the convergence of a volume corrected characteristics-mixed method (VCCMM) for advection-diffusion systems. It is known that, without volume correction, the method is first order convergent, provided there is a nondegenerate diffusion term. We consider the advective part of the system and give some properties of the weak solution. With these properties we prove that the volume corrected method, with no diffusion term, gives a lower order L¹-convergence rate of O(h/√Δt + h + (Δt)r), where r is related to the accuracy of the characteristic tracing. This result compares favorably to Godunov's method, but avoids the CFL constraint, so large time steps can be taken in practice. In fact, Godunov's method converges at O(h½), which is our result for Δt = Ch, where now C is not limited. However, the optimal choice, Δt = Ch2/(2r+1), gives a better rate, O(h2r/(2r+1)), than Godunov's method, e.g., O(h2/3) if r = 1. With a nondegenerate diffusion term, we obtain an L²-error estimate for the problem. We also prove the existence of, and give an error estimate for, a perturbed velocity field for which the volume is locally conserved. Finally, some convergence tests are given to verify the optimal convergence rate for r = 1. [ABSTRACT FROM AUTHOR]

We investigate a family of axisymmetric solutions to a coupling of Navier-Stokes and Allen--Cahn equations in R³. First, a one-dimensional system of equations is derived from the method of separation of variables, which approximates the three-dimensional system along its symmetry axis. Then based on them, by adding perturbation terms, we construct finite energy solutions to the three-dimensional system. We prove the global regularity of the constructed solutions in both large viscosity and small initial data cases. These solutions can be considered as perturbations near infinite-energy solutions. [ABSTRACT FROM AUTHOR]

We construct self-similar solutions of the Dafermos regularization of a system of conservation laws near structurally stable Riemann solutions composed of Lax shocks and rarefactions, with all waves possibly large. The construction requires blowing up a manifold of gain-of-stability turning points in a geometric singular perturbation problem as well as a new exchange lemma to deal with the remaining hyperbolic directions. [ABSTRACT FROM AUTHOR]

A powerly perturbed Markov chain (MC) is a family of finite MCs given by transition probability matrices P(ε) = (pij (ε)) (or generators for continuous-time MCs) such that pij (ε) = δijεdij + o(εdij), ε → 0. In the simplest case we have popular nearly completely decomposable (NCD) chains. It has been shown by directed forest expansions that solutions of linear systems related to P(ε) have a form xi(ε) = αiεαi + o(εαi ) for some vectors α = (αi) and a = (αi). Many characteristics of MCs such as stationary distributions, mean passage times, or limiting matrices can be defined in this way. We present efficient combinatorial aggregation algorithms for computing a and a. The algorithms rely on grouping the states of MCs in such a way that the probability of changing the state inside the group is of a greater order of magnitude than the interactions between groups. In contrast to existing methods, our approach is based on a combinatorial framework and can be seen as an algorithmization of the famous matrix tree theorem. We establish some preliminary results on the complexity of our algorithms. Numerical experiments on several network models, such as queueing systems or the Google problem, show the potential applicability of the method in real-life problems. [ABSTRACT FROM AUTHOR]