Narrow Results

In this paper, we present the implementation of the Density Functional Theory (DFT) method using the Geant4-DNA framework in the Single Instruction Single Data (SISD) mode. Furthermore, this implementation is improved in terms of execution time within the GeantV project with vectorization techniques such as Single Instruction Multiple Data (SIMD). Within this framework, a set of SIMD strategies in molecular calculation algorithms such as one-electron operators, two-electron operator, quadrature grids, and functionals, was implemented using the VecCore library. The applications developed in this work implement two DFT functionals, the Local Density Approximation (LDA) and the General Gradient Approximation (GGA), to approximate the molecular ground-state energies of small molecules and amino acids. To assess the performance of the implementations, a standard test simulation was performed in multiple CPU platforms. The SIMD vectorization strategy significantly accelerates DFT calculations, leading to time ratios ranging from 1.6 to 5.4 in either individual steps or entire implementations when compared with the scalar process within Geant4.

The ability of the existence of vectorizing compilers to extract vector instructions from blocks of sequential code does not remove the need for proper choice of software algorithms. In this paper, we study the vectorization of the insertion sorting, shellsort, and radix sortings. To measure their suitability for vectorization, we have implemented them on a Convex C-l, and computed the scalar/vector speedup for each method. We observed that for sorting methods based on compare/exchange, contingent methods often thought unsuitable for vectorization, the insertion sort is well performed, especially when using an M-section approach. And for radix sortings, the LSD methods are more suited to vectorization compared to the MSD methods. Finally, based on our study and experiments, we suggest that the straight radix sorting is a good choice for use on vector supercomputers.

An efficient implementation of a quasi-Newton algorithm for training feed-forward neural network on a Cray Y-MP is presented. The most time-consuming step of a neural network training using the quasi-Newton algorithm is the computation of the error function and its gradient. Parallelization embedded in these computations can be exploited through vectorization in a Cray Y-MP supercomputer. We show how they can be carried out such that the overall performance of the neural network training process can be enhanced substantially.

We review Schmidt and Kraus decompositions in the form of singular value decomposition using operations of reshaping, vectorization and reshuffling. We use the introduced notation to analyze the correspondence between quantum states and operations with the help of Jamiołkowski isomorphism. The presented matrix reorderings allow us to obtain simple formulae for the composition of quantum channels and partial operations used in quantum information theory. To provide examples of the discussed operations, we utilize a package for the Mathematica computing system implementing basic functions used in the calculations related to quantum information theory.

We present a vector-friendly blocked computing strategy for the lattice Boltzmann method (LBM). This strategy, along with a recently developed data structure, Structure of Arrays of Structures (SoAoS), is implemented for multi-relaxation type lattice Boltzmann (LB). The proposed methodology enables optimal memory bandwidth utilization in the advection step and high compute efficiency in the collision step of LB implementation. In a dense computing environment, current performance optimization framework for LBM is able to achieve high single-core efficiency.

Coherent effects of ultra-relativistic particles in crystals is an area of science under development. DYNECHARM + + is a toolkit for the simulation of coherent interactions between high-energy charged particles and complex crystal structures. The particle trajectory in a crystal is computed through numerical integration of the equation of motion. The code was revised and improved in order to exploit parallelization on multi-cores and vectorization of single instructions on multiple data. An Intel Xeon Phi card was adopted for the performance measurements. The computation time was proved to scale linearly as a function of the number of physical and virtual cores. By enabling the auto-vectorization flag of the compiler a three time speedup was obtained. The performances of the card were compared to the Dual Xeon ones.

The model of de Boer, Segel and Perelson, where the various shapes of antibodies are represented by sites on a d-dimensional lattice and where the antibody concentrations change with time only by constant factors, is simulated in one to ten dimensions, with millions of sites. The algorithm is fully vectorized in spite of the many if-conditions which allow one program to deal with all dimensions d. We find that an initially localized perturbation may spread over the whole lattice in high dimensions but prefers to remain localized in low dimensions.

We report on a lattice based algorithm, completely vectorized for molecular dynamics simulations. Its algorithmic complexity is of the order O(N), where N is the number of particles. The algorithm works very effectively when the particles have short range interaction, but it is applicable to each kind of interaction. The code was tested on a CRAY YMP EL in a simulation of flowing granular material.

A comparison between single-cluster and single-spin algorithms is made for the Ising model in 2 and 3 dimensions. We compare the amount of computer time needed to achieve a given level of statistical accuracy, rather than the speed in terms of site updates per second or the dynamical critical exponents. Our main result is that the cluster algorithms become more efficient when the system size, L^d, exceeds, L~70–300 for d=2 and l~80–200 for d=3. The exact value of the crossover is dependent upon the computer being used. The lower end of the crossover range is typical of workstations while the higher end is typical of vector computers. Hence, even for workstations, the system sizes needed for efficient use of the cluster algorithm is relatively large.

Recognition of engineering drawing entities is one of the most difficult stages in engineering drawing interpretation and many attempts to recognize various types of ED entities have been made. In this paper, we review algorithms for the recognition of ED entities, especially dimensions and crosshatching areas. For the recognition of dimensions, we analyze how dimension texts can be separated from graphics and how arrowheads of dimension lines are recognized. We also analyze the recent systems of ED interpretation. Finally, future tasks are discussed.

We propose an algorithm for creating line graphs from binary images. The algorithm consists of a vectorizer followed by a line detector that can handle a large variety of binary images and is tolerant to noise. The proposed algorithm can accurately extract higher-level geometry from the images lending itself well to automatic image recognition tasks. Our algorithm revisits the technique of image polygonization proposing a very robust variant based on subpixel resolution and the construction of directed paths along the center of the border pixels where each pixel can correspond to multiple nodes along one path. The algorithm has been used in the areas of chemical structure and musical score recognition and is available for testing at www.docnition.com. Extensive testing of the algorithm against commercial and noncommercial methods has been conducted with favorable results.

This paper deals with the efficient formulation of a three-dimensional finite element (FE) model for the dispersion of denser-than-air gases into the atmosphere. The model, which applies the k-ε turbulence model and takes into considerations the effects of heat transfer and density stratification in its mathematical formulation, requires cost-effective numerical methods in order to minimise its computer-time and memory requirements. The paper focuses on the most time-demanding step in the numerical solution, viz,. the procedure that assembles the global FE system of equations. The assembly-process has been suitably structured so as to take advantage of the vector processing capability of modern supercomputers. The possibility of using reduced, one-point quadrature for cost-effectiveness has also been investigated. Computations on a supercomputer and a PC demonstrate the success of the techniques adopted in reducing the time requirements of the model by a significant factor. The paper also reports on the model's validation against experimental data that confirms the accuracy of its transient solution.

This chapter presents a review of the results of fundamental and applied research performed by the team of authors.

The following methods and algorithms have been developed for constructive synthesis of the following:

• various orthonormal well-adapted basis functions (WABFs) that satisfy the specified properties and cover the initial set of points with a predetermined accuracy in a given metric. The process of coding reduces to calculating the expansion coefficients for these functions,
• various oblique-angle bases (smoothing (WASBFs) and restoring (WARBFs) functions). The coding of signals reduces to selecting irregularly located and smoothed with the respective WASBFs significant samples of the original signal. Decoding is carried out with the use of WARBFs,
• local homogeneous time-spaced smoothing and restoring functions (short bursts). The procedure for their synthesis is reduced to solving the multiextremal problem. On the basis of these functions, effective algorithms for adaptive compression and filtering with maximum coordinate error control have been developed. At the output of such algorithms, the signals and the information field are represented as a hierarchical set of significant samples and errors (truncated difference binary trees).

A general-to-specific method has been developed that is based on the proposed hierarchical structures for representation of 2D and 3D information and on decision-making methods for these structures. Intermediate solutions obtained in the course of processing the hierarchy upper levels can first be used as some approximation to the desired solution, and then they are used to evaluate the promising directions for continuing the search for the ultimate solution.

Correlation-extreme contour methods (CECM) for recognition of graphic objects have been developed. These methods are based on the calculation of similarity (proximity) estimates of the object and template contours and are invariant with respect to orthogonal transformations and scaling. The criteria for estimating the similarity are the root-meansquare deviation and the Hausdorff distance. CECM recognition algorithms have been implemented in two modes: learning and self-learning.

An algorithm has been developed for near-lossless compression of large-format raster graphic documents with a weakly formalized description of discrete objects and inscriptions. It is based on a two-criteria CECM algorithm with self-learning.

New intelligent information technologies and software have been developed for vectorizing such documents based on recognition methods with self-learning and computational geometry methods. All the developed algorithms’ end technologies are distinguished by novelty, low time consumption, and lowcomplexity, while coding and adaptive compression algorithms offer a high compression ratio.

Technical documents are documents of some science or engineering domain, in which graphics provide the basis for the information conveyed by the document. Engineering drawings in general and mechanical engineering drawings in particular are a typical example. The interpretation of such drawings entails converting them into some kind of CAD representation, which has a high-level meaning, including 3D structure. In this chapter, we review the different methods and techniques used to achieve this goal, which is still an active research topic. After presenting the general framework in which such a system must work, we introduce the three levels of interpretation: lexical, syntactic and semantic. We give an overview of the low- and intermediate-level tools used in this context: vectorization, recognition of arcs, hatching and dashed lines, etc. At the syntactic level, we describe the task of recognizing annotations in general and dimensioning in particular. We also elaborate on the functional analysis that is possible on each view. Finally, we describe the available techniques and the open problems for 3D reconstruction from several views.

This chapter describes aspects of methods for map interpretation. Maps are made according to rules, but this only slightly simplifies the design process of interpretation systems. This is because the same map can be drawn by different people having different styles. Also, updates on the same map can be months apart, causing aging effects. Sometimes, the rules are more obeyed, sometimes, they are less obeyed. A robust map interpretation system has to take this all into account.

In this chapter two systems for cadastral map interpretation are compared: a bottom-up system and a model-based system. The model-based system uses expectations of reality to correct and improve the interpretation. Apart from a better performance, a number of problems faced in the bottom-up system can be solved more easily in a model-based system. Also, parts of the model-based system can be re-used in an interpretation system for other types of maps.