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.     

GPU parallelization of the sequential matrix diagonalization algorithm and its application to high-dimensional data

This paper presents the parallelization on a GPU of the sequential matrix diagonalization (SMD) algorithm, a method for diagonalizing polynomial covariance matrices, which is the most recent technique for polynomial eigenvalue decomposition. We first parallelize with CUDA the calculation of the polynomial covariance matrix. Then, following a formal transformation of the polynomial matrix multiplication code—extensively used by SMD—we insert in this code the cublasDgemm function of CUBLAS library. Furthermore, a specialized cache memory system is implemented within the GPU to greatly limit the PC-to-GPU transfers of slices of polynomial matrices. The resulting SMD code can be applied efficiently over high-dimensional data. The proposed method is verified using sequences of images of airplanes with varying spatial orientation. The performance of the parallel codes for polynomial covariance matrix generation and SMD is evaluated and reveals speedups of up to 161 and 67, respectively, relative to sequential execution on a PC.     

Semi-tensor product of matrices and its application to Morgen's problem

This paper proposes a new matrix product, namely, semi-tensor product. It is a general-ization of the conventional matrix product. Meanwhile, it is also closely related to Kronecker (tensor) product of matrices. The purpose of introducing this product is twofold: (i) treat multi-dimensional da-ta; (ii) treat nonlinear problems in a linear way. Then the computer and numerical methods can be easily used for solving nonlinear problems. Properties and formulas are deduced. As an application, the Morgan's problem for control systems is formulated as a numerically solvable problem.     

On 'infinite basis set limits' in molecular electronic structure calculations

Sequences of basis sets can be constructed so as to approach the 'infinite basis set limit' in molecular electronic structure calculations. Extrapolation procedures can also be devized to provide accurate values of this limit. However, some care is required since the 'infinite basis set limit' may not correspond to the limit supported by a complete basis set. Extrapolation procedures can then lead to limiting values, which are not estimates of the exact solutions.     

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.     

Efficient first-principles calculations of the electronic structure of periodic systems

We have recently presented a real-space method for electronic-structure calculations of periodic systems that is based on the Hohenberg-Kohn-Sham density-functional theory. The method allows the computation of electronic properties of periodic systems in the spirit of traditional plane-wave approaches. In addition, it can be implemented efficiently on parallel computers. Here we will show that the method's inherent parallelism, in conjunction with a newly designed approach for solving the Kohn-Sham equations, enables the accurate study of the ionic and electronic properties of periodic systems containing thousands of atoms from first principles.     

Iterative lavrentiev regularization for symmetric kernel-driven operator equations: with application to digital image restoration problems

~~Iterative Lavrentiev regularization for symmetric kernel-driven operator equations: with application to digital image restoration problems1. Roggemann, M. C, WeJsh, B., Imaging Through Turbulence. New York. CRC Press, 1996. 2. Bertero, M., Boccacci, P., Introduction to Inverse Prolems in Imaging, Bristol: IOP Publishing, 1998. 3. George, S., Nair, M. T., A class of discrepancy principles for the simplified regularization of ill-posed problems, J. Austral. Math. Soc, Ser.…     

电子签章技术及其在网络电子合同中的应用研究

随着互联网的普及和信息技术的进展,基于网上交易的电子商务模式已经逐渐取代传统的交易方式,对于网络交易双方来说,如何确认对方的身份真实可信,如何确认对方发来的电子合同真实有效是一个首要解决的关键问题。随着我国电子签名法的正式实施,贸易双方通过基于数字签名的电子印章技术,在电子合同上通过加盖电子印章,可很好解决交易双方的身份验证和电子合同有效性的确认问题。本文结合网上贸易的具体应用需求,提出了一种基于第三方的面向网上贸易的电子签章模式,并对关键技术进行了讨论。     

Iterative inversion of neural networks and its application toadaptive control

An iterative constrained inversion technique is used to find the control inputs to the plant. That is, rather than training a controller network and placing this network directly in the feedback or feedforward paths, the forward model of the plant is learned, and iterative inversion is performed on line to generate control commands. The control approach allows the controllers to respond online to changes in the plant dynamics. This approach also attempts to avoid the difficulty of analysis introduced by most current neural network controllers, which place the highly nonlinear neural network directly in the feedback path. A neural network-based model reference adaptive controller is also proposed for systems having significant dynamics between the control inputs and the observed (or desired) outputs and is demonstrated on a simple linear control system. These results are interpreted in terms of the need for a dither signal for on-line identification of dynamic systems.     

Very large scale wavefunction orthogonalization in Density Functional Theory electronic structure calculations

Enforcing the orthogonality of approximate wavefunctions becomes one of the dominant computational kernels in planewave based Density Functional Theory electronic structure calculations that involve thousands of atoms. In this context, algorithms that enjoy both excellent scalability and single processor performance properties are much needed. In this paper we present block versions of the Gram-Schmidt method and we show that they are excellent candidates for our purposes. We compare the new approach with the state of the art practice in planewave based calculations and find that it has much to offer, especially when applied on massively parallel supercomputers such as the IBM Blue Gene/P Supercomputer. The new method achieves excellent sustained performance that surpasses 73 TFLOPS (67% of peak) on 8 Blue Gene/P¹ racks (32 768 compute cores), while it enables more than a two fold decrease in run time when compared with the best competing methodology.     

Fact structure and its application to updates in relational databases

We introduce the fact structure of a relation: a user defined semantic structure describing the information (called facts) represented by a tuple. We argue that regarding tuples as units of information leads to many problems in the relational model, rather, we propose facts as units of information, with tuples used to represent facts. These ideas are further refined by introducing primary facts, namely, those facts that are considered more important by a user. Then we study the problem of updates in such a fact-oriented environment, and characterize “deletable” and “nondeletable” facts, and prove that it is possible to delete deletable facts with no side effect.     

Sparse representation of precision matrices used in GMMs

The paper presents a novel precision matrix modeling technique for Gaussian Mixture Models (GMMs), which is based on the concept of sparse representation. Representation coefficients of each precision matrix (inverse covariance), as well as an accompanying overcomplete matrix dictionary, are learned by minimizing an appropriate functional, the first component of which corresponds to the sum of Kullback-Leibler (KL) divergences between the initial and the target GMM, and the second represents the sparse regularizer of the coefficients. Compared to the existing, alternative approaches for approximate GMM modeling, like popular subspace-based representation methods, the proposed model results in notably better trade-off between the representation error and the computational (memory) complexity. This is achieved under assumption that the training data in the recognition system utilizing GMM have an inherent sparseness property, which enables application of the proposed model and approximate representation using only one dictionary and a significantly smaller number of coefficients. Proposed model is experimentally compared with the Subspace Precision and Mean (SPAM) model, a state of the art instance of subspace-based representation models, using both the data from a real Automatic Speech Recognition (ASR) system, and specially designed sets of artificially created/synthetic data.     

New coprimeness over multivariable polynomial matrices and its application to control delay systems

This paper presents a new notion of coprimeness over multivariable polynomial matrices, where a single variable is given priority over the remaining variables. From a characterization through a set of common zeros of the minors, it is clarified that the presented coprimeness is equivalent to weakly zero coprimeness in the particular variable. An application of the presented coprimeness to control systems with non-commensurate delays and finite spectrum assignment is also presented. Because the presented coprimeness is stronger than minor coprimeness, non-commensurate delays are difficult to deal with in algebraic control theory. The “rational ratio condition” between delays, which can reduce non-commensurate delays to commensurate delays, proves to be both powerful and practical concept in algebraic control theory for delay systems.     

Spectral and structural properties of some pentadiagonal symmetric matrices

By using suitable bordering and modification techniques, spectral properties of some classes of pentadiagonal symmetric matrices are found.     

Characterizing and approximating eigenvalue sets of symmetric interval matrices

We consider the eigenvalue problem for the case where the input matrix is symmetric and its entries are perturbed, with perturbations belonging to some given intervals. We present a characterization of some of the exact boundary points, which allows us to introduce an inner approximation algorithm, that in many case estimates exact bounds. To our knowledge, this is the first algorithm that is able to guarantee exactness. We illustrate our approach by several examples and numerical experiments.     

Semantics of roundoff error propagation in finite precision calculations

We introduce a concrete semantics for floating-point operations which describes the propagation of roundoff errors throughout a calculation. This semantics is used to assert the correctness of a static analysis which can be straightforwardly derived from it. In our model, every elementary operation introduces a new first order error term, which is later propagated and combined with other error terms, yielding higher order error terms. The semantics is parameterized by the maximal order of error to be examined and verifies whether higher order errors actually are negligible. We consider also coarser semantics computing the contribution, to the final error, of the errors due to some intermediate computations. As a result, we obtain a family of semantics and we show that the less precise ones are abstractions of the more precise ones.     

On the transformation of symmetric sparse matrices to the triple diagonal form

The problem of minimizing the number of zero elements that become non-zero during the computation when a sparse symmetric matrix is reduced to a triple diagonal form, either by Givens' or Householder's method, is discussed. Algorithms for minimizing the growth of such non-zero elements are given.     

FEAST fundamental framework for electronic structure calculations: Reformulation and solution of the muffin-tin problem

In a recent article Polizzi (2009) [15], the FEAST algorithm has been presented as a general purpose eigenvalue solver which is ideally suited for addressing the numerical challenges in electronic structure calculations. Here, FEAST is presented beyond the “black-box” solver as a fundamental modeling framework which can naturally address the original numerical complexity of the electronic structure problem as formulated by Slater in 1937 [3]. The non-linear eigenvalue problem arising from the muffin-tin decomposition of the real-space domain is first derived and then reformulated to be solved exactly within the FEAST framework. This new framework is presented as a fundamental and practical solution for performing both accurate and scalable electronic structure calculations, bypassing the various issues of using traditional approaches such as linearization and pseudopotential techniques. A finite element implementation of this FEAST framework along with simulation results for various molecular systems is also presented and discussed.     

TCM3电子罗盘的特性与应用

电子罗盘正广泛应用于各类导航定位系统中。介绍了TCM3电子罗盘的特性,详细说明了TCM3的控制编程和航向、俯仰、横滚等参数的读取,利用TCM3和GPS组合实现在农业机器人控制平台上的导航应用。经试验测试,TCM3在农业机器人导航平台上航向精度为±1℃,能够满足大部分精准农业应用的需要。