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))点     

多重三角T阵与多元多项式的快速除法

我们在[1]中给出了求三角形T矩阵的逆和计算一元多项式除法的O(nlogn)算法,改进了这两个问题已有的工作量为O(nlog~2n)的快速算法。本文给出了多重三角T阵的乘积、求逆和多元多项式的快速除法等快速方法,推广了[1]和[2]的结果。为叙述简便,我们仅就二重上三角形T阵与二元多项式除法讨论。由此不难推广到一般情形。     

数论在数字信号处理中的应用

今天,在几乎所有的工程领域中,都需要运用各种数学变换、通过计算机对数字信号进行处理,因此,这些变换成了数字信号处理中的一种重要的工具. 数字信号处理中两个最基本的运算是计算离散付里叶变换(DFT)和卷积.为了快速计算它们,最近,出现了好几种新的数学变换,例如计算卷积的数论变换(NTT),计算DFT的Winograd变换(WFTA)等等,这些变换的乘法次数比熟知的快速付里叶变换(FFT)要少.所有这些变换有一个共同的特点,就是以数论作为它们的数学工具.1979年,国外已写出专著,总结了这方面的工作;1980年,国内这方面的一些工作也写进了著作[2].本文将扼要介绍国内外这方面的工作.为了后面叙述方便,这里先介绍一下卷     

一个组合条件等式与高阶等差数列方幂和

关于正数等差数列和一般等差数列方幂和的计算问题,及万会同志和笔者曾撰文给出其计算方法。(见[1]、[2]) 本文对一类典型的组合问题进行一般性的推广,得到了该类问题的通解及几个推论,推广了文[4]、[5]的主要结论。最后使用本文结     

由渠道设计问题引出的有向图上最小树形图问题的解法

在[1]中首先提出求一般有向图的最小树形图的计算方法。以后,在[2]中,对于一类特殊的有向图,即等双回路图,指出了[1]中的方法可以改进,使得计算的速度可以加快。 在最小树形图的实际应用中,渠道设计问题是一个重要的方面,[1]与[2]中都以此问题作为最小树形图问题的实际背景之一。本文将指出,对于由渠道设计问题引出的有向图上求最小树形图问题,可以用一种更简单的、推广起来也可能是更容易的方法来解决。     

用快速多项式变换(FPT)计算二维离散富里叶变换(DFT)

一 引言 H.J.Nussbaumer和P.Quandalle在[1]中引入了多项式变换並用它计算数字卷积和离散富里叶变换[2],[3]。我们在[4]中详细的研究了模M(z)是可约多项式时变换存在的条件,並用它来计算两个多项式的乘积[5]。本文研究用FPT计算二维DFT的方法。结果表明,当N=2~(m-r+1),M=2~m(1≤r≤m)时,所用的加法次数与通常以2为基     

离散椭圆型方程的矩阵方程表示及其直接解法

在[1]中讨论了解离散椭圆型方程的直接法,[2]、[3]中在椭圆型方程的类型和区域上得到了进一步的推广.它们的优点是计算起来快速且仅需要极小的存贮量.本文把求解的线性方程组写成矩阵方程形式,进一步发展矩阵分解法.首先,为了简单,如[1]那样考虑方程组     

三维DFT的FPT算法

本导出了一种三堆离散富氏变换(DFT)的快速多项式变换(FPT)算法，并对该算法的计算量与通常所用算法(行列法)进行了比较，最后对算法的优劣作了总结．     

具孤立奇点的映照的第二类相对上同调

<正> 在[6]中我们定义了两种相对上同调,并对在奇点处有有限重数的超曲面作了计算.G.-M.Greuel提出下述问题:[6]中哪些结果能推广到具孤立奇点的完全交叉.在[7]中我们把[6]中第一类相对上同调的计算推广到映照芽.本文把[6]中第二类相对上同调的计算推广到具孤立奇点的映照.     

n元函数极值的探讨

在高等数学或数学分析的教学中，经常遇到这样的问题：如何将二元函数求极值的方法推广到，n元函数中去。这一问题在教材中很小涉及，本在[1]、[2]基础上，讨论了，n(n≥2)元函数极值点的判别法，确立了判别临界点为极值点的一个充分条件。这些条件与[1]、[2]的方法是等价的，但方法简单。