MULTIVARIATE FOURIER SERIES OVER A CLASS OF NON TENSOR－PRODUCT PARTITION DOMAINS

This paper finds a way to extend the well-known Fourier methods,to so-called n 1 directions partition domains in n-dimension.In particular,in 2-D and 3-D cases,we study Fourier methods over 3-direction parallel hexagon partitions and 4-direction parallel paralleogram dodecahedron partitions,respectively.It has pointed that,the most concepts and results of Fourier methods on tensor-product case,such as periodicity,orthogonality of Fourier basis system,Partial sum of Fourier series and its approximation behavior,can be moved on the new non tensor-product partiton case.     

Fast Computation of Multivariate Kernel Estimators

Abstract

Multivariate extensions of binning techniques for fast computation of kernel estimators are described and examined. Several questions arising from this multivariate extension are addressed. The choice of binning rule is discussed, and it is demonstrated that linear binning leads to substantial accuracy improvements over simple binning. An investigation into the most appropriate means of computing the multivariate discrete convolutions required for binned kernel estimators is also given. The results of an empirical study indicate that, in multivariate settings, the fast Fourier transform offers considerable time savings compared to direct calculation of convolutions.     

FFT-Based Fast Computation of Multivariate Kernel Density Estimators With Unconstrained Bandwidth Matrices

The problem of fast computation of multivariate kernel density estimation (KDE) is still an open research problem. In our view, the existing solutions do not resolve this matter in a satisfactory way. One of the most elegant and efficient approach uses the fast Fourier transform. Unfortunately, the existing FFT-based solution suffers from a serious limitation, as it can accurately operate only with the constrained (i.e., diagonal) multivariate bandwidth matrices. In this article, we describe the problem and give a satisfactory solution. The proposed solution may be successfully used also in other research problems, for example, for the fast computation of the optimal bandwidth for KDE. Supplementary materials for this article are available online.     

Quantum Fourier transform revisited

The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank‐1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix‐2 QFT decomposition to a radix‐d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.     

矩阵分解与Chrestenson谱的计算

本文研究离散Fourier变换的一类变型-整数模合数m剩余类环上n元函数的Chrestenson谱的快速计算,基于稀疏矩阵分解,给出了两种复杂度为O(mⁿn∑^r_i=1p_i)的计算Chrestenson谱的快速算法,其中p₁p₂…p_r是m的素因子分解.     

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].     

对称r-循环矩阵的快速算法和并行算法

借助于快速付立叶变换(FFT),给出了一种判断对称r-循环线性系统是否有解的快速算法,并且在有解的情况下求出其解,该算法的计算复杂度为O(nlogn),且具有很好的并行性,若使用n台处理机并行处理该算法则只需要O(logn)步.当r=0时,对称r-循环矩阵变成一个上三角型Hankel矩阵,我们也给出了此类矩阵求逆的一种算法.最后将该算法推广到线性同余系统,其运算量仅为O(nlogn).     

Large-Scale Structured Sparsity via Parallel Fused Lasso on Multiple GPUs

We present a massively parallel algorithm for the fused lasso, powered by a multiple number of graphics processing units (GPUs). Our method is suitable for a class of large-scale sparse regression problems on which a two-dimensional lattice structure among the coefficients is imposed. This structure is important in many statistical applications, including image-based regression in which a set of images are used to locate image regions predictive of a response variable such as human behavior. Such large datasets are increasingly common. In our study, we employ the split Bregman method and the fast Fourier transform, which jointly have a high data-level parallelism that is distinct in a two-dimensional setting. Our multi-GPU parallelization achieves remarkably improved speed. Specifically, we obtained as much as 433 times improved speed over that of the reference CPU implementation. We demonstrate the speed and scalability of the algorithm using several datasets, including 8100 samples of 512 × 512 images. Compared to the single GPU counterpart, our method also showed improved computing speed as well as high scalability. We describe the various elements of our study as well as our experience with the subtleties in selecting an existing algorithm for parallelization. It is critical that memory bandwidth be carefully considered for multi-GPU algorithms. Supplementary material for this article is available online.     

Fourier Transform Over Local Fields

The Fourier transform in the space of distributions on finite-dimensional vector spaces over local fields is defined, and a strong similarity between the case of archimedian and non-archimedian fields is discussed. Furthermore, the definition of the Fourier transform for the case of “functions” on finite-dimensional vector spaces over 2-dimensional local fields is introduced. Leonardo da Vinci lecture held on June 29, 2005 Received: October 2005     

γ-循环线性方程组的快速算法

1．引言在数学以及应用科学中的许多问题都与周期性有关，从而导致一类特殊形式的TOeelitZ系统，即r一循环线性系统的求解，其计算复杂性为O（N”）［’j或渐近复杂性O（NlogZN）p］．由于循环矩阵与离散富里时变换之间的关系，我们也可通过快速富里叶变换（＊＊n来求解r一循环线性方程组，计算复杂性降为O（NlogZN）［‘，’］．事实上，到目前为止所有与厂循环矩阵有关问题的快速算法全部建立在富里叶变换某础之卜IZ，9，10，17，19，20］但另一方面富里叶交换定义在复数域上，而实际问题中的数据大多为实数，因此用FFT快速求解r…     

Windowed Fourier transform of two-dimensional quaternionic signals

In this paper, we generalize the classical windowed Fourier transform (WFT) to quaternion-valued signals, called the quaternionic windowed Fourier transform (QWFT). Using the spectral representation of the quaternionic Fourier transform (QFT), we derive several important properties such as reconstruction formula, reproducing kernel, isometry, and orthogonality relation. Taking the Gaussian function as window function we obtain quaternionic Gabor filters which play the role of coefficient functions when decomposing the signal in the quaternionic Gabor basis. We apply the QWFT properties and the (right-sided) QFT to establish a Heisenberg type uncertainty principle for the QWFT. Finally, we briefly introduce an application of the QWFT to a linear time-varying system.     

Roundoff Error Analysis of the Recursive Moving Window Discrete Fourier Transform

This paper presents both worst case and average case analysis of roundoff errors occuring in the floating point computation of the recursive moving window discrete Fourier transform (DFT) with precomputed twiddle factors. We show the strong influence of precomputation errors – both within the initial fast Fourier transform (FFT) and the recursion – on the numerical stability. Numerical simulations confirm the theoretical results.     

Properties of the Simpson discrete Fourier transform

Abstract

The Simpson discrete Fourier transform (SDFT) and its inverse are transformations relating the time and frequency domains. In this paper we state and prove the important properties of shift, circular convolution, conjugation, time reversal and Plancherel's theorem. In addition, we provide an alternative representation of the duality property.     

Fourier transform and related integral transforms in superspace

In this paper extensions of the classical Fourier, fractional Fourier and Radon transforms to superspace are studied. Previously, a Fourier transform in superspace was already studied, but with a different kernel. In this work, the fermionic part of the Fourier kernel has a natural symplectic structure, derived using a Clifford analysis approach. Several basic properties of these three transforms are studied. Using suitable generalizations of the Hermite polynomials to superspace (see [H. De Bie, F. Sommen, Hermite and Gegenbauer polynomials in superspace using Clifford analysis, J. Phys. A 40 (2007) 10441-10456]) an eigenfunction basis for the Fourier transform is constructed.     

Application of the discrete Fourier transform to solving the Cauchy integral equation

The uniquely solvable system of the Cauchy integral equation of the first kind and index 1 and an additional integral condition is treated. Such a system arises, for example, when solving the skew derivative problem for the Laplace equation outside an open arc in a plane. This problem models the electric current from a thin electrode in a semiconductor film placed in a magnetic field. A fast and accurate numerical method based on the discrete Fourier transform is proposed. Some computational tests are given. It is shown that the convergence is close to exponential.     

分块K—循环Toeplitz矩阵求逆的快速付氏变换法

1算法描述及推导 Toeplitz矩阵及Toeplitz系统的求解在谱分析、线性预测、误差控制码、自回归滤波器设计等领域内起着重要的作用~[1-3]，而分块Toeplitz矩阵在计算机的时序分析、自回归时序模型滤波中也经常出现~[4]。对一般Toeplitz矩阵求逆，其算术复杂性为O(n~2)~[5]-[6]，其中n为Toepleitz矩阵的阶，而K-循环Toeplitz矩阵的求逆，其算术复杂性可降为O(nlog_2n)，本文提供了mn附分块K-循环Toeplitz矩阵求逆的一种快速付氏变换算法，其算术复杂性为O（mnlog_2mn）.     

����ת��ģ���¾���Ȩ����Ȩ�Ķ����о�

This paper investigates the pricing of CatEPuts under a Markovian regime-switching jump-diffusion model. The parameters of this model, including the risk-free interest rate, the appreciation rate and the volatility of the clients' equity, are modulated by a continuous-time, finite-state, observable Markov chain. An equivalent martingale measure is selected by employing the regime-switching Esscher transform. The fast Fourier transform (FFT) technique is applied to price the CatEPuts. In a two-state Markov chain case, numerical example is presented to illustrate the practical implementation of the model.     

Clifford algebras,Fourier transforms,and quantum mechanics

In this review, we give an overview of several recent generalizations of the Fourier transform, related to either the Lie algebra or the Lie superalgebra . In the former case, one obtains scalar generalizations of the Fourier transform, including the fractional Fourier transform, the Dunkl transform, the radially deformed Fourier transform, and the super Fourier transform. In the latter case, one has to use the framework of Clifford analysis and arrives at the Clifford–Fourier transform and the radially deformed hypercomplex Fourier transform. A detailed exposition of all these transforms is given, with emphasis on aspects such as eigenfunctions and spectrum of the transform, characterization of the integral kernel, and connection with various special functions. Copyright © 2012 John Wiley & Sons, Ltd.     

A hybrid Fourier transform

A Fourier transform akin to Sneddon's R-transform is introduced. It is shown that the Hilbert transform links the two in much the same way as it connects the classical Fourier sine and cosine transforms.     

非线性玻尔兹曼方程的傅里叶谱方法

玻尔兹曼方程作为空气动理学中最基本的方程之一,是连接微观牛顿力学和宏观连续介质力学的重要桥梁.该方程描述了一个由大量粒子组成的复杂系统的非平衡态时间演化:除了基本的输运项,其最重要的特性是粒子间的相互碰撞由一个高维,非局部且非线性的积分算子来描述,从而给玻尔兹曼方程的数值求解带来非常大的挑战.在过去的二十年间,基于傅里叶级数的谱方法成为了数值求解玻尔兹曼方程的一种很受欢迎且有效的确定性算法.这主要归功于谱方法的高精度及它可以被快速傅里叶变换加速的特质.本文将回顾玻尔兹曼方程的傅里叶谱方法,具体包括方法的导出,稳定性和收敛性分析,快速算法,以及在一大类基于碰撞的空气动理学方程中的推广.