Discrete and continuous maximum principles for parabolic and elliptic operators

The major qualitative properties of linear parabolic and elliptic operators/PDEs are the different maximum principles (MPs). Another important property is the stabilization property (SP), which connects these two types of operators/PDEs. This means that under some assumptions the solution of the parabolic PDE tends to an equilibrium state when t→∞, which is the solution of the corresponding elliptic PDE. To solve PDEs we need to use some numerical methods, and it is a natural requirement that these qualitative properties are preserved on the discrete level. In this work we investigate this question when a two-level discrete mesh operator is used as the discrete model of the parabolic operator (which is a one-step numerical procedure for solving the parabolic PDE) and a matrix as a discrete elliptic operator (which is a linear algebraic system of equations for solving the elliptic PDE). We clarify the relation between the discrete parabolic maximum principle (DPMP), the discrete elliptic maximum principle (DEMP) and the discrete stabilization property (DSP). The main result is that the DPMP implies the DSP and the DEMP.     

Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem

Recently, the first author introduced some cryptographic functions closely related to the Diffie-Hellman problem called P-Diffie-Hellman functions. We show that the existence of a low-degree polynomial representing a P-Diffie-Hellman function on a large set would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on the degree of such interpolation polynomials. Analogously, we introduce a class of functions related to the discrete logarithm and show similar reduction and interpolation results.     

An elliptic theory of indicial weights and applications to non-linear geometry problems

Given an elliptic operator P on a non-compact manifold (with proper asymptotic conditions), there is a discrete set of numbers called indicial roots. It's known that P is Fredholm between weighted Sobolev spaces if and only if the weight is not indicial. We show that an elliptic theory exists even when the weight is indicial. We also discuss some simple applications to Yang–Mills theory and minimal surfaces.     

A flexible model and efficient solution strategies for discrete location problems

Flexible discrete location problems are a generalization of most classical discrete locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer, which depends on the position of that cost relative to the costs of fulfilling the demand of other customers.In this paper a covering type of model for the discrete ordered median problem is presented. For the solution of this model two sets of valid inequalities, which reduces the number of binary variables tremendously, and several variable fixing strategies are identified. Based on these concepts a specialized branch & cut procedure is proposed and extensive computational results are reported.     

On the discreteness criterion in <Emphasis Type="Italic">SL</Emphasis>(2, C)

In Tukia and Wang (Math. Scand 91:214–220, 2002) the authors conjectured that a non-elementary subgroup in SL(2, C) containing parabolic and elliptic elements is discrete if and only if each two-generator subgroup generated by a parabolic and an elliptic element is discrete. The purpose of this paper is to give an affirmative answer to this question.     

Extrapolation cascadic multigrid method on piecewise uniform grid

The triangular linear fnite elements on piecewise uniform grid for an elliptic problem in convex polygonal domain are discussed.Global superconvergence in discrete H1-norm and global extrapolation in discrete L2-norm are proved.Based on these global estimates the conjugate gradient method(CG)is efective,which is applied to extrapolation cascadic multigrid method(EXCMG).The numerical experiments show that EXCMG is of the global higher accuracy for both function and gradient.     

Approximation and optimization of Darboux type differential inclusions with set-valued boundary conditions

The present paper is devoted to an optimal control problem given by hyperbolic discrete (P _D ) and differential inclusions (P _C ) of generalized Darboux type and ordinary discrete inclusions. The results are extended to non-convex problems. An approach concerning necessary and sufficient conditions for optimality is proposed. In order to formulate sufficient conditions of optimality for problem (P _C ) the approximation method is used. Formulation of these conditions is based on locally adjoint mappings. Moreover for construction of adjoint partial differential inclusions the equivalence theorems of locally adjoint mappings are proved. One example with homogeneous boundary conditions is considered.     

Optimization of Second-Order Discrete Approximation Inclusions

The present article studies the approximation of the Bolza problem of optimal control theory with a fixed time interval given by convex and non-convex second-order differential inclusions (P _C ). Our main goal is to derive necessary and sufficient optimal conditions for a Cauchy problem of second-order discrete inclusions (P _D ). As a supplementary problem, discrete approximation problem (P _DA ) is considered. Necessary and sufficient conditions, including distinctive transversality, are proved by incorporating the Euler-Lagrange and Hamiltonian type of inclusions. The basic concept of obtaining optimal conditions is the locally adjoint mappings (LAM) and equivalence theorems, one of the most characteristic features of such approaches with the second-order differential inclusions that are peculiar to the presence of equivalence relations of LAMs. Furthermore, the application of these results are demonstrated by solving some non-convex problem with second-order discrete inclusions.     

L 2 -discrete hedging in a continuous-time model

In the setting of the Black-Scholes option pricing market model, the seller of a European option must trade continuously in time. This is, of course, unrealistic from the practical viewpoint. He must then follow a discrete trading strategy. However, it does not seem natural to hedge at deterministic times regardless of moves of the spot price. In this paper, it is supposed that the hedger trades at a fixed number N of rebalancing (stopping) times. The problem (P^N) of selecting the optimal hedging times and ratios which allow one to minimize the variance of replication error is considered. For given N rebalancing, the discrete optimal hedging strategy is identified for this criterion. The problem (P^N) is then transformed into a multidimensional optimal stopping problem with boundary constraints. The restrictive problem (P^N _BS) of selecting the optimal rebalancing for the same criterion is also considered when the ratios are given by Black-Scholes. Using the vector-valued optimal stopping theory, the existence is shown of an optimal sequence of rebalancing for each one of the problems (P^N) and (P^N _BS). It also shown BS that they are asymptotically equivalent when the number of rebalances becomes large and an optimality criterion is stated for the problem (P^N). The same study is made when more realistic restrictions are imposed on the hedging times. In the special case of two rebalances, the problem (P² _BS) is solved and the problems (P² _BS) and (P²) are transformed into two optimal stopping problems. This transformation is useful for numerical purposes.     

L-asymptotic behavior for a finite element approximation in parabolic quasi-variational inequalities related to impulse control problem

In this paper, the parabolic quasi-variational inequalities are transformed into a noncoercive elliptic quasi-variational inequalities. A new iterative discrete algorithm is proposed to show the existence and uniqueness, and a simple proof to asymptotic behavior in uniform norm is also given using the theta time scheme combined with a finite element spatial approximation. The proposed approach stands on a discrete L^∞-stability property with respect to the right-hand side and obstacle defined as an impulse control problem.     

Some new perspectives in best approximation and interpolation of random data

A new notion of universally optimal experimental design is introduced, relevant from the perspective of adaptive nonparametric estimation. It is demonstrated that both discrete and continuous Chebyshev designs are universally optimal in the problem of fitting properly weighted algebraic polynomials to random data. The result is a direct consequence of the well-known relation between Chebyshev’s polynomials and the trigonometric functions. Optimal interpolating designs in rational regression proved particularly elusive in the past. The question can be effectively handled using its connection to elliptic interpolation, in which the ordinary circular sinus, appearing in the classical trigonometric interpolation, is replaced by the Abel-Jacobi elliptic sinus sn(x, k) of a modulus k. First, it is demonstrated that — in a natural setting of equidistant design — the elliptic interpolant is never optimal in the so-called normal case k ∈ (?1, 1), except for the trigonometric case k = 0. However, the equidistant elliptic interpolation is always optimal in the imaginary case k ∈ i?. Through a relation between elliptic and rational functions, the result leads to a long sought optimal design, for properly weighted rational interpolants. Both the poles and nodes of the interpolants can be conveniently expressed in terms of classical Jacobi’s theta functions.     

Hybrid and Hybrid Adaptive Petri Nets: On the computation of a Reachability Graph

Petri Nets (PNs) constitute a well known family of formalisms for the modelling and analysis of Discrete Event Dynamic Systems (DEDS). As general formalisms for DEDS, PNs suffer from the state explosion problem. A way to alleviate this difficulty is to relax the original discrete model and deal with a fully or partially continuous model. In Hybrid Petri Nets (HPNs), transitions can be either discrete or continuous, but not both. In Hybrid Adaptive Petri Nets (HAPNs), each transition commutes between discrete and continuous behaviour depending on a threshold: if its load is higher than its threshold, it behaves as continuous; otherwise, it behaves as discrete. This way, transitions adapt their behaviour dynamically to their load. This paper proposes a method to compute the Reachability Graph (RG) of HPNs and HAPNs.     

Dirichlet problem on locally finite graphs

In this paper, we study the existence and uniqueness of solutions to the vertex-weighted Dirichlet problem on locally finite graphs. Let B be a subset of the vertices of a graph G. The Dirichlet problem is to find a function whose discrete Laplacian on G?B and its values on B are given. Each infinite connected component of G?B is called an end of G relative to B. If there are no ends, then there is a unique solution to the Dirichlet problem. Such a solution can be obtained as a limit of an averaging process or as a minimizer of a certain functional or as a limit-solution of the heat equation on the graph. On the other hand, we show that if G is a locally finite graph with l ends, then the set of solutions of any Dirichlet problem, if non-empty, is at least l-dimensional.     

Stochastic spanning tree problem

The minimal spanning tree problem has been well studied and until now many efficient algorithms such as [5,6] have been proposed. This paper generalizes it toward a stochastic version, i.e., considers a stochastic spanning tree problem in which edge costs are not constant but random variables and its objective is to find an optimal spanning tree satisfying a certain chance constraint. This problem may be considered as a discrete version of P-model first introduced by Kataoka [4].First it is transformed into its deterministic equivalent problem P. Then, an auxiliary problem P(R) with a positive parameter R is defined. After clarifying close relations between P and P(R), this paper proposes a polynomial order algorithm fully utilizing P(R). Finally, more improvement of the algorithm and applicability of this type algorithm to other discrete stochastic programming problems are discussed.     

Stability for semilinear elliptic variational inequalities depending on the gradient

In this work we give a result concerning the continuous dependence on the data for weak solutions of a class of semilinear elliptic variational inequalities (P_n) with a nonlinear term depending on the gradient of the solution. This paper can be seen as the second part of the work Matzeu and Servadei (2010) [9], in the sense that here we give a stability result for the C^1,α-weak solutions of problem (P_n) found in Matzeu and Servadei (2010) [9] through variational techniques. To be precise, we show that the solutions of (P_n), found with the arguments of Matzeu and Servadei (2010) [9], converge to a solution of the limiting problem (P), under suitable convergence assumptions on the data.     

Invariants of matrix pairs over discrete valuation rings and Littlewood-Richardson fillings

Let M and N be two r×r matrices of full rank over a discrete valuation ring R with residue field of characteristic zero. Let P,Q and T be invertible r×r matrices over R. It is shown that the orbit of the pair (M,N) under the action (M,N)?(PMQ^-1,QNT^-1) possesses a discrete invariant in the form of Littlewood-Richardson fillings of the skew shape λ/μ with content ν, where μ is the partition of orders of invariant factors of M, ν is the partition associated to N, and λ the partition of the product MN. That is, we may interpret Littlewood-Richardson fillings as a natural invariant of matrix pairs. This result generalizes invariant factors of a single matrix under equivalence, and is a converse of the construction in Appleby (1999) [1], where Littlewood-Richardson fillings were used to construct matrices with prescribed invariants. We also construct an example, however, of two matrix pairs that are not equivalent but still have the same Littlewood-Richardson filling. The filling associated to an orbit is determined by special quotients of determinants of a matrix in the orbit of the pair.     

A kind of nonnegative matrices and its application on the stability of discrete dynamical systems

In this paper we introduce a new kind of nonnegative matrices which is called (sp) matrices. We show that the zero solutions of a class of linear discrete dynamical systems are asymptotically stable if and only if the coefficient matrices are (sp) matrices. To determine that a matrix is (sp) matrix or not is very simple, we need only to verify that some elements of the coefficient matrices are zero or not. According to the result above, we obtain the conditions for the stability of several classes of discrete dynamical systems.     

Superconvergence and a posteriori error estimates of RT1 mixed methods for elliptic control problems with an integral constraint

In this paper, we investigate the superconvergence property and a posteriori error estimates of mixed finite element methods for a linear elliptic control problem with an integral constraint. The state and co-state are approximated by the order k = 1 Raviart-Thomas mixed finite element spaces and the control variable is approximated by piecewise constant functions. Approximations of the optimal control of the continuous optimal control problem will be constructed by a projection of the discrete adjoint state. It is proved that these approximations have convergence order h ². Moreover, we derive a posteriori error estimates both for the control variable and the state variables. Finally, a numerical example is given to demonstrate the theoretical results.     

Error estimates of the lumped mass finite element method for semilinear elliptic problems

We are concerned with the semilinear elliptic problems. We first investigate the L²-error estimate for the lumped mass finite element method. We then use the cascadic multigrid method to solve the corresponding discrete problem. On the basis of the finite element error estimates, we prove the optimality of the proposed multigrid method. We also report some numerical results to support the theory.     

Error inequalities for quintic and biquintic discrete Hermite interpolation

In this paper we shall develop a class of discrete Hermite interpolates in one and two independent variables. Further, we offer explicit error bounds in ?_∞ norm for the quintic and biquintic discrete Hermite interpolates. Some numerical examples are included to illustrate the results obtained.