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.     

A fast transform for spherical harmonics

Spherical harmonics arise on the sphere S² in the same way that the (Fourier) exponential functions {e^ik}k arise on the circle. Spherical harmonic series have many of the same wonderful properties as Fourier series, but have lacked one important thing: a numerically stable fast transform analogous to the Fast Fourier Transform (FFT). Without a fast transform, evaluating (or expanding in) spherical harmonic series on the computer is slow—for large computations probibitively slow. This paper provides a fast transform.For a grid ofO(N²) points on the sphere, a direct calculation has computational complexityO(N⁴), but a simple separation of variables and FFT reduce it toO(N³) time. Here we present algorithms with timesO(N^5/2 log N) andO(N²(log N)²). The problem quickly reduces to the fast application of matrices of associated Legendre functions of certain orders. The essential insight is that although these matrices are dense and oscillatory, locally they can be represented efficiently in trigonometric series.     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

FFTs for the 2-Sphere-Improvements and Variations

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this article we present a reformulation and variation of the original algorithm which results in a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. All require at most O(N log² N) operations where N is the number of sample points. We also address implementation considerations and give heuristics for allowing reliable and computationally efficient floating point implementations of slightly modified algorithms. These claims are supported by extensive numerical experiments from our implementation in C on DEC, HP, SGI and Linux Pentium platforms. These results indicate that variations of the algorithm are both reliable and efficient for a large range of useful problem sizes. Performance appears to be architecture-dependent. The article concludes with a brief discussion of a few potential applications.     

Spectral discretizations of 3-D elliptic problems and fast domain decomposition methods

An important for applications, the class of hp discretizations of second-order elliptic equations consists of discretizations based on spectral finite elements. The development of fast domain decomposition algorithms for them was restrained by the absence of fast solvers for the basic components of the method, i.e., for local interior problems on decomposition subdomains and their faces. Recently, the authors have established that such solvers can be designed using special factorized preconditioners. In turn, factorized preconditioners are constructed using an important analogy between the stiffness matrices of spectral and hierarchical basis hp-elements (coordinate functions of the latter are defined as tensor products of integrated Legendre polynomials). Due to this analogy, for matrices of spectral elements, fast solvers can be developed that are similar to those for matrices of hierarchical elements. Based on these facts and previous results on the preconditioning of other components, fast domain decomposition algorithms for spectral discretizations are obtained.     

Vekua theory for the Helmholtz operator

Vekua operators map harmonic functions defined on domain in \mathbb R²{\mathbb R^{2}} to solutions of elliptic partial differential equations on the same domain and vice versa. In this paper, following the original work of I. Vekua (Ilja Vekua (1907–1977), Soviet-Georgian mathematician), we define Vekua operators in the case of the Helmholtz equation in a completely explicit fashion, in any space dimension N ≥ 2. We prove (i) that they actually transform harmonic functions and Helmholtz solutions into each other; (ii) that they are inverse to each other; and (iii) that they are continuous in any Sobolev norm in star-shaped Lipschitz domains. Finally, we define and compute the generalized harmonic polynomials as the Vekua transforms of harmonic polynomials. These results are instrumental in proving approximation estimates for solutions of the Helmholtz equation in spaces of circular, spherical, and plane waves.     

Block Coordinate Relaxation Methods for Nonparametric Wavelet Denoising

Abstract

An important class of nonparametric signal processing methods entails forming a set of predictors from an overcomplete set of basis functions associated with a fast transform (e.g., wavelet packets). In these methods, the number of basis functions can far exceed the number of sample values in the signal, leading to an ill-posed prediction problem. The “basis pursuit” denoising method of Chen, Donoho, and Saunders regularizes the prediction problem by adding an l ₁ penalty term on the coefficients for the basis functions. Use of an l ₁ penalty instead of l ₂ has significant benefits, including higher resolution of signals close in time/frequency and a more parsimonious representation. The l ₁ penalty, however, poses a challenging optimization problem that was solved by Chen, Donoho and Saunders using a novel application of interior-point algorithms (IP). This article investigates an alternative optimization approach based on block coordinate relaxation (BCR) for sets of basis functions that are the finite union of sets of orthonormal basis functions (e.g., wavelet packets). We show that the BCR algorithm is globally convergent, and empirically, the BCR algorithm is faster than the IP algorithm for a variety of signal denoising problems.     

Spherical Harmonic Analysis for Spinors on H n (C)

Recent results on the harmonic analysis of spinor fields on the complex hyperbolic space H ⁿ (C) are reviewed. We discuss the action of the invariant differential operators on the Poisson transforms, the theory of spherical functions and the spherical transform. The inversion formula, the Paley–Wiener theorem, and the Plancherel theorem for the spherical transform are obtained by reduction to Jacobi analysis on L ²(R).     

The differential Fourier transform method

We suggest the two new discrete differential sine and cosine Fourier transforms of a complex vector which are based on solving by a finite difference scheme the inhomogeneous harmonic differential equations of the first order with complex coefficients and of the second order with real coefficients, respectively. In the basic version, the differential Fourier transforms require by several times less arithmetic operations as compared to the basic classicalmethod of discrete Fourier transform. In the differential sine Fourier transform, the matrix of the transformation is complex,with the real and imaginary entries being alternated, whereas in the cosine transform, the matrix is purely real. As in the classical case, both matrices can be converted into the matrices of cyclic convolution; thus all fast convolution algorithms including the Winograd and Rader algorithms can be applied to them. The differential Fourier transform method is compatible with the Good–Thomas algorithm of the fast Fourier transform and can potentially outperform all available methods of acceleration of the fast Fourier transform when combined with the fast convolution algorithms.     

Fast block Toeplitz orthogonalization

Summary Algorithms are presented which compute theQR factorization of a block-Toeplitz matrix inO(n) ² block-operations, wheren is the block-order of the matrix and a block-operation is a multiplication, inversion or a set of Householder operations involving one or two blocks. The algorithms are in general analogous to those presented in the scalar Toeplitz case in a previous paper, but the basic operation is the Householder transform rather than the Givens transform, and the computation of the Householder coefficients and other working matrices requires special treatment. Two algorithms are presented-the first computes onlyR explicitly and the second computes bothQ andR.     

An improved Monte Carlo factorization algorithm

Pollard's Monte Carlo factorization algorithm usually finds a factor of a composite integerN inO(N ^1/4) arithmetic operations. The algorithm is based on a cycle-finding algorithm of Floyd. We describe a cycle-finding algorithm which is about 36 percent faster than Floyd's (on the average), and apply it to give a Monte Carlo factorization algorithm which is similar to Pollard's but about 24 percent faster.     

Faster than the Fast Legendre Transform,the Linear-time Legendre Transform

A new algorithm to compute the Legendre–Fenchel transform is proposed and investigated. The so-called Linear-time Legendre Transform (LLT) improves all previously known Fast Legendre Transform algorithms by reducing their log-linear worst-case time complexity to linear. Since the algorithm amounts to computing several convex hulls and sorting, any convex hull algorithm well-suited for a particular problem gives a corresponding LLT algorithm. After justifying the convergence of the Discrete Legendre Transform to the Legendre–Fenchel transform, an extended computation time complexity analysis is given and confirmed by numerical tests. Finally, the LLT is illustrated with several examples and a LLT MATLAB package is described. This revised version was published online in June 2006 with corrections to the Cover Date.     

Rapidly computing sparse Legendre expansions via sparse Fourier transforms

In this paper, we propose a general strategy for rapidly computing sparse Legendre expansions. The resulting methods yield a new class of fast algorithms capable of approximating a given function f : [?1, 1] → ? with a near-optimal linear combination of s Legendre polynomials of degree ≤ N in just \((s \log N)^{\mathcal {O}(1)}\)-time. When s ? N, these algorithms exhibit sublinear runtime complexities in N, as opposed to traditional Ω(NlogN)-time methods for computing all of the first N Legendre coefficients of f. Theoretical as well as numerical results demonstrate the effectiveness of the proposed methods.     

A fast spherical harmonics transform algorithm

The spectral method with discrete spherical harmonics transform plays an important role in many applications. In spite of its advantages, the spherical harmonics transform has a drawback of high computational complexity, which is determined by that of the associated Legendre transform, and the direct computation requires time of for cut-off frequency . In this paper, we propose a fast approximate algorithm for the associated Legendre transform. Our algorithm evaluates the transform by means of polynomial interpolation accelerated by the Fast Multipole Method (FMM). The divide-and-conquer approach with split Legendre functions gives computational complexity . Experimental results show that our algorithm is stable and is faster than the direct computation for .

     

Factoring wavelet transforms into lifting steps

This article is essentially tutorial in nature. We show how any discrete wavelet transform or two band subband filtering with finite filters can be decomposed into a finite sequence of simple filtering steps, which we call lifting steps but that are also known as ladder structures. This decomposition corresponds to a factorization of the polyphase matrix of the wavelet or subband filters into elementary matrices. That such a factorization is possible is well-known to algebraists (and expressed by the formulaSL(n;R[z, z⁻¹])=E(n;R[z, z⁻¹])); it is also used in linear systems theory in the electrical engineering community. We present here a self-contained derivation, building the decomposition from basic principles such as the Euclidean algorithm, with a focus on applying it to wavelet filtering. This factorization provides an alternative for the lattice factorization, with the advantage that it can also be used in the biorthogonal, i.e., non-unitary case. Like the lattice factorization, the decomposition presented here asymptotically reduces the computational complexity of the transform by a factor two. It has other applications, such as the possibility of defining a wavelet-like transform that maps integers to integers. Research Tutorial Acknowledgements and Notes. Page 264.     

Revisiting Hardy's theorem for the Heisenberg group

We establish several versions of Hardy's theorem for the Fourier transform on the Heisenberg group. Let be the Fourier transform of a function f on and assume where is the heat kernel associated to the sublaplacian. We show that if then whenever . When we replace the condition on f by where is the Fourier transform of f in the t-variable. Under suitable assumptions on the ‘spherical harmonic coefficients’ of we prove: (i) when a=b; (ii) when a > b there are infinitely many linearly independent functions f satisfying both conditions on and . Received: 9 January 2001 / in final form: 17 April 2001 Published online: 1 February 2002     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

Multilevel preconditioning on the refined interface and optimal boundary solvers for the Laplace equation

In this paper we propose and analyze some strategies to construct asymptotically optimal algorithms for solving boundary reductions of the Laplace equation in the interior and exterior of a polygon. The interior Dirichlet or Neumann problems are, in fact, equivalent to a direct treatment of the Dirichlet-Neumann mapping or its inverse, i.e., the Poincaré-Steklov (PS) operator. To construct a fast algorithm for the treatment of the discrete PS operator in the case of polygons composed of rectangles and regular right triangles, we apply the Bramble-Pasciak-Xu (BPX) multilevel preconditioner to the equivalent interface problem in theH ^1/2-setting. Furthermore, a fast matrix-vector multiplication algorithm is based on the frequency cutting techniques applied to the local Schur complements associated with the rectangular substructures specifying the nonmatching decomposition of a given polygon. The proposed compression scheme to compute the action of the discrete interior PS operator is shown to have a complexity of the orderO(N log ^q N),q [2, 3], with memory needsO(N log² N), whereN is the number of degrees of freedom on the polygonal boundary under consideration. In the case of exterior problems we propose a modification of the standard direct BEM whose implementation is reduced to the wavelet approximation applied to either single layer or hypersingular harmonic potentials and, in addition, to the matrix-vector multiplication for the discrete interior PS operator.     

A duality theory for some non-convex functions of matrices

Abstract We study a special class of non-convex functions which appear in nonlinear elasticity, and we prove that they have a well-defined Legendre transform. Several examples are given, and an application to a nonlinear eigenvalue problem. Keywords: Duality, Legendre transform, Nonlinear elasticity Mathematics Subject Classification (2000): 05C38, 15A15, 05A15, 15A18     

Discrete fourier transform computation using prime Ramanujan numbers

Ramanujan numbers were introduced in [2] to implement discrete fourier transform (DFT) without using any multiplication operation. Ramanujan numbers are related to π and integers which are powers of 2. If the transform sizeN, is a Ramanujan number, then the computational complexity of the algorithms used for computing isO(N ²) addition and shift operations, and no multiplications. In these algorithms, the transform can be computed sequentially with a single adder inO(N ²) addition times. Parallel implementation of the algorithm can be executed inO(N) addition times, withO(N) number of adders. Some of these Ramanujan numbers of order-2 are related to the Biblical and Babylonian values of π [1]. In this paper, we analytically obtain upper bounds on the degree of approximation in the computation of DFT if JV is a prime Ramanujan number.