Efficient Computation of Roots in Finite Fields

We present an algorithm to compute rth roots in $\mathbb{F}_{q^m}We present an algorithm to compute rth roots in with complexity ?[(log m + r log q) m log q] if (m,q) = 1 and either (q(q−1),r) = 1 or r|(q−1) and ((q−1)/r,r) = 1. This compares well to previously known algorithms, which need O(r m³ log³ q) steps. Paulo S. L. M. Barreto: Supported by Scopus Tecnologia S. A. José Felipe Voloch: Supported by NSA grant MDA904-03-1-0117.     

A modular integer GCD algorithm

This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC '93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111–116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111–122] when U and V are close to the same size, that replaces U by (U−bV)/p, where p is one of the prime moduli and b is the unique integer in the interval (−p/2,p/2) such that . When the algorithm is executed on a bit common CRCW PRAM with O(nlognlogloglogn) processors, it takes O(n) time in the worst case. A heuristic model of the average case yields O(n/logn) time on the same number of processors.     

Low rank approximation in G0W0 calculations

The single particle energies obtained in a Kohn-Sham density functional theory (DFT) calculation are generally known to be poor approximations to electron excitation energies that are measured in transport, tunneling and spectroscopic experiments such as photo-emission spectroscopy. The correction to these energies can be obtained from the poles of a single particle Green’s function derived from a many-body perturbation theory. From a computational perspective, the accuracy and efficiency of such an approach depends on how a self energy term that properly accounts for dynamic screening of electrons is approximated. The G₀W₀ approximation is a widely used technique in which the self energy is expressed as the convolution of a noninteracting Green’s function (G₀) and a screened Coulomb interaction (W₀) in the frequency domain. The computational cost associated with such a convolution is high due to the high complexity of evaluating W₀ at multiple frequencies. In this paper, we discuss how the cost of G₀W₀ calculation can be reduced by constructing a low rank approximation to the frequency dependent part of W₀. In particular, we examine the effect of such a low rank approximation on the accuracy of the G₀W₀ approximation. We also discuss how the numerical convolution of G₀ and W₀ can be evaluated efficiently and accurately by using a contour deformation technique with an appropriate choice of the contour.     

A Randomized Homotopy for the Hermitian Eigenpair Problem

Foundations of Computational Mathematics - We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an $$ntimes n$$ Hermitian matrix $$A$$ , the...     

Modeling Language Evolution

We describe a model for the evolution of the languages used by the agents of a society. Our main result proves convergence of these languages to a common one under certain conditions. A few special cases are elaborated in more depth.     

Grid Methods in Computational Real Algebraic (and Semialgebraic) Geometry

In recent years, a family of numerical algorithms to solve problems in real algebraic and semialgebraic geometry has been slowly growing. Unlike their counterparts in symbolic computation they are numerically stable. But their complexity analysis, based on the condition of the data, is radically different from the usual complexity analysis in symbolic computation as these numerical algorithms may run forever on a thin set of ill-posed inputs.     

Graded polynomial identities for matrices with the transpose involution over an infinite field

Let F be an infinite field and let M_n(F) be the algebra of n×n matrices over F endowed with an elementary grading whose neutral component coincides with the main diagonal. In this paper, we find a basis for the graded polynomial identities of M_n(F) with the transpose involution. Our results generalize for infinite fields of arbitrary characteristic previous results in the literature, which were obtained for the field of complex numbers and for a particular class of elementary G-gradings.