Application of Modal Logics to the Specification and Verification of Programs

Temporal logic methods and algorithms are used for verifying programs. A method employing temporal semantic tables is proposed for studying the properties of dynamic processes.     

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus

We investigate read-once branching programs for the following search problem: given a Boolean m × n matrix with m > n, nd either an all-zero row, or two 1s in some column. Our primary motivation is that this models regular resolution proofs of the pigeonhole principle , and that for m > n ² no lower bounds are known for the length of such proofs. We prove exponential lower bounds (for arbitrarily large m!) if we further restrict this model by requiring the branching program either to finish one row of queries before asking queries about another row (the row model) or put the dual column restriction (the column model).Then we investigate a special class of resolution proofs for that operate with positive clauses of rectangular shape; we call this fragment the rectangular calculus. We show that all known upper bounds on the size of resolution proofs of actually give rise to proofs in this calculus and, inspired by this fact, also give a remarkably simple rectangular reformulation of the Haken–Buss–Turán lower bound for the case m n ². Finally we show that the rectangular calculus is equivalent to the column model on the one hand, and to transversal calculus on the other hand, where the latter is a natural proof system for estimating from below the transversal size of set families. In particular, our exponential lower bound for the column model translates both to the rectangular and transversal calculi.* Part of the work was done while this author was visiting Special Year on Logic and Algorithms at DIMACS, Princeton. Also supported by Russian Basic Research Foundation grant 96-01-01222. Part of this work was done while on sabbatical leave at the Institute for Advanced Study and Princeton University, Princeton. This work was supported by USA-Israel BSF grant 92-00106 and by a Wolfson research award administered by the Israeli Academy of Sciences, as well as a Sloan Foundation grant. This work was supported in part by National Science Foundation and DARPA under grant CCR-9627819, and by USA-Israel BSF grant 92-00106.     

Higher-Order Averaging, Formal Series and Numerical Integration I: B-series

We show how B-series may be used to derive in a systematic way the analytical expressions of the high-order stroboscopic averaged equations that approximate the slow dynamics of highly oscillatory systems. For first-order systems we give explicitly the form of the averaged systems with O(e^j)mathcal{O}(epsilon^{j}) errors, j=1,2,3 (2π ε denotes the period of the fast oscillations). For second-order systems with large O(e^-1)mathcal{O}(epsilon^{-1}) forces, we give the explicit form of the averaged systems with O(e^j)mathcal{O}(epsilon^{j}) errors, j=1,2. A variant of the Fermi–Pasta–Ulam model and the inverted Kapitsa pendulum are used as illustrations. For the former it is shown that our approach establishes the adiabatic invariance of the oscillatory energy. Finally we use B-series to analyze multiscale numerical integrators that implement the method of averaging. We construct integrators that are able to approximate not only the simplest, lowest-order averaged equation but also its high-order counterparts.     

Adiabatic Invariance and Applications: From Molecular Dynamics to Numerical Weather Prediction

A wide class of Hamiltonian systems exhibit a mixture of slow motion with superimposed fast oscillations. Under the assumption of scale separation, these systems can be investigated using the principle of adiabatic invariance. In this paper, we start with a review of some of the main theoretical and numerical findings. We then briefly summarize a few important implications for molecular dynamics (MD) before we provide a more extensive discussion of numerical weather prediction (NWP). In particular, the conservative Hamiltonian particle-mesh (HPM) method is extended to Euler's equation and the fundamental concepts of geostrophic and hydrostatic balance are illustrated on the level of fluid blobs. We also demonstrate numerically that symplectic time-stepping methods are able to maintain hydrostatic balance to high accuracy.     

Higher-Order Averaging, Formal Series and Numerical Integration II: The Quasi-Periodic Case

The paper considers non-autonomous oscillatory systems of ordinary differential equations with d≥1 non-resonant constant frequencies ω ₁,…,ω _d . Formal series like those used nowadays to analyze the properties of numerical integrators are employed to construct higher-order averaged systems and the required changes of variables. With the new approach, the averaged system and the change of variables consist of vector-valued functions that may be written down immediately and scalar coefficients that are universal in the sense that they do not depend on the specific system being averaged and may therefore be computed once and for all given ω ₁,…,ω _d . The new method may be applied to obtain a variety of averaged systems. In particular, we study the quasi-stroboscopic averaged system characterized by the property that the true oscillatory solution and the averaged solution coincide at the initial time. We show that quasi-stroboscopic averaging is a geometric procedure, because it is independent of the particular choice of co-ordinates used to write the given system. As a consequence, quasi-stroboscopic averaging of a canonical Hamiltonian (respectively, of a divergence-free) system results in a canonical (respectively, in a divergence-free) averaged system. We also study the averaging of a family of near-integrable systems where our approach may be used to construct explicitly d formal first integrals for both the given system and its quasi-stroboscopic averaged version. As an application we construct three first integrals of a system that arises as a nonlinear perturbation of five coupled harmonic oscillators with one slow frequency and four resonant fast frequencies.     

A Theorem for Numerical Verification on Local Uniqueness of Solutions to Fixed-Point Equations

We give a theoretical result with respect to numerical verification of existence and local uniqueness of solutions to fixed-point equations which are supposed to have Fréchet differentiable operators. The theorem is based on Banach's fixed-point theorem and gives sufficient conditions in order that a given set of functions includes a unique solution to the fixed-point equation. The conditions are formulated to apply readily to numerical verification methods.

We already derived such a theorem in [11 N. Yamamoto ( 1998 ). A numerical verification method for solutions of boundary value problems with local uniqueness by Banach's fixed-point theorem . SIAM J. Numer. Anal. 35 : 2004 – 2013 .[Crossref] , [Google Scholar]], which is suitable to Nakao's methods on numerical verification for PDEs. The present theorem has a more general form and one may apply it to many kinds of differential equations and integral equations which can be transformed into fixed-point equations.     

An Efficient Approach to the Numerical Verification for Solutions of Elliptic Differential Equations

The authors and their colleagues have developed numerical verification methods for solutions of second-order elliptic boundary value problems based on the infinite-dimensional fixed-point theorem using the Newton-like operator with appropriate approximation and constructive a priori error estimates for Poisson's equations. Many verification results show that the authors' methods are sufficiently useful when the equation has no first-order derivative. However, in the case that the equation includes the term of a first-order derivative, there is a possibility that the verification algorithm does not work even though we adopt a sufficiently accurate approximation subspace. The purpose of this paper is to propose an alternative method to overcome this difficulty. Numerical examples which confirm the effectiveness of the new method are presented.     

矩形到任意多边形区域的Schwarz-Christoffel变换数值解法

运用Schwarz-Christoffel变换方法，建立多边形区域到带状区域共形映射数学模型.对于模型中的约束条件和奇异积分问题，根据Riemann(黎曼)原理，建立复参数与实参数互逆变换，消除非线性系统的约束条件；经过合理积分路径的确定，模型中的奇异积分转化为Gauss-Jacobi(高斯 雅可比)型积分；采用Levenberg-Marquardt算法对非线性系统模型进行求解.根据第一类椭圆函数性质，建立了矩形区域到带状区域共形映射数学模型，通过复参数椭圆函数的计算，得到矩形边界与带状区域边界的关系.最后，对8点对称多边形区域与27点不规则条带状区域计算，将不规则封闭区域边界映射到矩形区域边界，矩形区域内的正交网格，通过变换之后在多边形区域内依然满足正交性，为研究不规则区域到规则区域映射的数值计算奠定基础.     

An Approach to The Numerical Verification of Solutions for Nonlinear Elliptic Problems With Local Uniqueness

We propose a numerical method to verify the existence and local uniqueness of solutions to nonlinear elliptic equations. We numerically construct a set containing solutions which satisfies the hypothesis of Banach's fixed point theorem in a certain Sobolev space. By using the finite element approximation and constructive error estimates, we calculate the eigenvalue bound with smallest absolute value to evaluate the norm of the inverse of the linearized operator. Utilizing this bound we derive a verification condition of the Newton-Kaiitorovich type. Numerical examples are presented.     

A Numerical Verification Method for a System of FitzHugh-Nagumo Type

We propose a numerical method to enclose a solution of the FitzHugh-Nagumo equation with Neumann boundary conditions. We construct, on a computer, a set which satisfies the hypothesis of Schauder's fixed point theorem for a compact map in a certain Sobolev space, which, therefore contains a solution. Several verified results are presented.     

Numerical Verification Methods for Solutions of the Free Boundary Problem

We propose two methods to enclose the solution of an ordinary free boundary problem. The problem is reformulated as a nonlinear boundary value problem on a fixed interval including an unknown parameter. By appropriately setting a functional space that depends on the finite element approximation, the solution is represented as a fixed point of a compact map. Then, by using the finite element projection with constructive error estimates, a Newton-type verification procedure is derived. In addition, numerical examples confirming the effectiveness of current methods are given.     

论中值定理类命题证明中的辅助函数构造

借助实例分析的方法,讨论在证明微分与积分相结合的中值定理类命题时,关于辅助函数的构造技巧及其变形思想.     

The Asymptotic Expansion and Numerical Verification of Van der Pol's Equation

A technique is presented in this paper to verify the order of accuracy of asymptotic expansion of Van der Pol's equation. The technique is focused on using numerical solutions as an independent means of verifying the validity of asymptotic expansions.     

二维多项式本征应变边界积分方程及其数值验证

针对弹性介质中的椭圆形异质体,给出了低阶多项式分布的二维本征应变边界积分方程和相应的Eshelby张量的定义．以边界元分域法为参照,利用含有单个异质体的弹性介质对提出的计算模型和算法进行了数值验证．结果表明该算法取得较大的改进,其计算效率高于传统的边界元法,计算精度则高于采用常数本征应变的计算模型．