Choiceless polynomial time

Turing machines define polynomial time (PTime) on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time (without presuming the presence of a linear order)? Earlier, one of us conjectured a negative answer. The problem motivated a quest for stronger and stronger PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines (formerly called evolving algebras). The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime.     

Twostep-by-twostep continuous PIRKN-type PC methods for nonstiff IVPs

In this paper, we start with the consideration of direct collocation-based Runge-Kutta-Nyström (RKN) methods with continuous output formulas for solving nonstiff initial-value problems (IVPs) for systems of special second-order differential equations y″(t) = f(t, y(t)). At nth step, the continuous output formulas can be used for calculating the step values at (n + 2)th step and the integration processes can be proceeded twostep-by-twostep. In this case, we obtain twostep-by-twostep RKN methods with continuous output formulas (continuous TBTRKN methods). Furthermore, we consider a parallel predictor-corrector (PC) iteration scheme using the continuous TBTRKN methods as corrector methods with predictor methods defined by the continuous output formulas. The resulting twostep-by-twostep parallel-iterated RKN-type PC methods with continuous output formulas (twostep-by-twostep continuous PIRKN-type PC methods or TBTCPIRKN methods) give us a faster integration processes. Numerical comparisons based on the solution of a few widely-used test problems show that the new TBTCPIRKN methods are much more efficient than the well-known PIRKN methods, the famous nonstiff sequential ODEX2, DOP853 codes and comparable with the CPIRKN methods.     

A note on parallelism in affine geometry

The uniqueness of the parallel lines is independent from the analogous statement on parallel planes and the usual further axioms of three-dimensional affine geometry. MSC: 51A15, 03F65.     

Evaluation of parallelism by ultrasonic echo method

The determination of parallelism in a transparent plate is usually done either by the movement of a stylus or by an optical method, such as interference fringes. For opaque objects, the only method appears to be the use of stylus. The authors have developed an acoustic method to evaluate the parallelism between faces of any block even if it is opaque to light. It is based on the echoes received from the two surfaces when incident upon by a short duration high frequency ultrasonic pulse. The paper describes the basic principle and also the methodologies for evaluation in laboratory and in industry. The method requires essentially only one side to be accessible. Theoretical and experimental results show excellent agreement up to 1° of arc. The uncertainty of measurements of results is ±0.1°. It is expected that the new method would find applications in several industries.     

Measurement of parallelism of the surfaces of a transparent sample

An interferometric method for the measurement of parallelism of the end faces of a transparent material is described. It is based on the measurement of fringe displacement caused by the wedge angle of the material by using the Lau effect.     

Exploiting structure in parallel implementation of interior point methods for optimization

OOPS is an object-oriented parallel solver using the primal–dual interior point methods. Its main component is an object-oriented linear algebra library designed to exploit nested block structure that is often present in truly large-scale optimization problems such as those appearing in Stochastic Programming. This is achieved by treating the building blocks of the structured matrices as objects, that can use their inherent linear algebra implementations to efficiently exploit their structure both in a serial and parallel environment. Virtually any nested block-structure can be exploited by representing the matrices defining the problem as a tree build from these objects. OOPS can be run on a wide variety of architectures and has been used to solve a financial planning problem with over 10⁹ decision variables. We give details of supported structures and their implementations. Further we give details of how parallelisation is managed in the object-oriented framework.     

A parallelized integral-direct second-order Møller–Plesset perturbation theory method with a fragment molecular orbital scheme

We propose a parallelized integral-direct algorithm of the second-order Møller–Plesset perturbation theory (MP2) as a size-consistent correlated method. The algorithm is a modification of the recipe by Mochizuki et al. [(1996) Theor Chim Acta 93:211]. There is no need to communicate the bulky data of integrals across worker processes, keeping the formal fifth-power dependence on the number of basis functions. A multiple integral screening procedure is incorporated to reduce the operation costs effectively. An approximate MP2 density matrix can also be directly calculated through the integral contraction with orbital energies. We implement the MP2 code by accepting Kitauras fragment molecular orbital (FMO) scheme as in the program ABINIT-MP developed by Nakano et al. [(2002) Chem Phys Lett 351:475]. The error in the FMO–MP2 energies is found to be within the order of the chemical accuracy. Timing and parallel acceleration results are shown for test molecules.     

一种求解扩散方程的混合格式

本文提出了一种求解扩散方程的新型混合格式，具有明显的并行性，很高的精度与稳定性．文中给出了一数值例子，其在一具有五个ｔｒａｎｓｐｕｔｅｒ的并行机上的并行加速达３．５．     

Parallelized integral-direct CIS(D) calculations with multilayer fragment molecular orbital scheme

We have developed a parallelized integral-direct code of the perturbative doubles correction for configuration interaction with singles, proposed as CIS(D) by Head-Gordon et al. (Chem Phys Lett 219:21, 1994). The CIS(D) method provides the energy corrections both of the relaxation and differential correlation for the respective CIS excited states. The implementation of CIS(D) is based on our original algorithm for the second-order Møller–Plesset perturbation (MP2) calculations (Mochizuki et al. in Theor Chem Acc 112:442, 2004). There is no need to communicate bulky intermediate data among worker processes of the parallelized execution. This CIS(D) code is then incorporated into a developer version of ABINIT-MP program, in order to improve the overestimation in excitation energies calculated by the CIS method in conjunction with the multilayer fragment molecular orbital scheme (MLFMO-CIS) (Mochizuki et al. in Chem Phys Lett 406:283, 2005). The MLFMO-CIS(D) method is first used in evaluating the lowest n\(\pi^{*}\) excitation energy of the hydrated formaldehyde. The photoactive yellow protein (PYP) is the second target of MLFMO-CIS(D) calculation. Through these applications, it is shown that the CIS(D) correction improves the CIS results favorably.     

一种利用图像序列进行摄像机标定的方法

结合消隐点的有关知识,利用图像序列中运动的人体及其阴影的垂直关系,给出了一种实用性比较强的摄像机标定方法.该方法采用线性的方法计算出了可变焦摄像机5参数的内参数矩阵及旋转矩阵,并在一定的条件下计算出平移矩阵,最终将摄像机完全标定.计算内参数及旋转矩阵时不必考虑图像之间对应点之间的关系,从而大大减少了图像检测期间算法的复杂度,提高了标定的速度.此外,模拟和实际图像实验也表明该自标定方法具有较高的鲁棒性和准确性,适用于在线摄像机标定系统.