An adaptive finite volume method for the diffraction grating problem with the truncated DtN boundary condition

We consider GMRES applied to discretisations of the high-frequency Helmholtz equation with strong trapping; recall that in this situation the problem is exponentially ill-conditioned through an increasing sequence of frequencies. Our main focus is on boundary-integral-equation formulations of the exterior Dirichlet and Neumann obstacle problems in 2- and 3-d. Under certain assumptions about the distribution of the eigenvalues of the integral operators, we prove upper bounds on how the number of GMRES iterations grows with the frequency; we then investigate numerically the sharpness (in terms of dependence on frequency) of both our bounds and various quantities entering our bounds. This paper is therefore the first comprehensive study of the frequency-dependence of the number of GMRES iterations for Helmholtz boundary-integral equations under trapping.

     

Variational approximations in energy space for the regulator problem with time delay

We consider a variational procedure for approximating the solution of the state regulator problem with time delay. Motivated by a dual formulation of the problem, we introduce a positive-definite functionalF over a certain energy space of Mikhlin and obtain approximating solutions by the Ritz-Trefftz idea of minimizing it over finite-dimensional subspaces. The resulting approximating solutions, in turn, furnish suboptimal solutions which converge to the optimal solution of the regulator problem with time delay. A priori error bounds in terms of splines are given. A posteriori error bounds are also obtained.     

Exponential sums and singular hypersurfaces

We give upper bounds for the absolute value of exponential sums in several variables attached to certain polynomials with coefficients in a finite field. This bounds are given in terms of invariants of the singularities of the projective hypersurface defined by its highest degree form. For exponential sums attached to the reduction modulo a power of a large prime of a polynomial f with integer coefficients and veryfying a certain condition on the singularities of its highest degree form, we give a bound in terms of the dimension of the Jacobian quotient . Received: 3 November 1997     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.     

Componentwise perturbation analyses for the QR factorization

Summary. This paper gives componentwise perturbation analyses for Q and R in the QR factorization A=QR, , R upper triangular, for a given real $m\times n$ matrix A of rank n. Such specific analyses are important for example when the columns of A are badly scaled. First order perturbation bounds are given for both Q and R. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition number for R is bounded for a fixed n when the standard column pivoting strategy is used. This strategy also tends to improve the condition of Q, so usually the computed Q and R will both have higher accuracy when we use the standard column pivoting strategy. Practical condition estimators are derived. The assumptions on the form of the perturbation are explained and extended. Weaker rigorous bounds are also given. Received April 11, 1999 / Published online October 16, 2000     

On the optimal control of arrivals to a single queue with arbitrary feedback delay

We consider a problem of admission control to a single queue in discrete time. The controller has access to k step old queue lengths only, where k can be arbitrary. The problem is motivated, in particular, by recent advances in high-speed networking where information delays have become prominent. We formulate the problem in the framework of Completely Observable Controlled Markov Chains, in terms of a multi-dimensional state variable. Exploiting the structure of the problem, we show that under appropriate conditions, the multi-dimensional Dynamic Programming Equation (DPE) can be reduced to a unidimensional one. We then provide simple computable upper and lower bounds to the optimal value function corresponding to the reduced unidimensional DPE. These upper and lower bounds, along with a certain relationship among the parameters of the problem, enable us to deduce partially the structural features of the optimal policy. Our approach enables us to recover simply, in part, the recent results of Altman and Stidham, who have shown that a multiple-threshold-type policy is optimal for this problem. Further, under the same relationship among the parameters of the problem, we provide easily computable upper bounds to the multiple thresholds and show the existence of simple relationships among these upper bounds. These relationships allow us to gain very useful insights into the nature of the optimal policy. In particular, the insights obtained are of great importance for the problem of actually computing an optimal policy because they reduce the search space enormously. This revised version was published online in June 2006 with corrections to the Cover Date.     

A property of eigenvalue bounds for a class of symmetric tridiagonal interval matrices

The eigenvalue bounds of interval matrices are often required in some mechanical and engineering fields. In this paper, we consider an interval eigenvalue problem with symmetric tridiagonal matrices. A theoretical result is obtained that under certain assumptions the upper and lower bounds of interval eigenvalues of the problem must be achieved just at some vertex matrices of the interval matrix. Then a sufficient condition is provided to guarantee the assumption to be satisfied. The conclusion is illustrated also by a numerical example. Copyright © 2010 John Wiley & Sons, Ltd.     

Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications

We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative, and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem, our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty method for solving irregular problems. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

A Posteriori Error Estimates for the Approximations of the Stresses in the Hencky Plasticity Problem

In this article, we derive a posteriori error estimates for the Hencky plasticity problem. These estimates are formulated in terms of the stresses and present guaranteed and computable bounds of the difference between the exact stress field and any approximation of it from the energy space of the dual variational problem. They consist of quantities that can be considered as penalties for the violations of the equilibrium equations, the yield condition and the constitutive relations that must hold for the exact stresses and strains. It is proved that the upper bound tends to zero for any sequence of stresses that tends to the exact solution of the Haar–Karman variational problem. An important ingredient of our analysis is a collection of Poincaré type inequalities involving the L ¹ norms of the tensors of small deformation. Estimates of this form are not new, however we will present computable upper bounds for the constants being involved even for rather complicated domains.     

KAM theory near multiplicity one resonant surfaces in perturbations of a-priori stable hamiltonian systems

Summary We consider a near-integrable Hamiltonian system in the action-angle variables with analytic Hamiltonian. For a given resonant surface of multiplicity one we show that near a Cantor set of points on this surface, whose remaining frequencies enjoy the usual diophantine condition, the Hamiltonian may be written in a simple normal form which, under certain assumptions, may be related to the class which, following Chierchia and Gallavotti [1994], we calla-priori unstable. For the a-priori unstable Hamiltonian we prove a KAM-type result for the survival of whiskered tori under the perturbation as an infinitely differentiable family, in the sense of Whitney, which can then be applied to the above normal form in the neighborhood of the resonant surface. This paper is dedicated to the memory of Juan C. Simo This paper was solicited by the editors to be part of a volume dedicated to the memory of Juan C. Simo.     

Enumerating a subset of the integer points inside a Minkowski sum

Sparse elimination exploits the structure of algebraic equations in order to obtain tighter bounds on the number of roots and better complexity in numerically approximating them. The model of sparsity is of combinatorial nature, thus leading to certain problems in general-dimensional convex geometry. This work addresses one such problem, namely the computation of a certain subset of integer points in the interior of integer convex polytopes. These polytopes are Minkowski sums, but avoiding their explicit construction is precisely one of the main features of the algorithm. Complexity bounds for our algorithm are derived under certain hypotheses, in terms of output-size and the sparsity parameters. A public domain implementation is described and its performance studied. Linear optimization lies at the inner loop of the algorithm, hence we analyze the structure of the linear programs and compare different implementations.     

Continuity theorems for the M/M/1/n queueing system

In this paper continuity theorems are established for the number of losses during a busy period of the M/M/1/n queue. We consider an M/GI/1/n queueing system where the service time probability distribution, slightly different in a certain sense from the exponential distribution, is approximated by that exponential distribution. Continuity theorems are obtained in the form of one or two-sided stochastic inequalities. The paper shows how the bounds of these inequalities are changed if further assumptions, associated with specific properties of the service time distribution (precisely described in the paper), are made. Specifically, some parametric families of service time distributions are discussed, and the paper establishes uniform estimates (given for all possible values of the parameter) and local estimates (where the parameter is fixed and takes only the given value). The analysis of the paper is based on the level crossing approach and some characterization properties of the exponential distribution. Dedicated to Vladimir Mikhailovich Zolotarev, Victor Makarovich Kruglov, and to the memory of Vladimir Vyacheslavovich Kalashnikov.     

On the problem of spurious eigenvalues in the approximation of linear elliptic problems in mixed form

In the approximation of linear elliptic operators in mixed form, it is well known that the so-called inf-sup and ellipticity in the kernel properties are sufficient (and, in a sense to be made precise, necessary) in order to have good approximation properties and optimal error bounds. One might think, in the spirit of Mercier-Osborn-Rappaz-Raviart and in consideration of the good behavior of commonly used mixed elements (like Raviart-Thomas or Brezzi-Douglas-Marini elements), that these conditions are also sufficient to ensure good convergence properties for eigenvalues. In this paper we show that this is not the case. In particular we present examples of mixed finite element approximations that satisfy the above properties but exhibit spurious eigenvalues. Such bad behavior is proved analytically and demonstrated in numerical experiments. We also present additional assumptions (fulfilled by the commonly used mixed methods already mentioned) which guarantee optimal error bounds for eigenvalue approximations as well.

     

Estimates of the deviations from the exact solutions for variational inequalities describing the stationary flow of certain viscous incompressible fluids

This paper is concerned with computable and guaranteed upper bounds of the difference between exact solutions of variational inequalities arising in the theory of viscous fluids and arbitrary approximations in the corresponding energy space. Such estimates (also called error majorants of functional type) have been derived for the considered class of nonlinear boundary‐value problems in (Math. Meth. Appl. Sci. 2006; 29:2225–2244) with the help of variational methods based on duality theory from convex analysis. In the present paper, it is shown that error majorants can be derived in a different way by certain transformations of the variational inequalities that define generalized solutions. The error bounds derived by this techniques for the velocity function differ from those obtained by the variational method. These estimates involve only global constants coming from Korn‐ and Friedrichs‐type inequalities, which are not difficult to evaluate in case of Dirichlet boundary conditions. For the case of mixed boundary conditions, we also derive another form of the estimate that contains only one constant coming from the following assertion: the L² norm of a vector‐valued function from H¹(Ω) in the factor space generated by the equivalence with respect to rigid motions is bounded by the L² norm of the symmetric part of the gradient tensor. As for some ‘simple’ domains such as squares or cubes, the constants in this inequality can be found analytically (or numerically), we obtain a unified form of an error majorant for any domain that admits a decomposition into such subdomains. Copyright © 2009 John Wiley & Sons, Ltd.     

Maximum principles for functionals associated with the solution of semilinear elliptic boundary value problems

We consider a new P-function associated with the solutionu of an elliptic boundary value problem and obtain pointwise bounds for the gradient in terms of the maximum ofu and the geometry of the domain. SimilarP-functions have previously been used to obtain bounds of the same type. Our results give improved bounds for certain problems, in particular we obtain isoperimetric inequalities for the maximum stress in the Saint-Venant torsion problem.     

Calibrating the Black-Derman-Toy model: some theoretical results

The Black-Derman-Toy (BDT) model is a popular one-factor interest rate model that is widely used by practitioners. One of its advantages is that the model can be calibrated to both the current market term structure of interest rate and the current term structure of volatilities. The input term structure of volatility can be either the short term volatility or the yield volatility. Sandmann and Sondermann derived conditions for the calibration to be feasible when the conditional short rate volatility is used. In this paper conditions are investigated under which calibration to the yield volatility is feasible. Mathematical conditions for this to happen are derived. The restrictions in this case are more complicated than when the short rate volatilities are used since the calibration at each time step now involves the solution of two non-linear equations. The theoretical results are illustrated by showing numerically that in certain situations the calibration based on the yield volatility breaks down for apparently plausible inputs. In implementing the calibration from period n to period n + 1, the corresponding yield volatility has to lie within certain bounds. Under certain circumstances these bounds become very tight. For yield volatilities that violate these bounds, the computed short rates for the period (n, n + 1) either become negative or else explode and this feature corresponds to the economic intuition behind the breakdown.     

Dirac eigenvalue estimates on surfaces

We prove lower Dirac eigenvalue bounds for closed surfaces with a spin structure whose Arf invariant equals 1. Besides the area only one geometric quantity enters in these estimates, the spin-cut-diameter which depends on the choice of spin structure. It can be expressed in terms of various distances on the surfaces or, alternatively, by stable norms of certain cohomology classes. In case of the 2-torus we obtain a positive lower bound for all Riemannian metrics and all nontrivial spin structures. For higher genus g the estimate is given by The corresponding estimate also holds for the -spectrum of the Dirac operator on a noncompact complete surface of finite area. As a corollary we get positive lower bounds on the Willmore integral for all 2-tori embedded in . Received: 15 May 2001; in final form: 11 September 2001 / Published online: 1 February 2002     

Space and time complexities of balanced sorting on processor arrays

A processor is balanced in carrying out a computation if its computing time equals its I/O time. When the computation bandwidth of a processor is increased, like when multiple processors are incorporated to form an array, the critical question is to what degree the processor's memory must be enlarged in order to alleviate the I/O bottleneck to keep the computation balanced. In this paper, for the sorting problem, we present two balanced algorithms on linearly connected and mesh-connected processor arrays, respectively, and show that they reach the derived lower bounds of memory sizes. We also verify that the time complexities of the algorithms are optimal under their respective hardware constraints.     

Approximate Solutions and Error Bounds for Solving Matrix Differential Equations Without Increasing the Dimension of the Problem

In this paper we present a method for solving initial value problems related to second order matrix differential equations. This method is based on the existence of a solution of a certain algebraic matrix equation related to the problem, and it avoids the increase of the dimension of the problem for its resolution. Approximate solutions, and their error bounds in terms of error bounds for the approximate solutions of the algebraic problem, are given.     

New and old bounds for standard quadratic optimization: dominance,equivalence and incomparability

A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Programming and decomposition of the objective function into a sum of two quadratic functions, each of which is easy to minimize. We provide a complete diagram of the dominance, incomparability, or equivalence relations among the bounds proposed in this and in previous works. In particular, we show that one of our new bounds dominates all the others. Furthermore, a specialization of such bound dominates Schrijver’s improvement of Lovász’s θ function bound for the maximum size of a clique in a graph.