首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 421 毫秒
1.
求格的覆盖半径是一个经典的困难问题,当格的维数不固定时,这个问题还没有非确定性的多项式时间的算法.已知的算法都是通过求Voronoi cell来计算覆盖半径,对于二维格,文章利用高斯算法给出了一个确定性的多项式时间的算法来求覆盖半径以及deep holes.  相似文献   

2.
如我们所知,诸如视频和图像等信号可以在某些框架下被表示为稀疏信号,因此稀疏恢复(或稀疏表示)是信号处理、图像处理、计算机视觉、机器学习等领域中被广泛研究的问题之一.通常大多数在稀疏恢复中的有效快速算法都是基于求解$l^0$或者$l^1$优化问题.但是,对于求解$l^0$或者$l^1$优化问题以及相关算法所得到的理论充分性条件对信号的稀疏性要求过严.考虑到在很多实际应用中,信号是具有一定结构的,也即,信号的非零元素具有一定的分布特点.在本文中,我们研究分片稀疏恢复的唯一性条件和可行性条件.分片稀疏性是指一个稀疏信号由多个稀疏的子信号合并所得.相应的采样矩阵是由多个基底合并组成.考虑到采样矩阵的分块结构,我们引入了子矩阵的互相干性,由此可以得到相应$l^0$或者$l^1$优化问题可精确恢复解的稀疏度的新上界.本文结果表明.通过引入采样矩阵的分块结构信息.可以改进分片稀疏恢复的充分性条件.以及相应$l^0$或者$l^1$优化问题整体稀疏解的可靠性条件.  相似文献   

3.
已有关于高阶导数有理插值方法的研究大都是基于广义范德蒙逆矩阵的思想,计算复杂度较高.本文利用埃米特插值基函数的方法和多项式插值的误差性质,给出一种满足高阶导数插值条件的切触有理插值算法,并且适用于向量值切触有理插值及插值重度不相等的情形,解决切触有理插值函数的存在性及算法复杂性问题.较之其他算法,具有计算复杂度较低,便于实际应用等特点.最后通过数值例子说明该算法的有效性.  相似文献   

4.
以牛顿多胞型技术为基础,根据牛顿多胞型中的点与点之间的相关性,给出了直接搜索多项式配平方和所需的最基本的项集Xs的算法,利用精确的符号算法PCAD,可将一类半正定多项式配成平方和,并编写了Maple程序"ASSOS",实现了多项式配平方和的自动生成.由多项式结构的稀疏性,此算法更能有效处理稀疏多项式.这一算法提高了多项式配平方和的效率,从而促进了一类代数不等式可读性证明的自动生成.除此之外,还给出了多项式不能表示为平方和的一个充分条件.  相似文献   

5.
图G=(V, E;f,ω)是顶点和边都赋权的树,f:V→R+,ω:E→R+.本文给出了顶点u与v之间距离的一种新的定义.在顶点和边都赋权的树中,研究在新距离条件下的r-控制集问题与k-中心问题.对于r-控制集问题,设计出了复杂性为Ο(n)的多项式时间算法;对于k-中心问题,设计出了Ο(n2log n)的多项式时间算法.  相似文献   

6.
仪洪勋 《数学杂志》1989,9(4):409-414
本文研究了微分多项式的值分布问题,得出了关于微分多项式的亏量的几个结果,改进了C.C.Yang,W.K.Hayman,L.R.Sons and W.Doeringer等人的有关定理,还用例子证明了本文定理的结果是最佳的。  相似文献   

7.
本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.  相似文献   

8.
基于GMRES的多项式预处理广义极小残差法   总被引:3,自引:0,他引:3  
全忠  向淑晃 《计算数学》2006,28(4):365-376
求解大型稀疏线性方程组一般采用迭代法,其中GMRES(m)算法是一种非常有效的算法,然而该算法在解方程组时,可能发生停滞.为了克服算法GMRES(m)解线性系统Ax=b过程中可能出现的收敛缓慢或不收敛,本文利用GMRES本身构造出一种有效的多项式预处理因子pk(z),该多项式预处理因子非常简单且易于实现.数值试验表明,新算法POLYGMRES(m)较好地克服了GMRES(m)的缺陷.  相似文献   

9.
线性复杂度和2-adic复杂度是衡量序列伪随机性的两个重要指标.文章研究这两个指标之间的关系,证明了由不可约多项式生成的LFSR序列簇的极小连接数达到最大可能值,即2~T-1,其中T为不可约多项式的周期,进而该序列簇的2-adic复杂度与对称2-adic复杂度均达到最大可能取值.特别地,当限定不可约多项式是本原多项式时,即可得到m-序列的相应结论.  相似文献   

10.
申子慧  申培萍 《应用数学》2019,32(1):176-182
本文针对线性比式和优化问题提出一个完全多项式时间近似算法,该算法主要利用原问题的等价问题及网格结点参数获得有限个与结点参数相关的线性规划问题,通过求解这些线性规划问题获得原问题的近似最优解.最终证明算法的收敛性,并给出了算法的计算复杂度,通过计算结果呈现算法的有效性与可行性.  相似文献   

11.
We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton polytope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterion in toric varieties.  相似文献   

12.
Ariyawansa and Zhu have proposed a new class of optimization problems termed stochastic semidefinite programs to handle data uncertainty in applications leading to (deterministic) semidefinite programs. For stochastic semidefinite programs with finite event space, they have also derived a class of volumetric barrier decomposition algorithms, and proved polynomial complexity of certain members of the class. In this paper, we consider homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. We show how the structure in such problems may be exploited so that the algorithms developed in this paper have complexity similar to those of the decomposition algorithms mentioned above.  相似文献   

13.
A system of algebraic equations over a finite field is called sparse if each equation depends on a small number of variables. In this paper new deterministic algorithms for solving such equations are presented. The mathematical expectation of their running time is estimated. These estimates are at present the best theoretical bounds on the complexity of solving average instances of the above problem. In characteristic 2 the estimates are significantly lower the worst case bounds provided by SAT solvers.  相似文献   

14.
《Journal of Complexity》1996,12(2):134-166
Sparse elimination exploits the structure of a multivariate polynomial by considering its Newton polytope instead of its total degree. We concentrate on polynomial systems that generate zero-dimensional ideals. A monomial basis for the coordinate ring is defined from a mixed subdivision of the Minkowski sum of the Newton polytopes. We offer a new simple proof relying on the construction of a sparse resultant matrix, which leads to the computation of a multiplication map and all common zeros. The size of the monomial basis equals the mixed volume and its computation is equivalent to computing the mixed volume, so the latter is a measure of intrinsic complexity. On the other hand, our algorithms have worst-case complexity proportional to the volume of the Minkowski sum. In order to derive bounds in terms of the sparsity parameters, we establish new bounds on the Minkowski sum volume as a function of mixed volume. To this end, we prove a lower bound on mixed volume in terms of Euclidean volume which is of independent interest.  相似文献   

15.
《Journal of Complexity》2005,21(1):43-71
Our first contribution is a substantial acceleration of randomized computation of scalar, univariate, and multivariate matrix determinants, in terms of the output-sensitive bit operation complexity bounds, including computation modulo a product of random primes from a fixed range. This acceleration is dramatic in a critical application, namely solving polynomial systems and related studies, via computing the resultant. This is achieved by combining our techniques with the primitive-element method, which leads to an effective implicit representation of the roots. We systematically examine quotient formulae of Sylvester-type resultant matrices, including matrix polynomials and the u-resultant. We reduce the known bit operation complexity bounds by almost an order of magnitude, in terms of the resultant matrix dimension. Our theoretical and practical improvements cover the highly important cases of sparse and degenerate systems.  相似文献   

16.
We consider the problem of recognizing AT-free graphs. Although there is a simple O(n3) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in , , and O(n2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.  相似文献   

17.
Rational Arnoldi is a powerful method for approximating functions of large sparse matrices times a vector. The selection of asymptotically optimal parameters for this method is crucial for its fast convergence. We present and investigate a novel strategy for the automated parameter selection when the function to be approximated is of Cauchy–Stieltjes (or Markov) type, such as the matrix square root or the logarithm. The performance of this approach is demonstrated by numerical examples involving symmetric and nonsymmetric matrices. These examples suggest that our black-box method performs at least as well, and typically better, as the standard rational Arnoldi method with parameters being manually optimized for a given matrix.  相似文献   

18.
We present a new computational approach to approximating a large, noisy data table by a low-rank matrix with sparse singular vectors. The approximation is obtained from thresholded subspace iterations that produce the singular vectors simultaneously, rather than successively as in competing proposals. We introduce novel ways to estimate thresholding parameters, which obviate the need for computationally expensive cross-validation. We also introduce a way to sparsely initialize the algorithm for computational savings that allow our algorithm to outperform the vanilla singular value decomposition (SVD) on the full data table when the signal is sparse. A comparison with two existing sparse SVD methods suggests that our algorithm is computationally always faster and statistically always at least comparable to the better of the two competing algorithms. Supplementary materials for the article are available in an online appendix. An R package ssvd implementing the algorithms introduced in this article is available on CRAN.  相似文献   

19.
We investigate multiplication algorithms for dense and sparse polynomials and polynomial matrices over different numerical domains and obtain expressions for the complexity of multiplication of polynomials and polynomial matrices understood as the expectation of the number of arithmetic operations. These expressions for a set of parameters of practical interest are tabulated. The results of experiments with the corresponding programs are presented. Bibliography: 8 titles.  相似文献   

20.
This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.  相似文献   

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

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