N=2^t点DFT的快速卷积算法

从所周知,循环卷积和离散富里叶变换(DFT)可以互相计算,只要得到其中一个的快速算法就可导出另一个的快速算法。循环卷积目前已有乘法量为O(N)的最佳算法(特别是当N较小时),为此关键是如何将DFT转化为循环卷积,当DFT的长度N=p(p为素数),Rader利用有限域GF(p)的乘法群是循环群就成功地将p点DFT转化为Q(p)(F(p)为户的Euler函数)点循环卷积;当N=p~e时,由于商环Z/(p~e)存在F(p~c)阶元素,人们也成功地将p~c点DFT转化为P(p~(c-1))一系列循环卷积,即一个y(p~c)点循环卷积,二个P(p~(c-1))点     

平行六边形区域上的快速离散傅立叶变换

In this paper, we propose a fast algorithm for computing the DGFT (Discrete Generalized Fourier Transforms) on hexagon domains [6], based on the geometric properties of the domain. Our fast algorithm (FDGFT) reduces the computation complexity of DGFT from O(N4) to O(N2 log N). In particulary, for N =2^P23^P34^P45^P56^P6, the floating point computation working amount equals to(17/2P2 16p3 135/8p4 2424/25p5 201/2P6)3N^2. Numerical examples are given to access our analysis.     

多层快速多极子方法的快速插值

多层快速多极子方法(MLFMM)可用来加速迭代求解由Maxwell方程组或Helmholtz方程导出的积分方程,其复杂度理论上是O(NlogN),N为未知量个数.MLFMM依赖于快速计算每层的转移项,以及上聚和下推过程中的层间插值.本文引入计算类似N体问题的一维快速多极子方法(FMM1D).基于FMM1D的快速Lagr...     

Fast skew-feedback shift-register synthesis

A skew-feedback shift-register is a generalization of a linear-feedback shift-register and can be applied in decoding (interleaved) Reed–Solomon codes or Gabidulin codes beyond half their code distance. A fast algorithm is proposed which synthesizes all shortest skew-feedback shift-registers generating L sequences of varying length over a field. For fixed L, the time complexity of the algorithm is ${{\mathcal O}(M(N) \log N)}$ operations, where N is the length of a longest sequence and M(N) is the complexity of the multiplication of two skew polynomials of maximum degree N.     

Fast evaluation of trigonometric polynomials from hyperbolic crosses

The discrete Fourier transform in d dimensions with equispaced knots in space and frequency domain can be computed by the fast Fourier transform (FFT) in arithmetic operations. In order to circumvent the ‘curse of dimensionality’ in multivariate approximation, interpolations on sparse grids were introduced. In particular, for frequencies chosen from an hyperbolic cross and spatial knots on a sparse grid fast Fourier transforms that need only arithmetic operations were developed. Recently, the FFT was generalised to nonequispaced spatial knots by the so-called NFFT. In this paper, we propose an algorithm for the fast Fourier transform on hyperbolic cross points for nonequispaced spatial knots in two and three dimensions. We call this algorithm sparse NFFT (SNFFT). Our new algorithm is based on the NFFT and an appropriate partitioning of the hyperbolic cross. Numerical examples confirm our theoretical results.     

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

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

r-对称循环矩阵及逆矩阵三角分解的快速算法

根据r-对称循环矩阵的特殊结构给出了求这类矩阵本身及其逆矩阵三角分解的快速算法,算法的运算量均为O(n2),一般矩阵及逆矩阵三角分解的运算量均为O(n3).     

Singular integral transforms and fast numerical algorithms

Fast algorithms for the accurate evaluation of some singular integral operators that arise in the context of solving certain partial differential equations within the unit circle in the complex plane are presented. These algorithms are generalizations and extensions of a fast algorithm of Daripa [11]. They are based on some recursive relations in Fourier space and the FFT (Fast Fourier Transform), and have theoretical computational complexity of the order O(N) per point, where N² is the total number of grid points. An application of these algorithms to quasiconformal mappings of doubly connected domains onto annuli is presented in a follow-up paper.     

Fast multipole method for multidimensional integrals

We give a fast algorithm to evaluate a class of d-dimensional integrals. A direct numerical evaluation of these integrals costs N^d, where d is the number of variables and N is the number of discrete points of each variable. The algorithm we present in this Note permits to reduce this cost from N^d to a cost of the order O(N). This recursive algorithm takes its inspiration from the well-known Fast-Multipole method. At the end of this paper we give some physical applications of such an algorithm.     

Efficient Reconstruction of Functions on the Sphere from Scattered Data

Recently, fast and reliable algorithms for the evaluation of spherical harmonic expansions have been developed. The corresponding sampling problem is the computation of Fourier coefficients of a function from sampled values at scattered nodes. We consider a least squares approximation and an interpolation of the given data. Our main result is that the rate of convergence of the two proposed iterative schemes depends only on the mesh norm and the separation distance of the nodes. In conjunction with the nonequispaced FFT on the sphere, the reconstruction of N² Fourier coefficients from M reasonably distributed samples is shown to take O(N² log² N + M) floating point operations. Numerical results support our theoretical findings.     

A FAST COMPACT DIFFERENCE METHOD FOR TWO-DIMENSIONAL NONLINEAR SPACE-FRACTIONAL COMPLEX GINZBURG-LANDAU EQUATIONS

This paper focuses on a fast and high-order finite difference method for two-dimensional space-fractional complex Ginzburg-Landau equations.We firstly establish a three-level finite difference scheme for the time variable followed by the linearized technique of the nonlinear term.Then the fourth-order compact finite difference method is employed to discretize the spatial variables.Hence the accuracy of the discretization is O(τ2 + h41 +h42) in L2-norm,where τ is the temporal step-size,both h1 and h2 denote spatial mesh sizes in x-and y-directions,respectively.The rigorous theoretical analysis,including the uniqueness,the almost unconditional stability,and the convergence,is studied via the energy argument.Practically,the discretized system holds the block Toeplitz structure.Therefore,the coefficient Toeplitz-like matrix only requires O(M1M2) memory storage,and the matrix-vector multiplication can be carried out in O(M1M2(logM1 + log M2))computational complexity by the fast Fourier transformation,where M1 and M2 denote the numbers of the spatial grids in two different directions.In order to solve the resulting Toeplitz-like system quickly,an efficient preconditioner with the Krylov subspace method is proposed to speed up the iteration rate.Numerical results are given to demonstrate the well performance of the proposed method.     

Toeplitz型矩阵的逆矩阵的快速三角分解算法

针对有关“型”矩阵的三角分解问题 ,提出了一种 Toeplitz型矩阵的逆矩阵的快速三角分解算法 .首先假设给定 n阶非奇异矩阵 A,利用一组线性方程组的解 ,得到 A- 1的一个递推关系式 ,进而利用该关系式得到 A- 1的一种三角分解表达式 ,然后从 Toeplitz型矩阵的特殊结构出发 ,利用上述定理的结论 ,给出了Toeplitz型矩阵的逆矩阵的一种快速三角分解算法 ,算法所需运算量为 O( mn2 ) .最后 ,数值计算表明该算法的可靠性 .     

基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数．     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

r－轮换矩阵快速求逆算法的推广

ｒ－轮换矩阵快速求逆算法的推广成礼智（国防科技大学）ＴＨＥＧＥＮＥＲＡＬＩＺＡＴＩＯＮＯＦＴＨＥＦＡＳＴＡＬＧＯＲＩＴＨＭＦＯＲＩＮＶＥＲＴＩＮＧｒ－ＣＩＲＣＵＬＡＮＴＭＡＴＲＩＣＥＳ￥ＣｈｅｎｇＬｉ－ｚｈｉ（ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆ...     

求鳞状因子循环矩阵的逆阵及广义逆阵的快速付氏变换法

借助快速付立叶变换(FFT),本文给出一种求n阶鳞状因子循环矩阵的逆阵、自反g-逆、群逆、Moore-Penrose逆的快速算法,该算法的计算复杂性为O(nlog2n),最后给出的两个数值算例表明了该算法的有效性.     

Methods of solving Fredholm equations optimal on classes of functions

This paper is devoted to the solution of linear Fredholm equations in the unit s-dimensional cube for classes of functions with a dominant mixed derivative of order r in each variable. We present an algorithm for obtaining the solution over the whole domain with an error O(N^?r ln^2s?1 N) in the uniform metric using the values of the given functions at O(N ln^2s?1 N) points and consisting of O(N ln^2s?1 N) elementary operations. We show that these estimates can only be improved at the expense of the exponent of ln N.     

Approximation of a bending plate problem with a boundary unilateral constraint

Summary We study a variational formulation of the unilaterally supported bent plate problem and we analyze the approximation of the problem by a mixed finite element method. We proveO(h) andO(h|lnh|^1/2) error bounds respectively for the moments and the displacement.Work partially supported by M.P.I., by G.N.I.M. of C.N.R. and by I.A.N. of C.N.R. of Pavia     

FAST DENSE MATRIX METHOD FOR THE SOLUTION OF INTEGRAL EQUATIONS OF THE SECOND KIND

We present a fast algorithm based on polynomial interpolation to approximate matrices arising from the discretization of second-kind integral equations where the kernel function is either smooth, non-oscillatory and possessing only a finite number of singularities or a product of such function with a highly oscillatory coefficient function. Contrast to wavelet-like approximations, ourapproximation matrix is not sparse. However, the approximation can be construced in O(n) operations and requires O(n) storage, where n is the number of quadrature points used in the discretization. Moreover, the matrix-vector multiplication cost is of order O(nlogn). Thus our scheme is well suitable for conjugate gradient type methods. Our numerical results indicate that the algorithm is very accurate and stable for high degree polynomial interpolation.     

Block seriation problems: A unified approach. Reply to the problem of H. Garcia and J. M. Proth (Applied Stochastic Models and Data Analysis, 1, (1), 25–34 (1985))

In their article, entitled ‘Group technology in production management, the short horizon planning level’, H. Garcia and J. M. Proth have stated the following problem: starting from a (0, 1) binary matrix of size (N x M), how to divide into independent subsets the rows of this matrix simultaneously with a one-to-one corresponding partition of the columns, maximizing the presence of 1s in the intersecting blocks with a joint minimization of the presence of 0s outside of these blocks. The authors have proposed an efficient and very fast heuristic algorithm in comparison with the existing methods of a fast-growing literature on the subject. The only drawback of this algorithm is its dependence on the initial partition. In this paper, we try to improve this algorithm slightly, first in rewriting the objective function in a linear form and secondly in giving computational improvements related to this linear formulation.