Convenient use of legacy software in Java with Janet package

This paper describes Janet package — highly expressive Java language extension that enables convenient creation of powerful native methods and efficient Java-to-native code interfaces. Java native interface (JNI) is a low-level API that is rather inconvenient if used directly. Therefore Janet, as the higher-level tool, combines flexibility of JNI with Java’s ease-of-use. Performance results of Janet-generated interface to the lip library are shown. Java code, which uses lip, is compared with native C implementation.     

Bayanihan: building and studying web-based volunteer computing systems using Java

Project Bayanihan is developing the idea of volunteer computing, which seeks to enable people to form very large parallel computing networks very quickly by using ubiquitous and easy-to-use technologies such as web browsers and Java. By utilizing Java’s object-oriented features, we have built a flexible software framework that makes it easy for programmers to write different volunteer computing applications, while allowing researchers to study and develop the underlying mechanisms behind them. In this paper, we show how we have used this framework to write master-worker style applications, and to develop approaches to the problems of programming interface, adaptive parallelism, fault-tolerance, computational security, scalability, and user interface design.     

Theories with self-application and computational complexity

Applicative theories form the basis of Feferman’s systems of explicit mathematics, which have been introduced in the 1970s. In an applicative universe, all individuals may be thought of as operations, which can freely be applied to each other: self-application is meaningful, but not necessarily total. It has turned out that theories with self-application provide a natural setting for studying notions of abstract computability, especially from a proof-theoretic perspective. This paper is concerned with the study of (unramified) bounded applicative theories which have a strong relationship to classes of computational complexity. We propose new applicative systems whose provably total functions coincide with the functions computable in polynomial time, polynomial space, polynomial time and linear space, as well as linear space. Our theories can be regarded as applicative analogues of traditional systems of bounded arithmetic. We are also interested in higher-type features of our systems; in particular, it is shown that Cook and Urquhart’s system is directly contained in a natural applicative theory of polynomial strength.     

Family of Ternary Arithmetic Polynomial Expansions Based on New Transforms

New classes of Linearly Independent Ternary Arithmetic (LITA) transforms being the bases of ternary arithmetic polynomial expansions are introduced here. Recursive equations defining the LITA transforms and the corresponding butterfly diagrams are shown. Various properties and relations between introduced classes of new transforms are discussed. Computational costs to calculate LITA transforms and applications of corresponding polynomial expansions in logic design are also discussed.     

Symbolic–numeric sparse interpolation of multivariate polynomials

We consider the problem of sparse interpolation of an approximate multivariate black-box polynomial in floating point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give efficient and numerically robust solutions. We note the similarity between the exact Ben-Or/Tiwari sparse interpolation algorithm and the classical Prony’s method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony’s method. We analyse the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques in practice through numerical experiments and applications.     

Simultaneous modular reduction and Kronecker substitution for small finite fields

We present algorithms to perform modular polynomial multiplication or a modular dot product efficiently in a single machine word. We use a combination of techniques. Polynomials are packed into integers by Kronecker substitution; several modular operations are performed at once with machine integer or floating point arithmetic; normalization of modular images is avoided when possible; some conversions back to polynomial coefficients are avoided; the coefficients are recovered efficiently by preparing them before conversion. We discuss precisely the required control on sizes and degrees. We then present applications to polynomial multiplication, prime field linear algebra and small extension field arithmetic, where these techniques lead to practical gains of quite large constant factors.     

Methods and guidelines for the design and development of domestic ubiquitous computing applications

Bringing ubiquitous computing applications to home environments is a great challenge. In our research we investigate how applications can be conceived, designed and implemented in such a way that they fit into people’s lives. We describe our experiments on how methods of user centred design and participatory design can be appropriated to elicit users’ requirements and design ideas for ubiquitous computing applications for the home. In particular we report on a study on information presentation using display appliances. In a participatory design process enhanced with technology probes, we individually discussed potential solutions for specific homes with 14 people. Each of the resulting solutions is tailored to suit a single person. For each of these individual solutions we specified prototypes that would accommodate the user’s needs but are generic in its applicability at the same time. Based on this we derived a first set of guidelines for the design of display appliances in the home environment.     

The design of the Boost interval arithmetic library

We present the design of the Boost interval arithmetic library, a C++$++$ library designed to handle mathematical intervals efficiently and in a generic way. Interval computations are an essential tool for reliable computing. Increasingly a number of mathematical proofs have relied on global optimization problems solved using branch-and-bound algorithms with interval computations; it is therefore extremely important to have a mathematically correct implementation of interval arithmetic. Various implementations exist with diverse semantics. Our design is unique in that it uses policies to specify three independent variable behaviors: rounding, checking, and comparisons. As a result, with the proper policies, our interval library is able to emulate almost any of the specialized libraries available for interval arithmetic, without any loss of performance nor sacrificing the ease of use. This library is openly available at www.boost.org.     

Derivative Free Inclusion Methods for Polynomial Zeros

Two iterative methods for the simultaneous inclusion of complex zeros of a polynomial are presented. Both methods are realized in circular interval arithmetic and do not use polynomial derivatives. The first method of the fourth order is composed as a combination of interval methods with the order of convergence two and three. The second method is constructed using double application of the inclusion method of Weierstrass’ type in serial mode. It is shown that its R-order of convergence is bounded below by the spectral radius of the corresponding matrix. Numerical examples illustrate the convergence rate of the presented methods     

Simultaneous calculation of several conjunction terms for generalized polynomial forms of Boolean functions

An algorithm for the simultaneous calculation of several conjunction terms of the Zhegalkin (Reed-Muller) polynomial with fixed polarity and an arithmetic polynomial on the same set of variables is proposed. The performance evaluation of the proposed algorithm is presented. An example of the simultaneous calculation of the arithmetic polynomial’s terms is described to demonstrate an increase in the calculation performance.     

Modeling Combinational Circuits Using Linear Word-level Structures

In many applications of circuit design and synthesis, it is natural and in some instances essential to manipulate logic functions and model circuits using word-level representations and arithmetic operations in contrast to bit-level representations and logic operations. This paper reviews linear word-level structures and formulates their properties for combinational circuit modeling. The paper addresses the following problem: given a library of gates with their corresponding word-level representations such as linear arithmetic expressions or respective graph structures, find a word-level model of an arbitrary combinational circuit/netlist using that library of gates and minimizing memory allocation and time delay requirements. We present a comprehensive study on linearization assuming various circuit processing strategies. In particular, we develop a new approach to manipulate linear word-level representations by means of cascades. The practical applicability of linear structures and developed algorithms is strengthen by considering the problem of timing analysis. All this is supported by the experimental study on benchmark circuits.     

有限域的算术软件及其编码密码应用

利用有限域的多项式基表示法研制了有限域的算术软件.给出了有限域上[n,k]-循环码存在的充要条件以及新的编码算法与编码软件.讨论了有限域的算术软件在非线性扩频码设计和现代密码设计中的应用.     

On construction of a library of formally verified low-level arithmetic functions

Arithmetic functions are used in many important computer programs such as computer algebra systems and cryptographic software. The latter are critical applications whose correct implementation deserves to be formally guaranteed. They are also computation-intensive applications, so that programmers often resort to low-level assembly code to implement arithmetic functions. We propose an approach for the construction of a library of formally verified low-level arithmetic functions. To build our library, we first introduce a formalization of data structures for signed multi-precision arithmetic in low-level programs. We use this formalization to verify the implementation of several primitive arithmetic functions using Separation logic, an extension of Hoare logic to deal with pointers. Since this direct style of formal verification leads to technically involved specifications, we also propose for larger functions to show a formal simulation relation between pseudo-code and assembly. This style of verification is illustrated with a concrete implementation of the binary extended gcd algorithm.     

基于OpenCV的摄像机标定

以增强现实系统中摄像机标定技术为研究对象,分析了开放计算机视觉函数库OpenCV中的摄像机模型,特别充分考虑了透镜的径向畸变和切向畸变影响及求解方法,给出了基于OpenCV的摄像机标定算法.该算法充分发挥了OpenCV的函数库功能,提高了标定精度和计算效率,具有良好的跨平台移植性,可以满足增强现实和其它计算机视觉系统的需要.     

Exact rotation-minimizing frames for spatial Pythagorean-hodograph curves

An exact specification of the rotation-minimizing frame on a spatial Pythagorean-hodograph (PH) curve can be derived by integration of a rational function. The result is an angular function θ(t) of the curve parameter, comprising in general both rational and logarithmic terms, that specifies the orientation of the rotation-minimizing frame relative to the Frenet frame. For PH cubics and quintics, the solution employs only arithmetic operations on the curve coefficients and some complex square and cube root extractions. Moreover, the generalization to PH curves of arbitrary order entails only standard polynomial algorithms (i.e., arithmetic, greatest common divisors, and resultants), solution of a linear system, and a minimal element of polynomial root-solving. Rotation-minimizing frames are employed in computer animation, the construction of swept surfaces, and in robotics applications where the axis of a tool or probe should remain tangential to a given spatial path while minimizing changes of orientation about this axis.     

The amended DSeSC power method for polynomial root-finding

Cardinal's matrix version of the Sebastiao e Silva polynomial root-finder rapidly approximates the roots as the eigenvalues of the associated Frobenius matrix. We preserve rapid convergence to the roots but amend the algorithm to allow input polynomials with multiple roots and root clusters. As in Cardinal's algorithm, we repeatedly square the Frobenius matrix in nearly linear arithmetic time per squaring, which yields dramatic speedup versus the recent effective polynomial root-finder based on the application of the inverse power method to the Frobenius matrix.     

A generic lazy evaluation scheme for exact geometric computations

We present a generic C++ design to perform exact geometric computations efficiently using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms. Their efficiency is also important for many applications, hence the need for delaying the costly exact computations at run time until they are actually needed, if at all. Our approach is generic and extensible in the sense that it is possible to make it a library that users can apply to their own geometric objects and primitives. It involves techniques such as generic functor-adaptors, static and dynamic polymorphism, reference counting for the management of directed acyclic graphs, and exception handling for triggering exact computations when needed. It also relies on multi-precision arithmetic as well as interval arithmetic. We apply our approach to the whole geometry kernel of Cgal.     

Incremental Polygon Rendering on a SIMD Processor Array

We demonstrate how both area coherence and parallelism can be exploited in order to speed up rendering operations on a SIMD square array of processors. Our algorithms take advantage of the method of differences, in order to incrementally compute the values of a linear polynomial function at discrete intervals and thus implement area rendering operations efficiently. We discuss how filling of convex polygons, hidden surface elimination and smooth shading can be implemented on an N × N processor array that supports planar arithmetic, that is, arithmetic operations performed on N × N matrices in parallel for all matrix elements. A major attraction of the method we present is that it is based on a SIMD processor array; such machines are now recognised as highly general purpose given the wide range of applications successfully implemented on them.     

The root and Bell’s disk iteration methods are of the same error propagation characteristics in the simultaneous determination of the zeros of a polynomial,Part II: Round-off error analysis by use of interval arithmetic

In Part I (Ikhile, 2008) [4], it was established that the root and Bell’s disk/point iteration methods with or without correction term are of the same asymptotic error propagation characteristics in the simultaneous determination of the zeros of a polynomial. This concluding part of the investigation is a study in round-offs, its propagation and its effects on convergence employing interval arithmetic means. The purpose is to consequently draw attention on the effects of round-off errors introduced from the point arithmetic part, on the rate of convergence of the generalized root and Bell’s simultaneous interval iteration algorithms and its enhanced modifications introduced in Part I for the numerical inclusion of all the zeros of a polynomial simultaneously. The motivation for studying the effects of round-off error propagation comes from the fact that the readily available computing devices at the moment are limited in precision, more so that accuracy expected from some programming or computing environments or from these numerical methods are or can be machine dependent. In fact, a part of the finding is that round-off propagation effects beyond a certain controllable order induces overwhelmingly delayed or even a severely retarded convergence speed which manifest glaringly as poor accuracy of these interval iteration methods in the computation of the zeros of a polynomial simultaneously. However, in this present consideration and even in the presence of overwhelming influence of round-offs, we give conditions under which convergence is still possible and derive the error/round-off relations along with the order/$R$-order of convergence of these methods with the results extended to similar interval iteration methods for computing the zeros of a polynomial simultaneously, especially to Bell’s interval methods for refinement of zeros that form a cluster. Our findings are instructive and quite revealing and supported by evidence from numerical experiments. The analysis is preferred in circular interval arithmetic.