首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 96 毫秒
1.
Orderly Algorithm to Enumerate Central Groupoids and Their Graphs   总被引:1,自引:0,他引:1  
A graph has the unique path property UPPn if there is a unique path of length n between any ordered pair of nodes. This paper reiterates Royle and MacKay's technique for constructing orderly algorithms. We wish to use this technique to enumerate all UPP2 graphs of small orders 3^2 and 4^2. We attempt to use the direct graph formalism and find that the algorithm is inefficient. We introduce a generalised problem and derive algebraic and combinatoric structures with appropriate structure. Then we are able to design an orderly algorithm to determine all UPP2 graphs of order 3^2, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 4^2 in the near future.  相似文献   

2.
韩燕 《东北数学》2007,23(3):272-282
Due to its complexities in both mathematicM formulations and applications, universal co-kriging (UCK) has not been sufficiently discussed in literature. An extended and simpler matrix formulation UCK with incorporation of a polynomial variable trend is proposed in this paper. Estimators of the value and expectation of a regionMized vector taken in a point are obtained on the basis of cross-covaxiance and cross-vaxiogram, respectively. The complex expressions of co-kriging with trend are greatly simplified by introducing special matrix operations, such as Kronecker product, into the formulations. This simplification offers a feasible and easier approach for computer coding of the UCK, and helps the practitioners to use the UCK technique conveniently in real cases.  相似文献   

3.
The Markov property of Markov process functionals which are frequently used in economy, finance, engineering and statistic analysis is studied. The conditions to judge Markov property of some important Markov process functionals are presented, the following conclusions are obtained: the multidimensional process with independent increments is a multidimensional Markov process; the functional in the form of path integral of process with independent increments is a Markov process; the surplus process with the doubly stochastic Poisson process is a vector Markov process. The conditions for linear transformation of vector Markov process being still a Markov process are given.  相似文献   

4.
The purpose of this paper is to provide an error analysis for the multicategory support vector machine (MSVM) classificaton problems. We establish the uniform convergency approach for MSVMs and estimate the misclassification error. The main difficulty we overcome here is to bound the offset vector. As a result, we confirm that the MSVM classification algorithm with polynomial kernels is always efficient when the degree of the kernel polynomial is large enough. Finally the rate of convergence and examples are given to demonstrate the main results.  相似文献   

5.
An effcient algorithm for deciding whether a given integer vector is thespectrum of some Boolean function is presented.The algorithm performs astep-by-step spectral decomposition of the input vector and checks at eachstep a set of necessary conditions for spectrality for the resulting vectors.The algorithm concludes that the input vector cannot lead to a valid Booleanfunction as soon as a vector not satisfying the conditions is found,which,as proved in the paper,for almost all cases happens after the first step ofthe decomposition.  相似文献   

6.
Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.  相似文献   

7.
Subdivision algorithm (Stationary or Non-stationary) is one of the most active and exciting research topics in wavelet analysis and applied mathematical theory. In multidimensional non-stationary situation, its limit functions are both compactly supported and infinitely differentiable. Also, these limit functions can serve as the scaling functions to generate the multidimensional non-stationary orthogonal or biorthogonal semi-multiresolution analysis (Semi-MRAs). The spectral approximation property of multidimensional non-stationary biorthogonal Semi-MRAs is considered in this paper. Based on nonstationary subdivision scheme and its limit scaling functions, it is shown that the multidimensional nonstationary biorthogonal Semi-MRAs have spectral approximation order r in Sobolev space H^s(R^d), for all r ≥ s ≥ 0.  相似文献   

8.
The convergence analysis of a nonlinear Lagrange algorithm for solving nonlinear constrained optimization problems with both inequality and equality constraints is explored in detail. The estimates for the derivatives of the multiplier mapping and the solution mapping of the proposed algorithm are discussed via the technique of the singular value decomposition of matrix. Based on the estimates, the local convergence results and the rate of convergence of the algorithm are presented when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions. Furthermore, the condition number of the Hessian of the nonlinear Lagrange function with respect to the decision variables is analyzed, which is closely related to efficiency of the algorithm. Finally, the preliminary numericM results for several typical test problems are reported.  相似文献   

9.
This article proposes a method for fitting models subject to a convex and log-convex constraint on the probability vector of a product multinomial (binomial) distribution. We present an iterative algorithm for finding the restricted maximum likelihood estimates (MLEs) of the probability vector and show that the algorithm converges to the true solution. Some examples are discussed to illustrate the method.  相似文献   

10.
We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.  相似文献   

11.
A new fast algorithm is presented for the multidimensional discrete Fourier transform (DFT). This algorithm is derived using an interesting technique called “vector coding” (VC), and we call it the vector-coding fast Fourier transform (VC-FFT) algorithm. Since the VC-FFT is an extension of the Cooley–Tukey algorithm from 1-D to multidimensional form, the structure of the program is as simple as the Cooley–Tukey fast Fourier transform (FFT). The new algorithm significantly reduces the number of multiplications and recursive stages. The VC-FFT therefore comprehensively reduces the complexity of the algorithm as compared with other current multidimensional DFT algorithms.  相似文献   

12.
A variant of the Cooley-Tukey algorithm due to Stockham is derived and vectorized and is shown to be on a par with the Pease algorithm. The Stockham algorithm is then proposed for the entire computation of the two-dimensional fast Fourier transform on a vector computer.  相似文献   

13.
An approach to reducing large computational time in the problem of multidimensional dichotomous data structuring based on algebraic properties of finite geometries is proposed. A vector parameterization of the Grassmannian Gr2(k, n) reducing memory expenditures and the number of operations required to solve this problem is introduced. A parallelization algorithm based on this parameterization and Gray coding which further reduces computational time is constructed.  相似文献   

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

15.
针对非一致并行机环境下特殊工艺约束提前/拖后调度问题,设计了一个基于向量组编码的新遗传算法,此算法的编码方法简单,能有效地反映实际调度方案,即清楚地反映出每机器加工产品的代号和顺序.引入浓度概念,对种群中浓度高的个体进行抑制,从而增加群体多样性,同时,利用爬山算法对种群中个体进行局部搜索,提高了种群质量,加快了收敛速度.仿真结果表明,此算法是有效的,适用于解实际的此类调度问题.  相似文献   

16.
冯德修 《计算数学》1981,3(3):268-271
在J.L.Shanks的基础上,给出了产生离散叙率Walsh函数的迭代方程,由迭代 方程推出了离散Walsh 函数的表达式和Walsh变换的速算 法(FWWT).  相似文献   

17.
运用小波变换进行图像压缩的算法其核心都是小波变换的多分辨率分析以及对不同尺度的小波系数的量化和编码 .本文提出了一种基于能量的自适应小波变换和矢量量化相结合的压缩算法 .即在一定的能量准则下 ,根据子图像的能量大小决定是否进行小波分解 ,然后给出恰当的小波系数量化 .在量化过程中 ,采用一种改进的LBG算法进行码书的训练 .实验表明 ,本算法广泛适用于不同特征的数字图像 ,在取得较高峰值信噪比的同时可以获得较高的重建图像质量 .  相似文献   

18.
Fractal image compression is a promising technique to improve the efficiency of image storage and image transmission with high compression ratio, however, the huge time consumption for the fractal image coding is a great obstacle to the practical applications. In order to improve the fractal image coding, efficient fractal image coding algorithms using a special unified feature and a DCT coder are proposed in this paper. Firstly, based on a necessary condition to the best matching search rule during fractal image coding, the fast algorithm using a special unified feature (UFC) is addressed, and it can reduce the search space obviously and exclude most inappropriate matching subblocks before the best matching search. Secondly, on the basis of UFC algorithm, in order to improve the quality of the reconstructed image, a DCT coder is combined to construct a hybrid fractal image algorithm (DUFC). Experimental results show that the proposed algorithms can obtain good quality of the reconstructed images and need much less time than the baseline fractal coding algorithm.  相似文献   

19.
Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is minimization of a multimodal function with unfavorable properties like invariants and non-differentiability. Recently a branch and bound algorithm for multidimensional scaling with city-block distances has been proposed for solution of medium-size problems exactly. The algorithm exploits piecewise quadratic structure of the objective function. In this paper a parallel version of the branch and bound algorithm for multidimensional scaling with city-block distances has been proposed and investigated. Parallel computing enabled solution of larger problems what was not feasible with the sequential version.  相似文献   

20.
Sampling from a truncated multivariate normal distribution (TMVND) constitutes the core computational module in fitting many statistical and econometric models. We propose two efficient methods, an iterative data augmentation (DA) algorithm and a non-iterative inverse Bayes formulae (IBF) sampler, to simulate TMVND and generalize them to multivariate normal distributions with linear inequality constraints. By creating a Bayesian incomplete-data structure, the posterior step of the DA algorithm directly generates random vector draws as opposed to single element draws, resulting obvious computational advantage and easy coding with common statistical software packages such as S-PLUS, MATLAB and GAUSS. Furthermore, the DA provides a ready structure for implementing a fast EM algorithm to identify the mode of TMVND, which has many potential applications in statistical inference of constrained parameter problems. In addition, utilizing this mode as an intermediate result, the IBF sampling provides a novel alternative to Gibbs sampling and eliminates problems with convergence and possible slow convergence due to the high correlation between components of a TMVND. The DA algorithm is applied to a linear regression model with constrained parameters and is illustrated with a published data set. Numerical comparisons show that the proposed DA algorithm and IBF sampler are more efficient than the Gibbs sampler and the accept-reject algorithm.  相似文献   

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

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