ATP-based Cross-Verification of Mizar Proofs: Method, Systems, and First Experiments

Mizar is a proof assistant used for formalization and mechanical verification of mathematics. The main use of Mizar is in the development of the Mizar Mathematical Library (MML), in which proofs are verified by the Mizar proof checker. The Mizar proof checker has a quite complex implementation, and also lacks the ability to print out detailed atomic proof steps in a format that is easy to verify with an independent proof-checking tool. This can raise concerns about the correctness of the MML. This paper describes a translation of Mizar natural-deduction proofs to the TPTP format used for recording derivations from first-order automated theorem proving systems, and verification of the resulting TPTP format derivations. The system was tested on two nontrivial sets of Mizar problems: the 252 “MPTP Challenge” problems, and 245 Mizar root theorems. The results of these tests are encouraging, and indicate that cross-verification of the whole MML is feasible. Supported by a Marie Curie International Fellowship within the 6th European Community Framework Programme.     

Fractional programming revisited

A new format is proposed for fractional programming problems. This format gives full expression to the fact that the parametric approach to fractional programming problems is rooted in a first-order necessary and sufficient optimality condition. It is thus shown that although traditionally it has not been construed as such, the parametric approach is in fact classical par excellence.     

Multilevel preconditioning and low‐rank tensor iteration for space–time simultaneous discretizations of parabolic PDEs

This paper addresses the solution of parabolic evolution equations simultaneously in space and time as may be of interest in, for example, optimal control problems constrained by such equations. As a model problem, we consider the heat equation posed on the unit cube in Euclidean space of moderately high dimension. An a priori stable minimal residual Petrov–Galerkin variational formulation of the heat equation in space–time results in a generalized least squares problem. This formulation admits a unique, quasi‐optimal solution in the natural space–time Hilbert space and serves as a basis for the development of space–time compressive solution algorithms. The solution of the heat equation is obtained by applying the conjugate gradient method to the normal equations of the generalized least squares problem. Starting from stable subspace splittings in space and in time, multilevel space–time preconditioners for the normal equations are derived. In order to reduce the complexity of the full space–time problem, all computations are performed in a compressed or sparse format called the hierarchical Tucker format, supposing that the input data are available in this format. In order to maintain sparsity, compression of the iterates within the hierarchical Tucker format is performed in each conjugate gradient iteration. Its application to vectors in the hierarchical Tucker format is detailed. Finally, numerical results in up to five spatial dimensions based on the recently developed htucker toolbox for MATLAB are presented. Copyright © 2014 John Wiley & Sons, Ltd.     

On the approximation of high-dimensional differential equations in the hierarchical Tucker format

The hierarchical Tucker format is a way to decompose a high-dimensional tensor recursively into sums of products of lower-dimensional tensors. The number of degrees of freedom in such a representation is typically many orders of magnitude lower than the number of entries of the original tensor. This makes the hierarchical Tucker format a promising approach to solve ordinary differential equations for high-dimensional tensors. In order to propagate the approximation in time, differential equations for the parameters of the hierarchical Tucker format are derived from the Dirac-Frenkel variational principle. We prove an error bound for the dynamical approximation in the hierarchical Tucker format by extending previous results of Koch and Lubich for the non-hierarchical Tucker format.     

四阶R-K方法中一类新算法的分析

对常微分方程初值问题数值计算中的四阶R-K方法首次具体给出了一般格式中的参数所满足的方程,并提出了新的计算格式,这些新算法对某些初值问题其整体截断误差有明显的减少.这对常微分方程初值问题在社会、经济、生态等领域中的广泛应用将提供有益的新算法.     

Stochastic Arithmetic in Multiprecision

Floating-point arithmetic precision is limited in length the IEEE single (respectively double) precision format is 32-bit (respectively 64-bit) long. Extended precision formats can be up to 128-bit long. However some problems require a longer floating-point format, because of round-off errors. Such problems are usually solved in arbitrary precision, but round-off errors still occur and must be controlled. Interval arithmetic has been implemented in arbitrary precision, for instance in the MPFI library. Interval arithmetic provides guaranteed results, but it is not well suited for the validation of huge applications. The CADNA library estimates round-off error propagation using stochastic arithmetic. CADNA has enabled the numerical validation of real-life applications, but it can be used in single precision or in double precision only. In this paper, we present a library called SAM (Stochastic Arithmetic in Multiprecision). It is a multiprecision extension of the classic CADNA library. In SAM (as in CADNA), the arithmetic and relational operators are overloaded in order to be able to deal with stochastic numbers. As a consequence, the use of SAM in a scientific code needs only few modifications. This new library SAM makes it possible to dynamically control the numerical methods used and more particularly to determine the optimal number of iterations in an iterative process. We present some applications of SAM in the numerical validation of chaotic systems modeled by the logistic map.     

Method of Nonconforming Mixed Finite Element for Second Order Elliptic Problems

In this paper, the method of non-conforming mixed finite element for second order elliptic problems is discussed and a format of real optimal order for the lowest order error estimate.     

Economic and financial prediction using rough sets model

A state-of-the-art review of the literature related to economic and financial prediction using rough sets model is presented, with special emphasis on the business failure prediction, database marketing and financial investment. These three applications require the accurate prediction of the future states based on the identification of patterns in the historical data. In addition, the historical data are in the format of a multi-attribute information table. All these conditions suit the rough sets model, an effective tool for multi-attribute classification problems. The different rough sets models and issues concerning the implementation of rough sets model – indicator selection, discretization and validation test, are also discussed in this paper. This paper will demonstrate that rough sets model is applicable to a wide range of practical problems pertaining to economic and financial prediction. In addition, the results show that the rough sets model is a promising alternative to the conventional methods for economic and financial prediction.     

热传导—对流问题的混合有限元分析注记

本文研究流体力学中的热传导－对流问题,分析其混合有限元解的存在性和误差估计,并给出一些混合有限元格式的例子。     

RobinX: A three-field classification and unified data format for round-robin sports timetabling

Sports timetabling problems are combinatorial optimization problems which consist of creating a timetable that defines against whom, when, and where teams play games. In the literature, sports timetabling problems have been reported featuring a wide variety of constraints and objectives. This variety makes it challenging to identify the relevant set of papers for a given sports timetabling problem. Moreover, the lack of a generally accepted data format makes that problem instances and their solutions are rarely shared. Consequently, it is hard to assess algorithmic performance since solution methods are often tested on just one or two specific instances. To mitigate these issues, this paper presents RobinX, a three-field notation to describe a sports timetabling problem by means of the tournament format, the constraints in use, and the objective. We use this notation to classify sports timetabling problems presented in the operations research literature during the last five decades. Moreover, RobinX contains xml-based file templates to store problem instances and their solutions and presents an online platform that offers three useful tools. First, a query tool assists users to select the relevant set of papers for a given timetabling problem. Second, the online platform provides access to an xml data repository that contains real-life problem instances from different countries and sports. Finally, the website enables users to interact with a free and open-source C++-library to read and write xml files and to validate and evaluate encoded instances and solutions.     

An XML format for benchmarks in High School Timetabling

The High School Timetabling Problem is amongst the most widely used timetabling problems. This problem has varying structures in different high schools even within the same country or educational system. Due to lack of standard benchmarks and data formats this problem has been studied less than other timetabling problems in the literature. In this paper we describe the High School Timetabling Problem in several countries in order to find a common set of constraints and objectives. Our main goal is to provide exchangeable benchmarks for this problem. To achieve this we propose a standard data format suitable for different countries and educational systems, defined by an XML schema. The schema and datasets are available online.     

求解对流扩散方程的一致四阶紧致格式

目前,许多高精度差分格式,由于未成功地构造与其精度匹配的稳定的边界格式,不得不采用低精度的边界格式.本文针对对流扩散方程证明了存在一致四阶紧致格式,它的边界点的计算格式和内点的计算格式的截断误差主项保持一致,给出了具体内点和边界格式;并分析了此半离散格式的渐近稳定性.数值结果表明该格式是四阶精度;在对流占优情况下,本文边界格式的数值结果比四阶精度的显式差分格式的的数值结果的数值振荡小,取得了不错的效果,理论结果得到了数值验证;驱动方腔数值结果显示,本文对N-S方程的离散格式具有很好的可靠性,适合对复杂流体流动的数值模拟和研究.     

An XML-based schema for stochastic programs

This paper describes a proposed format to record instances of stochastic programs. It forms part of a larger XML-based schema that is designed to allow the expression of essentially any type of mathematical program within a unifying framework. A wide variety of different linear and nonlinear stochastic programs can be handled, and the paper describes in some detail how this is done. Screen captures and sample problems illustrate the use of the schema.     

A new look at fractional programming

The parametric approach to fractional programming problems is examined and a new format is proposed for it. The latter reflects the fact that the approach as a whole capitalizes on a first-order necessary and sufficient optimality condition pertaining to differentiable pseudolinear functions.     

弱有限元方法在线弹性问题中的应用

本文考虑弱有限元（简称WG）方法在线弹性问题中的应用.WG方法是传统有限元方法的推广,用于偏微分方程的数值求解.和传统有限元一样,它的基本思想源于变分原理.WG方法的特点是使用在剖分单元内部和剖分单元边界上分别有定义的分片多项式函数（即弱函数）作为近似函数来逼近真解,并针对弱函数定义相应的弱微分算子代入数值格式进行计算.除此之外,WG方法允许在数值格式中引进稳定子以实现近似函数的弱连续性.WG方法具有允许使用任意多边形或多面体剖分,数值格式与逼近函数构造简单,易于满足相应的稳定性条件等优点.本文考虑WG方法在求解线弹性问题中的应用.围绕线弹性问题数值求解中常见的三个问题,即：数值格式的强制性,闭锁性,应力张量的对称性介绍WG方法在线弹性问题求解中的应用.     

Prior analysis and scheduling of the 2011 Rugby Union ITM Cup in New Zealand

This paper describes work done for the New Zealand Rugby Union (NZRU) in preparation for their most important wholly domestic competition in 2011. This competition had to be played during a shorter timescale than usual because of the 2011 Rugby Union World Cup, and the NZRU were keen to ensure that they could incorporate the format they wanted into this timescale without unfortunate consequences. In addition, they wanted to introduce a novel feature into this tournament. Thus some detailed prior experimental, or ‘what-if’, analysis was necessary. This paper describes this analysis and its results. As a result of this analysis, the NZRU was persuaded to abandon one of its design ideas, but was able to proceed with others, enabling them to announce the detailed format of the competition in the confidence that it would work well in practice. Subsequent scheduling of the competition in this format proved successful, and the resulting schedule is shown together with detailed analysis of its notional costs. The paper demonstrates how important it can be for schedulers to be closely involved in tournament design in advance of the actual scheduling.     

The Development of Linear Distance Functions for Distribution Analysis

The general method of estimating the road mileage between points identified only by their co-ordinates is to proportionately inflate the straight-line distance between them. We present the traditional single-region model and extend this to a generalized multi-region format. The inflating parameters are derived and various statistical tests carried out to evaluate the models. It is shown that, on average, the multi-region approach gives better mileage estimates for all types of distribution analysis. For specific problems, which are discussed, the single-region model is shown to produce results which are unacceptable for the planning of distribution networks.     

Pre-service teachers' free and structured mathematical problem posing

This exploratory study examined how pre-service teachers (PSTs) pose mathematical problems for free and structured mathematical problem-posing conditions. It was hypothesized that PSTs would pose more complex mathematical problems under structured posing conditions, with increasing levels of complexity, than PSTs would pose under free posing conditions, because the structured posing condition would guide PSTs to more closely consider the mathematical relationships in a posing situation. Sixty-five PSTs – 61 participating in a written assessment and 4 participating in task-based interviews – responded to problem-posing tasks under free or structured posing conditions. Two-way independent samples t-tests and chi-square tests were used to test the hypothesis, along with a qualitative analysis of the task-based interviews. We found that while the task format had limited impact on the complexity of problems posed, PSTs in the structured-posing condition may have more closely attended to the mathematical concepts in each task, and may have also impacted their process of posing problems than those in the free posing condition.