FFTs on the Rotation Group

We discuss an implementation of an efficient algorithm for the numerical computation of Fourier transforms of bandlimited functions defined on the rotation group SO(3). The implementation is freely available on the web. The algorithm described herein uses O(B ⁴) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the O(B ³)) spherical harmonics of degree at most B. This compares very favorably with the direct O(B ⁶) algorithm derived from a basic quadrature rule on O(B ³) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over SO(3) which has been used as the analytic engine for some new approaches to searching 3D databases (Funkhouser et al., ACM Trans. Graph. 83–105, [2003]; Kazhdan et al., Eurographics Symposium in Geometry Processing, pp. 167–175, [2003]). Our implementation is based on the “Separation of Variables” technique (see, e.g., Maslen and Rockmore, Proceedings of the DIMACS Workshop on Groups and Computation, pp. 183–237, [1997]). In conjunction with techniques developed for the efficient computation of orthogonal polynomial expansions (Driscoll et al., SIAM J. Comput. 26(4):1066–1099, [1997]), our fast SO(3) algorithm can be improved to give an algorithm of complexity O(B ³log ² B), but at a cost in numerical reliability. Numerical and empirical results are presented establishing the empirical stability of the basic algorithm. Examples of applications are presented as well. First author was supported by NSF ITR award; second author was supported by NSF Grant 0219717 and the Santa Fe Institute.     

The Efficient Computation of Fourier Transforms on Semisimple Algebras

We present a general diagrammatic approach to the construction of efficient algorithms for computing a Fourier transform on a semisimple algebra. This extends previous work wherein we derive best estimates for the computation of a Fourier transform for a large class of finite groups. We continue to find efficiencies by exploiting a connection between Bratteli diagrams and the derived path algebra and construction of Gel’fand–Tsetlin bases. Particular results include highly efficient algorithms for the Brauer, Temperley–Lieb, and Birman–Murakami–Wenzl algebras.     

Deciding finiteness for matrix groups over function fields

LetF be a field andt an indeterminate. In this paper we consider aspects of the problem of deciding if a finitely generated subgroup of GL(n,F(t)) is finite. WhenF is a number field, the analysis may be easily reduced to deciding finiteness for subgroups of GL(n,F), for which the results of [1] can be applied. WhenF is a finite field, the situation is more subtle. In this case our main results are a structure theorem generalizing a theorem of Weil and upper bounds on the size of a finite subgroup generated by a fixed number of generators with examples of constructions almost achieving the bounds. We use these results to then give exponential deterministic algorithms for deciding finiteness as well as some preliminary results towards more efficient randomized algorithms. Supported in part by NSF DMS Awards 9404275 and Presidential Faculty Fellowship.     

Nonlinear approximation theory on compact groups

In this article we extend to the setting of band-limited functions on compact groups previous results bounding from below the percentage of energy, contained in the low frequency portion of the spectrum of a positive function defined on a cyclic group. Connections to signal recovery for positive functions, as well as partial spectral analysis, are also discussed.     

Separation of variables and the computation of Fourier transforms on finite groups, I

This paper introduces new techniques for the efficient computation of a Fourier transform on a finite group. We present a divide and conquer approach to the computation. The divide aspect uses factorizations of group elements to reduce the matrix sum of products for the Fourier transform to simpler sums of products. This is the separation of variables algorithm. The conquer aspect is the final computation of matrix products which we perform efficiently using a special form of the matrices. This form arises from the use of subgroup-adapted representations and their structure when evaluated at elements which lie in the centralizers of subgroups in a subgroup chain. We present a detailed analysis of the matrix multiplications arising in the calculation and obtain easy-to-use upper bounds for the complexity of our algorithm in terms of representation theoretic data for the group of interest.

Our algorithm encompasses many of the known examples of fast Fourier transforms. We recover the best known fast transforms for some abelian groups, the symmetric groups and their wreath products, and the classical Weyl groups. Beyond this, we obtain greatly improved upper bounds for the general linear and unitary groups over a finite field, and for the classical Chevalley groups over a finite field. We also apply these techniques to obtain analogous results for homogeneous spaces.

This is part I of a two part paper. Part II will present a refinement of these techniques which yields further savings.

     

A note on the order of finite subgroups of GL(n, ℤ)

supported in part by an NSF Math Sciences Postdoctoral Fellowship     

Eikonal approach to scattering from coated perfect conductors in a spinor formalism

The eikonal approach is applied to the problem of the scattering of electromagnetic waves from an excluded volume in the presence of a weak external potential. The scattering of electromagnetic waves is treated in the spinor formalism previously developed by the author. The excluded volume is eventually taken to be a perfectly conducting cone, the external potential a coating of thickness , with complex dielectric constant , and permeability (tacitly assumed equal to 1). It is shown that to order (N–1), whereN=( )^1/2, the eikonal approach in the spinor formalism yields results equivalent to those obtained from the vector theory of Überall in the particular case of nose-on backscattering, using the eikonal function corresponding to straight-line propagation.Any views expressed in this paper are those of the author. They should not be interpreted as reflecting the views of The RAND Corporation or the official opinion or policy of any of its governmental or private research sponsors. Papers are reproduced by The RAND Corporation as a courtesy to members of its staff.     

Evolution of community structure in the world trade web

In this note we study the bilateral merchandise trade flows between 186 countries over the 1948–2005 period using data from the International Monetary Fund. We use the network visualization package Pajek to identify network structure and behavior across thresholds and over time. In particular, we focus on the evolution of trade “islands” in a world trade network in which countries are linked with directed edges weighted according to the fraction of total dollars sent from one country to another. We find mixed evidence for globalization.