Vector coding algorithms for multidimensional discrete Fourier transform

A new fast algorithm is presented for the multidimensional discrete Fourier transform (DFT). This algorithm is derived using an interesting technique called “vector coding” (VC), and we call it the vector-coding fast Fourier transform (VC-FFT) algorithm. Since the VC-FFT is an extension of the Cooley–Tukey algorithm from 1-D to multidimensional form, the structure of the program is as simple as the Cooley–Tukey fast Fourier transform (FFT). The new algorithm significantly reduces the number of multiplications and recursive stages. The VC-FFT therefore comprehensively reduces the complexity of the algorithm as compared with other current multidimensional DFT algorithms.     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

Fast algorithms for calculation of Gibbs derivatives on finite groups

In this paper we discuss the definition of Gibbs derivatives on finite, not necessarily Abelian, groups in terms of the partial Gibbs derivatives. We consider the matrix representation of Gibbs derivatives defined in this way, which enables us to disclose FFT-like algorithms for the calculation of the values of Gibbs derivatives of functions on finite groups into fields admitting the existence of a Fourier transform on groups.     

Isomorphism of a Ring to the Endomorphism Ring of an Abelian Group

This paper presents necessary and sufficient conditions under which isomorphism of endomorphism rings of additive groups of arbitrary associative rings with 1 implies isomorphism of these rings. For a certain class of Abelian groups, we present a criterion which shows when isomorphism of their endomorphism rings implies isomorphism of these groups. We demonstrate necessary and sufficient conditions under which an arbitrary ring is the endomorphism ring of an Abelian group. This solves Problem 84 in L. Fuchs’ “Infinite Abelian Groups.”__________Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 1, pp. 231–234, 2003.     

A fast direct algorithm for implementing a high-order finite element method on rectangles as applied to boundary value problems for the Poisson equation

Fast direct and inverse algorithms for expansion in terms of eigenvectors of one-dimensional eigenvalue problems for a high-order finite element method (FEM) are proposed based on the fast discrete Fourier transform. They generalize logarithmically optimal Fourier algorithms for solving boundary value problems for Poisson-type equations on rectangular meshes to high-order FEM. The algorithms can be extended to the multidimensional case and can be applied to nonstationary problems.     

Weakly Linearly Compact Topological Abelian Groups

In this paper, we study linearly topological groups. We introduce the notion of a weakly linearly compact group, which generalizes the notion of a weakly separable group, and examine the main properties of such groups. For weakly linearly compact groups, we construct the character theory and present an algebraic characterization of some classes of such groups. Some well-known theorems for periodic Abelian groups are generalized for the case of linearly discrete, topological Abelian groups; for linearly compact and linearly discrete topological Abelian groups, we also construct the character theory and study some important properties of linearly discrete groups. For linearly discrete, topological Abelian groups, we analyze the splittability condition (Theorem 3.12) and present the characteristic condition of decomposability of a discrete group G into the direct sum of rank-1 groups. We also present an algebraic characterization of linearly compact groups. We introduce the notion of a weakly linearly compact, topological Abelian group, which generalizes the notion of a weakly separable Abelian group, and examine some properties of such groups. These groups are a generalization of fibrous Abelian groups introduced by Vilenkin. We give an algebraic characterization of divisible, weakly locally compact Abelian groups that do not contain nonzero elements of finite order (Proposition 7.9). For weakly locally compact Abelian groups, we construct universal groups.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

Ring structures and the discrete Fourier transform

Since the pioneering work of J. W. Cooley and J. W. Tukey Math. Comp.19 1965 297–301, a great deal of effort has been devoted to developing efficient algorithms for computing finite Fourier transform. Among the new methods suggested over the past several years, methods depending on ring-theoretic structures have received special attention. This approach, originally suggested by C. Rader (Proc. IEEE5, 6 1968, 1107–1108), was really developed by S. Winograd (“Arithmetic Complexity of Computations,” CBMS-NSF Regional Conference Series in Applied Mathematics 1980 into a powerful new algorithm. Winograd's real contribution was to realize that there are efficient algorithms to evaluate cyclic convolution. The purpose of this article is twofold: first, to make more explicit the interplay between ring-theoretic structures and the algorithms for the finite Fourier transform; second, to use this new insight to construct new algorithms for evaluating the finite Fourier transform on the groups $\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}\text{⊕}\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}\text{⊕ … ⊕}\text{Z}\text{(p}{}^{\mathrm{s}}\text{Z)}$.     

Separation of Variables and the Computation of Fourier Transforms on Finite Groups,II

We present a general diagrammatic approach to the construction of efficient algorithms for computing the Fourier transform of a function on a finite group. By extending work which connects Bratteli diagrams to the construction of Fast Fourier Transform algorithms we make explicit use of the path algebra connection to the construction of Gel’fand–Tsetlin bases and work in the setting of quivers. We relate this framework to the construction of a configuration space derived from a Bratteli diagram. In this setting the complexity of an algorithm for computing a Fourier transform reduces to the calculation of the dimension of the associated configuration space. Our methods give improved upper bounds for computing the Fourier transform for the general linear groups over finite fields, the classical Weyl groups, and homogeneous spaces of finite groups, while also recovering the best known algorithms for the symmetric group.     

Rank-deficient submatrices of Fourier matrices

We consider the maximal rank-deficient submatrices of Fourier matrices with order a power of a prime number. We do this by considering a hierarchical subdivision of these matrices into low rank blocks. We also explore some connections with the fast Fourier transform (FFT), and with an uncertainty principle for Fourier transforms over finite Abelian groups.     

Geometry of the finite fourier transform

We provide a geometric interpretation for the multidimensional finite Fourier transform and give a reformulation of the Macwilliams identitity in terms of theta functions.     

Finite unsolvable nonsimple (A)-groups

The article gives a classification of finite unsolvable nonsimple groups satisfying the following condition (A): the intersection of any two nonincident subgroups of even order is Abelian.Translated from Matematicheskie Zamatki, Vol. 10, No. 2, pp. 163–168, August, 1971.The author would like to thank his academic sponsor, V. M. Basarkin, for the statement of the problem.     

Efficient computation of Fourier transforms on compact groups

This article genralizes the fast Fourier transform algorithm to the computation of Fourier transforms on compact Lie groups. The basic technique uses factorization of group elements and Gel'fand-Tsetlin bases to simplify the computations, and may be extended to treat the computation of Fourier transforms of finitely supported distributions on the group. Similar transforms may be defined on homogeneous spaces; in that case we show how special function properties of spherical functions lead to more efficient algorithms. These results may all be viewed as generalizations of the fast Fourier transform algorithms on the circle, and of recent results about Fourier transforms on finite groups. Acknowledgements and Notes. This paper was written while the author was supported by the Max-Planck-Institut für Mathematik, Bonn, Germany.     

On arithmetical algorithms over finite fields

Standard methods for calculating over GF(pⁿ), the finite field of pⁿ elements, require an irreducible polynomial of degree n with coefficients in GF(p). Such a polynomial is usually obtained by choosing it randomly and then verifying that it is irreducible, using a probabilistic algorithm. If it is not, the procedure is repeated. Here we given an explicit basis, with multiplication table, for the fields GF(p^pk), for k = 0, 1, 2,…, and their union. This leads to efficient computational methods, not requiring the preliminary calculation of irreducible polynomials over finite fields and, at the same time, yields a simple recursive formula for irreducible polynomials which generate the fields. The fast Fourier transform (FFT) is a method for efficiently evaluating (or interpolating) a polynomial of degree < n at all of the nth roots of unity, i.e., on the finite multiplicate subgroups of F, in O(nlogn) operations in the underlying field. We give an analogue of the fast Fourier transform which efficiently evaluates a polynomial on some of the additive subgroups ofF. This yields new “fast” algorithms for polynomial computation.     

Abelian groups

In the present, third survey of reviews of articles on Abelian groups are included papers reviewed during 1972–1978. Here, as in the previous surveys, the questions concerning finite Abelian groups, topological groups, ordered groups, group algebras, modules, structures of subgroups, as well as the questions connected with logic, are not touched on.Translated from Itogi Nauki i Tekhniki, Algebra, Topologiya, Geometriya, Vol. 17, pp. 3–63, 1979.     

On noncommutative serving extensions of groups

The paper studies serving extensions of noncommutative groups in the sense of the definition transferred naturally from the theory of Abelian groups. The basic results are those continuing the Los Theorem on the de composability of Abelian serving extensions of algebraic compact groups in the category of all groups.Translated from Matematicheskie Zametki, Vol. 11, No. 3, pp. 283–291, March, 1972.The author wishes to take this opportunity to thank her scientific adviser Prof. L. Ya. Kulikov for his attention to this work.     

Correlation-Immune and Resilient Functions Over a Finite Alphabet and Their Applications in Cryptography

We extend the notions of correlation-immune functions and resilient functions to functions over any finite alphabet. A previous result due to Gopalakrishnan and Stinson is generalized as we give an orthogonal array characterization, a Fourier transform and a matrix characterization for correlation-immune and resilient functions over any finite alphabet endowed with the structure of an Abelian group. We then point out the existence of a tradeoff between the degree of the algebraic normal form and the correlation-immunity order of any function defined on a finite field and we construct some infinite families of t-resilient functions with optimal nonlinearity which are particularly well-suited for combining linear feedback shift registers. We also point out the link between correlation-immune functions and some cryptographic objects as perfect local randomizers and multipermutations.     

Computation of the fractional Fourier transform

In this paper we make a critical comparison of some programs for the digital computation of the fractional Fourier transform that are freely available and we describe our own implementation that filters the best out of the existing ones. Two types of transforms are considered: first, the fast approximate fractional Fourier transform algorithm for which two algorithms are available. The method is described in [H.M. Ozaktas, M.A. Kutay, G. Bozda i, IEEE Trans. Signal Process. 44 (1996) 2141–2150]. There are two implementations: one is written by A.M. Kutay, the other is part of package written by J. O'Neill. Second, the discrete fractional Fourier transform algorithm described in the master thesis by Ç. Candan [Bilkent University, 1998] and an algorithm described by S.C. Pei, M.H. Yeh, and C.C. Tseng [IEEE Trans. Signal Process. 47 (1999) 1335–1348].     

Two geometric interpretations of the multidimensional Hardy uncertainty principle

Hardy's uncertainty principle says that a square integrable function and its Fourier transform cannot be simultaneously arbitrarily sharply localized. We show that a multidimensional version of this uncertainty principle can be best understood in geometrical terms using the fruitful notion of symplectic capacity, which was introduced in the mid-eighties following unexpected advances in symplectic topology (Gromov's non-squeezing theorem). In this geometric formulation, the notion of Fourier transform is replaced with that of polar duality, well-known from convex geometry.     

Strong asymptotics of the recurrence coefficients of orthogonal polynomials associated to the generalized Jacobi weight

We study asymptotics of the recurrence coefficients of orthogonal polynomials associated to the generalized Jacobi weight, which is a weight function with a finite number of algebraic singularities on [−1,1]. The recurrence coefficients can be written in terms of the solution of the corresponding Riemann–Hilbert (RH) problem for orthogonal polynomials. Using the steepest descent method of Deift and Zhou, we analyze the RH problem, and obtain complete asymptotic expansions of the recurrence coefficients. We will determine explicitly the order 1/n terms in the expansions. A critical step in the analysis of the RH problem will be the local analysis around the algebraic singularities, for which we use Bessel functions of appropriate order. In addition, the RH approach gives us also strong asymptotics of the orthogonal polynomials near the algebraic singularities in terms of Bessel functions.