On Graph-Based Cryptography and Symbolic Computations

We have been investigating the cryptographical properties of in nite families of simple graphs of large girth with the special colouring of vertices during the last 10 years. Such families can be used for the development of cryptographical algorithms (on symmetric or public key modes) and turbocodes in error correction theory. Only few families of simple graphs of large unbounded girth and arbitrarily large degree are known. The paper is devoted to the more general theory of directed graphs of large girth and their cryptographical applications. It contains new explicit algebraic constructions of in finite families of such graphs. We show that they can be used for the implementation of secure and very fast symmetric encryption algorithms. The symbolic computations technique allow us to create a public key mode for the encryption scheme based on algebraic graphs.

Computer-Assisted Proofs and Symbolic Computations

We discuss some main points of computer-assisted proofs based on reliable numerical computations. Such so-called self-validating numerical methods in combination with exact symbolic manipulations result in very powerful mathematical software tools. These tools allow proving mathematical statements (existence of a fixed point, of a solution of an ODE, of a zero of a continuous function, of a global minimum within a given range, etc.) using a digital computer. To validate the assertions of the underlying theorems fast finite precision arithmetic is used. The results are absolutely rigorous. To demonstrate the power of reliable symbolic-numeric computations we investigate in some details the verification of very long periodic orbits of chaotic dynamical systems. The verification is done directly in Maple, e.g. using the Maple Power Tool intpakX or, more efficiently, using the C++ class library C-XSC.

Kinematics of pantograph masts

This paper deals with the kinematics of pantograph masts. Pantograph masts have widespread use in space application as deployable structures. They are over constrained mechanisms with degree-of-freedom, evaluated by the Grübler–Kutzback formula, as less than one. In this paper, a numerical algorithm is used to evaluate the degree-of-freedom of pantograph masts by obtaining the null space of a constraint Jacobian matrix. In the process redundant joints in the masts are obtained. A method based on symbolic computation, to obtain the closed-form kinematics equations of triangular and box shaped pantograph masts, is presented. In the process, the various configurations such masts can attain during deployment, are obtained. The closed-form solution also helps in identifying the redundant joints in the masts. The symbolic computations involving the Jacobian matrix also leads to a method to evaluate the global degree-of-freedom for these masts.

Automatic Design of a Maglev Controller in State Space

We describe the automatic synthesis of a global nonlinear controller for stabilizing a magnetic levitation system. The synthesized control system can stabilize the maglev vehicle with large initial displacements from an equilibrium, and possesses a much larger operating region than the classical linear feedback design for the same system. The controller is automatically synthesized by a suite of computational tools. This work demonstrates that the difficult control synthesis task can be automated, using programs that actively exploit knowledge of nonlinear dynamics and state space and combine powerful numerical and symbolic computations with spatial-reasoning techniques.

Automatic Analysis and Synthesis of Controllers for Dynamical Systems Based On P

I present a novel design methodology for the synthesis of automatic controllers, together with a computational environment---the Control Engineer's Workbench---integrating a suite of programs that automatically analyze and design controllers for high-performance, global control of nonlinear systems. This work demonstrates that difficult control synthesis tasks can be automated, using programs that actively exploit and efficiently represent knowledge of nonlinear dynamics and phase space and effectively use the representation to guide and perform the control design. The Control Engineer's Workbench combines powerful numerical and symbolic computations with artificial intelligence reasoning techniques. As a demonstration, the Workbench automatically designed a high-quality maglev controller that outperforms a previous linear design by a factor of 20.

Use of computer algebra in the calculation of Feynman diagrams

The increasing precision of current and future experiments in high-energy physics requires a likewise increase in the accuracy of the calculation of theoretical predictions, in order to find evidence for possible deviations of the generally accepted Standard Model of elementary particles and interactions. Calculating the experimentally measurable cross sections of scattering and decay processes to a higher accuracy directly translates into including higher order radiative corrections in the calculation. The large number of particles and interactions in the full Standard Model results in an exponentially growing number of Feynman diagrams contributing to any given process in higher orders. Additionally, the appearance of multiple independent mass scales makes even the calculation of single diagrams non-trivial. For over two decades now, the only way to cope with these issues has been to rely on the assistance of computers. The aim of the xloops project is to provide the necessary tools to automate the calculation procedures as far as possible, including the generation of the contributing diagrams and the evaluation of the resulting Feynman integrals. The latter is based on the techniques developed in Mainz for solving one- and two-loop diagrams in a general and systematic way using parallel/orthogonal space methods. These techniques involve a considerable amount of symbolic computations. During the development of xloops it was found that conventional computer algebra systems were not a suitable implementation environment. For this reason, a new system called GiNaC has been created, which allows the development of large-scale symbolic applications in an object-oriented fashion within the C++ programming language. This system, which is now also in use for other projects besides xloops, is the main focus of this thesis. The implementation of GiNaC as a C++ library sets it apart from other algebraic systems. Our results prove that a highly efficient symbolic manipulator can be designed in an object-oriented way, and that having a very fine granularity of objects is also feasible. The xloops-related parts of this work consist of a new implementation, based on GiNaC, of functions for calculating one-loop Feynman integrals that already existed in the original xloops program, as well as the addition of supplementary modules belonging to the interface between the library of integral functions and the diagram generator.

Mapping dissociations in verb morphology

Substantial behavioural and neuropsychological evidence has been amassed to support the dual-route model of morphological processing, which distinguishes between a rule-based system for regular items (walk–walked, call–called) and an associative system for the irregular items (go–went). Some neural-network models attempt to explain the neuropsychological and brain-mapping dissociations in terms of single-system associative processing. We show that there are problems in the accounts of homogeneous networks in the light of recent brain-mapping evidence of systematic double-dissociation. We also examine the superior capabilities of more internally differentiated connectionist models, which, under certain conditions, display systematic double-dissociations. It appears that the more differentiation models show, the more easily they account for dissociation patterns, yet without implementing symbolic computations.

Multibody System Mechanics: Modelling, Stability, Control, and Robustness by V. A. Konoplev and A. Cheremensky

BOOK REVIEWS Multibody System Mechanics: Modelling, Stability, Control, and Ro- bustness, by V. A. Konoplev and A. Cheremensky, Mathematics and its Appli- cations Vol. 1, Union of Bulgarian Mathematicians, Sofia, 2001, XXII + 288 pp., $ 65.00, ISBN 954-8880-09-01

Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming

Irregular computations pose sorne of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures, which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. Starting in the mid 80s there has been significant progress in the development of parallelizing compilers for logic pro­gramming (and more recently, constraint programming) resulting in quite capable paralle­lizers. The typical applications of these paradigms frequently involve irregular computations, and make heavy use of dynamic data structures with pointers, since logical variables represent in practice a well-behaved form of pointers. This arguably makes the techniques used in these compilers potentially interesting. In this paper, we introduce in a tutoríal way, sorne of the problems faced by parallelizing compilers for logic and constraint programs and provide pointers to sorne of the significant progress made in the area. In particular, this work has resulted in a series of achievements in the areas of inter-procedural pointer aliasing analysis for independence detection, cost models and cost analysis, cactus-stack memory management, techniques for managing speculative and irregular computations through task granularity control and dynamic task allocation such as work-stealing schedulers), etc.

Automatic parallelization of irregular and pointer-based computations: perspectives from logic and constraint programming

Irregular computations pose some of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. In the past decade there has been significant progress in the development of parallelizing compilers for logic programming and, more recently, constraint programming. The typical applications of these paradigms frequently involve irregular computations, which arguably makes the techniques used in these compilers potentially interesting. In this paper we introduce in a tutorial way some of the problems faced by parallelizing compilers for logic and constraint programs. These include the need for inter-procedural pointer aliasing analysis for independence detection and having to manage speculative and irregular computations through task granularity control and dynamic task allocation. We also provide pointers to some of the progress made in these áreas. In the associated talk we demónstrate representatives of several generations of these parallelizing compilers.

An investigation of the social learning and symbolic interaction models for the development of self-concepts and self-esteem

Two studies were conducted to investigate empirical support for two models relating to the development of self-concepts and self-esteem in upper-primary school children. The first study investigated the social learning model by examining the relationship between mothers' and fathers' self-reported self-concepts and self-esteem and the self-reported self-concepts and self-esteem of their children. The second study investigated the symbolic interaction model by examining the relationship between children's perception of the frequency of positive and negative statements made by parents and their self-reported self-concepts and self-esteem. The results of these studies suggested that what parents say to their children and how they interact with them is more closely related to their children's self-perceptions than the role of modelling parental attitudes and behaviours. The findings highlight the benefits of parents talking positively to their children.

The experience of China-educated nurses working in Australia : a symbolic interactionist perspective

Transnational nurse migration is a growing phenomenon. However, relatively little is known about the experiences of immigrant nurses and particularly about non-English speaking background nurses who work in more economically developed countries. Informed by a symbolic interactionist framework, this research explored the experience of China-educated nurses working in the Australian health care system. Using a modified constructivist grounded theory method, the main source of data were 46 face to face in-depth interviews with 28 China-educated nurses in two major cities in Australia. The key findings of this research are fourfold. First, the core category developed in this study is reconciling different realities, which inserts a theoretical understanding beyond the concepts of acculturation, assimilation, and integration. Second, in contrast to the dominant discourse which reduces the experience of immigrant nurses to language and culture, this research concludes that it was not just about language and nor was it simply about culture. Third, rather than focus on the negative aspects of difference as in the immigration literature and in the practice of nursing, this research points to the importance of recognising the social value of difference. Finally, the prevailing view that the experience of immigrant nurses is largely negative belies its complexities. This research concludes that it is naïve to define the experience as either good or bad. Rather, ambivalence was the essential feature of the experience and a more appropriate theoretical concept. This research produced a theoretical understanding of the experience of China-educated nurses working in Australia. The findings may not only inform Chinese nurses who wish to immigrate but also contribute to the implementation of more effective support services for immigrant nurses in Australian health care organisations.

Automated symbolic and numeric procedure for manipulator rigid-body dynamic significance analysis and simplification

This paper describes an automated procedure for analysing the significance of each of the many terms in the equations of motion for a serial-link robot manipulator. Significance analysis provides insight into the rigid-body dynamic effects that are significant locally or globally in the manipulator's state space. Deleting those terms that do not contribute significantly to the total joint torque can greatly reduce the computational burden for online control, and a Monte-Carlo style simulation is used to investigate the errors thus introduced. The procedures described are a hybrid of symbolic and numeric techniques, and can be readily implemented using standard computer algebra packages.

Avoiding full extension field arithmetic in pairing computations

The most costly operations encountered in pairing computations are those that take place in the full extension field Fpk . At high levels of security, the complexity of operations in Fpk dominates the complexity of the operations that occur in the lower degree subfields. Consequently, full extension field operations have the greatest effect on the runtime of Miller’s algorithm. Many recent optimizations in the literature have focussed on improving the overall operation count by presenting new explicit formulas that reduce the number of subfield operations encountered throughout an iteration of Miller’s algorithm. Unfortunately, almost all of these improvements tend to suffer for larger embedding degrees where the expensive extension field operations far outweigh the operations in the smaller subfields. In this paper, we propose a new way of carrying out Miller’s algorithm that involves new explicit formulas which reduce the number of full extension field operations that occur in an iteration of the Miller loop, resulting in significant speed ups in most practical situations of between 5 and 30 percent.

Faster pairing computations on curves with high-degree twists

Research on efficient pairing implementation has focussed on reducing the loop length and on using high-degree twists. Existence of twists of degree larger than 2 is a very restrictive criterion but luckily constructions for pairing-friendly elliptic curves with such twists exist. In fact, Freeman, Scott and Teske showed in their overview paper that often the best known methods of constructing pairing-friendly elliptic curves over fields of large prime characteristic produce curves that admit twists of degree 3, 4 or 6. A few papers have presented explicit formulas for the doubling and the addition step in Miller’s algorithm, but the optimizations were all done for the Tate pairing with degree-2 twists, so the main usage of the high- degree twists remained incompatible with more efficient formulas. In this paper we present efficient formulas for curves with twists of degree 2, 3, 4 or 6. These formulas are significantly faster than their predecessors. We show how these faster formulas can be applied to Tate and ate pairing variants, thereby speeding up all practical suggestions for efficient pairing implementations over fields of large characteristic.