首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 203 毫秒
1.
In this paper, a fast algorithm for the discrete sine transform(DST) of a Toeplitz matrix of order N is derived. Only O(N log N) O(M) time is needed for the computation of M elements. The auxiliary storage requirement is O(N). An application of the new fast algorithm is also discussed.  相似文献   

2.
Based on the corrected finite pointset method (CFPM) with CPU-GPU heteroid parallelization (CFPM-GPU), a high-efficiency, accurate and fast parallel algorithm was developed for the high-dimensional phase separation phenomena governed by the multi-component Cahn-Hilliard (C-H) equation in complex domains. The proposed parallel algorithm with the CFPM-GPU was built in a process like: ① introduce the Wendland weight function into the discretization of the finite pointset method (FPM) scheme for the 1st/2nd spatial derivatives, based on the Taylor series and the weighted least square concept; ② use the above FPM scheme twice to approximate the 4th spatial derivative in the C-H equation, which is called the CFPM method; ③ for the first time establish an accelerating parallel algorithm for the CFPM with local matrices by means of a single GPU card based on the CUDA programming. Two benchmark problems of 2D radially and 3D spherically symmetric C-H equations were first solved to test the accuracy and high-efficiency of the proposed CFPM-GPU, and the acceleration ratio of the GPU parallelization to the single CPU computation is about 160. Subsequently, the proposed CFPM-GPU was used to predict the 2D/3D multi-phase separation phenomena in complex domains, and the prediction was compared with other numerical results. The numerical results show that, the proposed CFPM-GPU is valid and high-efficiency to simulate the 2D/3D multi-phase separation cases in complex domains. © 2023 Editorial Office of Applied Mathematics and Mechanics. All rights reserved.  相似文献   

3.
In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual interior matrices, we can construct an algorithm which is very similar to the primal-dual potential reduction algorithm of Huang and Kortanek [6] for linear programming. The complexity of the algorithm is either O(nlog(X0 · S0/ε) or O(nlog(X0· S0/ε) depends on the value of ρ in the primal-dual potential function, where X0 and S0 is the initial interior matrices of the positive semi-definite programming.  相似文献   

4.
In this paper, for the the primes p such that 3 is a divisor of p-1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(pm)(any positive integer m) with the period 3n (n and pm - 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-lmamura algorithm, we can determine the linear complexity of any sequence over GF(pm) with the period 3n (n and pm - 1 are coprime) more efficiently.  相似文献   

5.
Stochastic gradient descent(SGD) is one of the most common optimization algorithms used in pattern recognition and machine learning.This algorithm and its variants are the preferred algorithm while optimizing parameters of deep neural network for their advantages of low storage space requirement and fast computation speed.Previous studies on convergence of these algorithms were based on some traditional assumptions in optimization problems.However,the deep neural network has its unique properties.Some assumptions are inappropriate in the actual optimization process of this kind of model.In this paper,we modify the assumptions to make them more consistent with the actual optimization process of deep neural network.Based on new assumptions,we studied the convergence and convergence rate of SGD and its two common variant algorithms.In addition,we carried out numerical experiments with LeNet-5,a common network framework,on the data set MNIST to verify the rationality of our assumptions.  相似文献   

6.
This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O(n~(1/2)L) iteration complexity which is the best result for convex quadratic programming so far.  相似文献   

7.
In this paper, we introduce for the first time a new eligible kernel function with a hyperbolic barrier term for semidefinite programming(SDP). This add a new type of functions to the class of eligible kernel functions. We prove that the interior-point algorithm based on the new kernel function meets O(n3/4 logε/n)iterations as the worst case complexity bound for the large-update method. This coincides with the complexity bound obtained by the first kernel function with a trigonometri...  相似文献   

8.
In this paper the continous finite element to solve initinal value problem for system of linear differential equations is used, and the absolute stability of the corresponding single step k-order hidden shceme is discussed. In the paper by simplified means, the superconvergence of finite element and one of it on the nodes are proved. Using the continuous finite element to solve linear Hamilton systems: Pt = Hq,qt = -Hp, the conservation of energy H(p,q) = 1/2 ap^2 bpq 1/2 cq^2 can be obtained. The computation shows that even if division is regular and the error of finite element Ph, qh is big, H(ph, qh) is almost equal H(p, q) in the range of computation accuracy.  相似文献   

9.
This paper deals with blowing up of solutions to the Cauchy problem for a class of general- ized Zakharov system with combined power-type nonlinearities in two and three space dimensions. On the one hand, for c0 = +∞ we obtain two finite time blow-up results of solutions to the aforementioned system. One is obtained under the condition α≥ 0 and 1 + 4/N ≤ p N +2/N-2 or α 0 and 1 p 1 + 4/N (N = 2, 3); the other is established under the condition N = 3, 1 p N +2/N-2 and α(p-3) ≥ 0. On the other hand, for c0 +∞ and α(p-3) ≥ 0, we prove a blow-up result for solutions with negative energy to the Zakharov system under study.  相似文献   

10.
In this paper, a general algorithm for the computation of the Fourier coefficients of 2π-periodic(continuous) functions is developed based on Dirichlet characters, Gauss sums and the generalized M¨obius transform. It permits the direct extraction of the Fourier cosine and sine coefficients. Three special cases of our algorithm are presented. A VLSI architecture is presented and the error estimates are given.  相似文献   

11.
从所周知,循环卷积和离散富里叶变换(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))点  相似文献   

12.
王元 《数学学报》1956,6(4):565-582
<正> 引言 本文之目的是在證明作者在[1]內所提及的若干結果,本文所有的結果,均在廣義的Riemann猜測之下,而獲得的. 現在,先將廣義的Riemann猜測述於下:  相似文献   

13.
When the sample size is $N$, the computational complexity of the least squares estimate of mean change point is O(N^2), and it's necessary to reduce the computational complexity in the case of huge data. In this paper, a two-stage fast scanning algorithm is proposed for the estimation of mean change point, and it is proved that this method has the same convergence speed and limiting distribution as the least squares estimation of mean change point, and the optimal complexity of the new algorithm is O(N^{4/3}\cdot b_n^{2/3}). We have conducted sufficient data experiments in terms of computation time and estimated efficiency, and the results show that the estimated efficiency of the new and old methods is similar, but the computation time of our method is obviously shortened.  相似文献   

14.
证明了,如果λ1,λ2,λ3,λ4是正实数,λ1/λ2是无理数和代数效,V是well-spaced序列,δ>0,那么对于ν,∈V,ν≤X,ε>0,使得|λ1p21+λ2p22+λ3p33+λ4p34-ν|<ν-δ没有素数解P1,p2,p3,p4的ν的个数不超过O(X20/21+2δ+ε).  相似文献   

15.
本文采用一簇新的核函数设计原始-对偶内点算法用于解决P*(κ)线性互补问题.通过利用一些优良、简洁的分析工具,证明该算法具有O(q(2κ+1)n1/p(logn)1+1/qlog(n/ε))迭代复杂性.  相似文献   

16.
堆垒素数论的一些新结果   总被引:1,自引:0,他引:1  
潘承洞 《数学学报》1959,9(3):315-329
<正> (?)在1937年证明了所有充分大的奇数 N 皆可表成三素数之和,即有N=p_1+p_2+p_3,其中 p_i(i=1,2,3)为奇素数.而本文的目的在于限制 p_i(i=1,2,3)的变化范围.证明了下面三个定理:定理1.°设 N 为充分大的奇数,则必有 pi(i=1,2,3)满足  相似文献   

17.
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.  相似文献   

18.
张勇 《数学进展》2021,(2):184-194
设b,c为整数,定义广义中心三项式系数Tn(b,c)=[xnx2+bx+c]n=[π/2]∑k=0(n 2k)(2k n)bn-2kck(n∈N={0,1...}),这里[xn]P(x)表示多项式P(x)中xn项的系数.特别地,中心Delannoy多项式Dn(x)=Tn(2x+1,x2+x)(n∈N),中心三项式系数Tn=Tn(1,1)(n∈N).本文研究了孙智伟在[南京大学学报:数学半年刊,2019,36(1):1-99]中提出的猜想,即完全证明了两个关于Dn(x)和的超同余式和一个关于中心三项式系数的超同余式的特殊情形.例如,设p为素数,r,m为正整数满足p■m条件.则对于任何p-adic整数x,有1/m2p3r-3(prm-1∑k=0(2k+1)Dk(x)2-P2pr-1m-1∑k=0(2k+1)Dk(x)2)=0(mod p3).  相似文献   

19.
In this paper we carry over the Björck-Pereyra algorithm for solving Vandermonde linear systems to what we suggest to call Szegö-Vandermonde systems VΦ(x), i.e., polynomial-Vandermonde systems where the corresponding polynomial system Φ is the Szegö polynomials. The properties of the corresponding unitary Hessenberg matrix allow us to derive a fast O(n2) computational procedure. We present numerical experiments that indicate that for ill-conditioned matrices the new algorithm yields better forward accuracy than Gaussian elimination.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号