Issues and challenges in orbital-free density functional calculations

Solving the Euler equation which corresponds to the energy minimum of a density functional expressed in orbital-free form involves related but distinct computational challenges. One is the choice between all-electron and pseudopotential calculations and, if the latter, construction of the pseudopotential. Another is the stability, speed, and accuracy of solution algorithms. Underlying both is the fundamental issue of satisfactory quality of the approximate functionals (kinetic energy and exchange–correlation). We address both computational issues and illustrate them by some comparative performance testing of our recently developed modified-conjoint generalized gradient approximation kinetic energy functionals. Comparisons are given for atoms, diatomic molecules, and some simple solids.     

Quickstep: Fast and accurate density functional calculations using a mixed Gaussian and plane waves approach

We present the Gaussian and plane waves (GPW) method and its implementation in Quickstep which is part of the freely available program package CP2K. The GPW method allows for accurate density functional calculations in gas and condensed phases and can be effectively used for molecular dynamics simulations. We show how derivatives of the GPW energy functional, namely ionic forces and the Kohn-Sham matrix, can be computed in a consistent way. The computational cost of computing the total energy and the Kohn-Sham matrix is scaling linearly with the system size, even for condensed phase systems of just a few tens of atoms. The efficiency of the method allows for the use of large Gaussian basis sets for systems up to 3000 atoms, and we illustrate the accuracy of the method for various basis sets in gas and condensed phases. Agreement with basis set free calculations for single molecules and plane wave based calculations in the condensed phase is excellent. Wave function optimisation with the orbital transformation technique leads to good parallel performance, and outperforms traditional diagonalisation methods. Energy conserving Born-Oppenheimer dynamics can be performed, and a highly efficient scheme is obtained using an extrapolation of the density matrix. We illustrate these findings with calculations using commodity PCs as well as supercomputers.     

Efficient multi-scale computation of products of orbitals in electronic structure calculations

The computation of two-electron integrals in electronic structure calculations is a major bottleneck in Hartree-Fock, density functional theory and post-Hartree-Fock methods. For large systems, one has to compute a huge number of two-electron integrals for these methods which leads to very high computational costs. The adaptive computation of products of orbitals in wavelet bases provides an important step towards efficient algorithms for the treatment of two-electron integrals in tensor product formats. For this, we use the non-standard approach of Beylkin which avoids explicit coupling between different resolution levels. We tested the efficiency of the algorithm for the products of orbitals in Daubechies wavelet bases and computed the two-electron integrals. This paper contains the detailed procedure and corresponding error analysis.     

Parallel solution of partial symmetric eigenvalue problems from electronic structure calculations

The computation of selected eigenvalues and eigenvectors of a symmetric (Hermitian) matrix is an important subtask in many contexts, for example in electronic structure calculations. If a significant portion of the eigensystem is required then typically direct eigensolvers are used. The central three steps are: reduce the matrix to tridiagonal form, compute the eigenpairs of the tridiagonal matrix, and transform the eigenvectors back. To better utilize memory hierarchies, the reduction may be effected in two stages: full to banded, and banded to tridiagonal. Then the back transformation of the eigenvectors also involves two stages. For large problems, the eigensystem calculations can be the computational bottleneck, in particular with large numbers of processors. In this paper we discuss variants of the tridiagonal-to-banded back transformation, improving the parallel efficiency for large numbers of processors as well as the per-processor utilization. We also modify the divide-and-conquer algorithm for symmetric tridiagonal matrices such that it can compute a subset of the eigenpairs at reduced cost. The effectiveness of our modifications is demonstrated with numerical experiments.     

Performance of computationally intensive parameter sweep applications on Internet‐based Grids of computers: the mapping of molecular potential energy hypersurfaces

This work focuses on the use of computational Grids for processing the large set of jobs arising in parameter sweep applications. In particular, we tackle the mapping of molecular potential energy hypersurfaces. For computationally intensive parameter sweep problems, performance models are developed to compare the parallel computation in a multiprocessor system with the computation on an Internet‐based Grid of computers. We find that the relative performance of the Grid approach increases with the number of processors, being independent of the number of jobs. The experimental data, obtained using electronic structure calculations, fit the proposed performance expressions accurately. To automate the mapping of potential energy hypersurfaces, an application based on GRID superscalar is developed. It is tested on the prototypical case of the internal dynamics of acetone. Copyright © 2006 John Wiley & Sons, Ltd.     

Improving the scalability of a symmetric iterative eigensolver for multi‐core platforms

We describe an efficient and scalable symmetric iterative eigensolver developed for distributed memory multi‐core platforms. We achieve over 80% parallel efficiency by major reductions in communication overheads for the sparse matrix‐vector multiplication and basis orthogonalization tasks. We show that the scalability of the solver is significantly improved compared to an earlier version, after we carefully reorganize the computational tasks and map them to processing units in a way that exploits the network topology. We discuss the advantage of using a hybrid OpenMP/MPI programming model to implement such a solver. We also present strategies for hiding communication on a multi‐core platform. We demonstrate the effectiveness of these techniques by reporting the performance improvements achieved when we apply our solver to large‐scale eigenvalue problems arising in nuclear structure calculations. Because sparse matrix‐vector multiplication and inner product computation constitute the main kernels in most iterative methods, our ideas are applicable in general to the solution of problems involving large‐scale symmetric sparse matrices with irregular sparsity patterns. Copyright © 2013 John Wiley & Sons, Ltd.     

Enhanced Van der Waals calculations in genetic algorithms for protein structure prediction

Several ab initio computational methods for protein structure prediction have been designed using full‐atom models and force field potentials to describe interactions among atoms. Those methods involve the solution of a combinatorial problem with a huge search space. Genetic algorithms (GAs) have shown significant performance increases for such methods. However, even a small protein may require hundreds of thousands of energy function evaluations making GAs suitable only for the prediction of very small proteins. We propose an efficient technique to compute the van der Waals energy (the greatest contributor to protein stability) speeding up the whole GA. First, we developed a Cell‐List Reconstruction procedure that divides the tridimensional space into a cell grid for each new structure that the GA generates. The cells restrict the calculations of van der Waals potentials to ranges in which they are significant, reducing the complexity of such calculations from quadratic to linear. Moreover, the proposal also uses the structure of the cell grid to parallelize the computation of the van der Waals energy, achieving additional speedup. The results have shown a significant reduction in the run time required by a GA. For example, the run time for the prediction of a protein with 147,980 atoms can be reduced from 217 days to 7 h. Copyright © 2012 John Wiley & Sons, Ltd.     

Efficient computation algorithm for dynamic modelling of tree structure robot arms

This paper presents an efficient dynamic analysis of tree structure robot arms. The computational approach used is based on Lagrange equations of motion. The Topological Structure matrix {TSM [ε]} completely describes the robot arm structure. This matrix plays an important role in this analysis. The separation of the link's geometry from the joint's motion is necessary for the systematization of such a procedure. The computation procedure is efficiently organized in order to produce the smallest possible computation time. An example of a 7-link robot arm with two end-effectors is presented to clarify the computation steps leading to the dynamic model of any tree structure robot arm. This analysis can be easily applied to simple chain robot arms considered as a special case of the tree structure type.     

Broadband slat noise prediction based on CAA and stochastic sound sources from a fast random particle-mesh (RPM) method

The application of a low-cost computational aeroacoustics (CAA) approach to a slat noise problem is studied. A fast and efficient stochastic method is introduced to model the unsteady turbulent sound sources in the slat-cove of a high-lift airfoil. It is based on the spatial convolution of spatiotemporal white-noise and can reproduce target distributions of turbulence kinetic energy and length scales, such as that provided by a RANS computation of the time-averaged turbulent flow problem. The computational method yields a perfectly solenoidal velocity field. For homogeneous isotropic turbulence, the complete second-order two-point velocity correlation tensor is realized exactly. Two RANS turbulence models are applied to the slat noise problem to study how sensitive the aeroacoustics predictions depend on turbulence kinetic energy predictions. Results for the sound generation at the slat are given for a Menter SST turbulence model with and without Kato-Launder modification. The aeroacoustic simulations yield a characteristic narrow band spectrum that compares very well with the experimental data. The directivities found point toward an edge noise mechanism at the slat as the main cause for slat noise sound generation.     

EGGS: Sparsity-Specific Code Generation

Sparse matrix computations are among the most important computational patterns, commonly used in geometry processing, physical simulation, graph algorithms, and other situations where sparse data arises. In many cases, the structure of a sparse matrix is known a priori, but the values may change or depend on inputs to the algorithm. We propose a new methodology for compile-time specialization of algorithms relying on mixing sparse and dense linear algebra operations, using an extension to the widely-used open source Eigen package. In contrast to library approaches optimizing individual building blocks of a computation (such as sparse matrix product), we generate reusable sparsity-specific implementations for a given algorithm, utilizing vector intrinsics and reducing unnecessary scanning through matrix structures. We demonstrate the effectiveness of our technique on a benchmark of artificial expressions to quantitatively evaluate the benefit of our approach over the state-of-the-art library Intel MKL. To further demonstrate the practical applicability of our technique we show that our technique can improve performance, with minimal code changes, for mesh smoothing, mesh parametrization, volumetric deformation, optical flow, and computation of the Laplace operator.     

Computation of functions of Hamiltonian and skew-symmetric matrices

In this paper we consider numerical methods for computing functions of matrices being Hamiltonian and skew-symmetric. Analytic functions of this kind of matrices (i.e., exponential and rational functions) appear in the numerical solutions of ortho-symplectic matrix differential systems when geometric integrators are involved. The main idea underlying the presented techniques is to exploit the special block structure of a Hamiltonian and skew-symmetric matrix to gain a cheaper computation of the functions. First, we will consider an approach based on the numerical solution of structured linear systems and then another one based on the Schur decomposition of the matrix. Splitting techniques are also considered in order to reduce the computational cost. Several numerical tests and comparison examples are shown.     

Dielectric polarization in axially-symmetric nanostructures: A computational approach

A computational scheme to evaluate exactly the effects of the dielectric mismatch in semiconductor nanostructures with axial symmetry is presented. It is based on the numerical computation of the image charges induced by the carriers at the dielectric interface. Strategies enabling an efficient convergence in the calculation of the self-polarization potential are detailed. Illustrative calculations on exciton and image potential states properties of semiconductor nanorods reveal the need of the developed tool. We show that, contrary to spherical nanostructure geometries, the optical band gap of nanorods is blueshifted as the dielectric constant of the surrounding medium decreases. As for image potential states, we find a strongly anisotropic distribution of the surface electron density, which is a consequence of the variable curvature of the dielectric interface.     

Calculation of turbulent three-dimensional jet induced flow in rectangular enclosures

Numerical calculations are presented for two jet induced three-dimensional flows in rectangular enclosures. The computation method uses the three velocity components and pressure as primary variables. Turbulence is modeled by a two-equation model, which incorporates governing equations for kinetic energy of turbulence and its rate dissipation. Results are compared with available velocity data. Comparisons between measured and predicted results are in general good, although some discrepancies are found. Predicted fields of both mean and isotropic turbulence velocities are shown for both cases.     

基于目标函数的模糊模型一体化建模

基于模糊集合的模糊模型, 利用模糊推理规则描述复杂、病态、非线性系统是一种有效方法. 本文提出了利用目标函数确定非线性系统的结构和参数的方法. 首先, 通过Gustafson-Kessel(GK)模糊聚类确定模型结构. 然后, 通过目标函数与参数估计一起进行递推计算, 进而实现对模糊模型结构简化, 删除冗余规则. 结构确定过程中采用了UD矩阵分解方法, 大大降低了计算量. 仿真结果证明了提出方法的有效性.     

Numerical approaches to the kinetic semiconductor equation

In this paper we consider several methods for the numerical computation of carrier transport effects in semiconductors based on kinetic equations. We especially discuss the computational costs of the different algorithms, which in some cases prohibit their application to higher dimensional problems.     

Secure outsourcing of large matrix determinant computation

Cloud computing provides the capability to connect resource-constrained clients with a centralized and shared pool of resources, such as computational power and storage on demand. Large matrix determinant computation is almost ubiquitous in computer science and requires largescale data computation. Currently, techniques for securely outsourcing matrix determinant computations to untrusted servers are of utmost importance, and they have practical value as well as theoretical significance for the scientific community. In this study, we propose a secure outsourcing method for large matrix determinant computation. We employ some transformations for privacy protection based on the original matrix, including permutation and mix-row/mixcolumn operations, before sending the target matrix to the cloud. The results returned from the cloud need to be decrypted and verified to obtain the correct determinant. In comparison with previously proposed algorithms, our new algorithm achieves a higher security levelwith greater cloud efficiency. The experimental results demonstrate the efficiency and effectiveness of our algorithm.     

A new inverse kinematics algorithm for binary manipulators with many actuators

In this paper we present a new, and extremely fast, algorithm for the inverse kinematics of discretely actuated manipulator arms with many degrees of freedom. Our only assumption is that the arm is macroscopically serial in structure, meaning that the overall structure is a serial cascade of units with each unit having either a serial or parallel kinematic structure. Our algorithm builds on previous works in which the authors and coworkers have used the workspace density function in a breadthfirst search for solving the inverse kinematics problem. The novelty of the method presented here is that only the 'mean' of this workspace density function is used. Hence the requirement of storing a sampled version of the workspace density function (which is a function on a six-dimensional space in the case of a spatial manipulator) is circumvented. We illustrate the technique with both planar revolute and variable-geometry-truss manipulators, and briefly describe a new manipulator design for which this algorithm is applicable.     

Computing urban radiation: A sparse matrix approach

Cities numerical simulation including physical phenomena generates highly complex computational challenges. In this paper, we focus on the radiation exchange simulation on an urban scale, considering different types of cities. Observing that the matrix representing the view factors between buildings is sparse, we propose a new numerical model for radiation computation. This solution is based on the radiosity method. We show that the radiosity matrix associated with models composed of up to 140k patches can be stored in main memory, providing a promising avenue for further research. Moreover, a new technique is proposed for estimating the inverse of the radiosity matrix, accelerating the computation of radiation exchange. These techniques could help to consider the characteristics of the environment in building design, as well as assessing in the definition of city regulations related to urban construction.     

GPU加速在第一性原理输运研究中的应用

分子器件中的第一性原理输运计算比普通的密度泛函计算要慢很多,其最根本原因在于密度矩阵计算方法的不同。本文将 GPU 加速应用于第一性原理的输运计算,重点实现相关矩阵运算的加速。测试结果表明,在单次迭代中,对于较大的体系,相对于调用 MKL 库,密度矩阵的运算速度在单个 Tesla M2090 可以提高一个数量级以上,在 Tesla K20m 上则可以提高 20 倍以上,从而取得了很好的加速效果,而且体系越大,加速效果越好。     

云计算环境下安全的极限学习机外包机制

应用程序中涉及到的数据日益扩大且结构日益复杂,使得在大规模数据上运行极限学习机ELM成为一个具有挑战性的任务。为了应对这一挑战,提出了一个在云计算环境下安全和实用的ELM外包机制。该机制将ELM显式地分为私有部分和公有部分,可以有效地减少训练时间,并确保算法输入与输出的安全性。私有部分主要负责随机参数的生成和一些简单的矩阵计算;公有部分外包到云计算服务器中,由云计算服务商负责ELM算法中计算量最大的计算Moore-Penrose广义逆的操作。该广义逆也作为证据以验证结果的正确性和可靠性。我们从理论上对该外包机制的安全性进行了分析。在CIFAR-10数据集上的实验结果表明,我们所提出的机制可以有效地减少用户的计算量。