Highly symmetric bi-frames for triangle surface multiresolution processing

In this paper we investigate the construction of dyadic affine (wavelet) bi-frames for triangular-mesh surface multiresolution processing. We introduce 6-fold symmetric bi-frames with 4 framelets (frame generators). 6-fold symmetric bi-frames yield frame decomposition and reconstruction algorithms (for regular vertices) with high symmetry, which is required for the design of the corresponding frame multiresolution algorithms for extraordinary vertices on the triangular mesh. Compared with biorthogonal wavelets, the constructed bi-frames have better smoothness and smaller supports. In addition, we also provide frame multiresolution algorithms for extraordinary vertices. All the frame algorithms considered in this paper are given by templates (stencils) so that they are implementable. Furthermore, we present some preliminary experimental results on surface processing with frame algorithms constructed in this paper.     

Conditions for variable-metric algorithms to be conjugate-gradient algorithms

Variable-metric algorithms have played an important role in unconstrained optimization theory. This paper presents a sufficiency condition on the sequence of metrics in a variable-metric algorithm that will make it a conjugate-gradient algorithm. The Huang class of algorithms (Ref. 1) and the class of self-scaling variable-metric algorithms by Oren (Ref. 2) all satisfy the condition. This paper also includes a discussion of the behavior of algorithms that meet the condition on nonquadratic functions.     

A numerical evaluation of some collinear scaling algorithms for unconstrained

Collinear scaling algorithms for unconstrained minimization were first proposed by Davidon (1977,80) so that they may incorporate more information about the problem than is possible with quasi–Newton algorithms. Sorensen (1980,82), and Ariyawansa (1983,90) have derived collinear scaling algorithms as natural extensions of quasi–Newton algorithms. In this paper we describe the results of a comprehensive numerical evaluation of four members in the classes of collinear scaling algorithms derived by Sorensen (1980,82) and Ariyawansa (1983,90), relative to the quasi–Newton algorithms they extend.     

Approximate nonlinear programming algorithms for solving stochastic programs with recourse

This paper summarizes the main results on approximate nonlinear programming algorithms investigated by the author. These algorithms are obtained by combining approximation and nonlinear programming algorithms. They are designed for programs in which the evaluation of the objective functions is very difficult so that only their approximate values can be obtained. Therefore, these algorithms are particularly suitable for stochastic programming problems with recourse.Project supported by the National Natural Science Foundation of China.     

非线性Galerkin算法的收敛性和复杂性

本文给出了数值求解非线性发展方程的全离散非线性Ｇａｌｅｒｋｉｎ算法,即将空间离散时的谱非线性Ｇａｌｅｒｋｉｎ算法和时间离散的Ｅｕｌｅｒ差分格式相结合,得到了显式和隐式两种全离散数值格式,相应地也考虑了显式和隐式的Ｇａｌｅｒｋｉｎ全离散格式,并分别分析了上述四种全离散格式的收敛性和复杂性,经过比较得出结论;在某些约束条件下,非线性Ｇａｌｅｒｋｉｎ算法和Ｇａｌｅｒｋｉｎ算法具有相同阶的收敛速度,然而前     

A comparison of sequential Delaunay triangulation algorithms

This paper presents an experimental comparison of a number of different algorithms for computing the Delaunay triangulation. The algorithms examined are: Dwyer's divide and conquer algorithm, Fortune's sweepline algorithm, several versions of the incremental algorithm (including one by Ohya, Iri and Murota, a new bucketing-based algorithm described in this paper, and Devillers's version of a Delaunay-tree based algorithm that appears in LEDA), an algorithm that incrementally adds a correct Delaunay triangle adjacent to a current triangle in a manner similar to gift wrapping algorithms for convex hulls, and Barber's convex hull based algorithm.

Most of the algorithms examined are designed for good performance on uniformly distributed sites. However, we also test implementations of these algorithms on a number of non-uniform distributions. The experiments go beyond measuring total running time, which tends to be machine-dependent. We also analyze the major high-level primitives that algorithms use and do an experimental analysis of how often implementations of these algorithms perform each operation.     

Properties of some convolution algorithms for the thermal analysis of semiconductor devices

This paper deals with three kinds of convolution algorithms designed for the thermal analysis of semiconductor devices and electronic circuits with the use of the lumped thermal models. Such kind of models and algorithms is especially convenient to analyse the electronic circuits consisting of a high number of thermally sensitive devices. The fundamental features, such as: stability, convergence and accuracy of these algorithms, are considered and investigated in the paper. In the investigations the exponential test function describing the dissipated power is taken into account. It was analytically proved that the considered algorithms are stable and convergent. The analytical formulas describing the values of the local and total cut off error of the algorithms are proposed. The theoretical considerations are accompanied by some calculation results illustrating the influence of the values of thermal parameter models and the size of the analysis step on the accuracy of calculations carried out with the considered algorithms.     

On Solving Large-Scale Finite Minimax Problems Using Exponential Smoothing

This paper focuses on finite minimax problems with many functions, and their solution by means of exponential smoothing. We conduct run-time complexity and rate of convergence analysis of smoothing algorithms and compare them with those of SQP algorithms. We find that smoothing algorithms may have only sublinear rate of convergence, but as shown by our complexity results, their slow rate of convergence may be compensated by small computational work per iteration. We present two smoothing algorithms with active-set strategies and novel precision-parameter adjustment schemes. Numerical results indicate that the algorithms are competitive with other algorithms from the literature, and especially so when a large number of functions are nearly active at stationary points.     

广义非线性集值混合拟变分包含的扰动近似点算法

本文研究一类广义非线性集值混合拟变分包含,概括了尚明生等人引入与研究过的熟知的广义集值变分包含类成特例.运用预解算子的技巧,建立了广义非线性集值混合拟变分包含与不动点问题之间的等价性,其中,预解算子JρA(·,x)是具有常数1/(1+cρ)的Lipschitz连续算子.本文还建立了几个扰动迭代算法,并提供了由算法生成的逼近解的收敛判据,所得算法与结果改进与推广了尚明生等人的相应算法与结果.     

A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization

This paper shows how evolutionary algorithms can be described in a concise, yet comprehensive and accurate way. A classification scheme is introduced and presented in a tabular form called TEA (Table of Evolutionary Algorithms). It distinguishes between different classes of evolutionary algorithms (e.g., genetic algorithms, ant systems) by enumerating the fundamental ingredients of each of these algorithms. At the end, possible uses of the TEA are illustrated on classical evolutionary algorithms.     

求解线性方程组的顺序算法和并行算法的理论时耗估价

本文讨论了求解密集型线性方程组的两种并行算法。这两种算法都在下上单元(LU)分解。法的基础上使用了前向和后向置换进行的。这些算法在数值上是稳定的,并在顺序平衡机上用各种处理程序进行试验,都得到良好效果。     

On the convergence of generalized Schwarz algorithms for solving obstacle problems with elliptic operators

In this paper, multiplicative and additive generalized Schwarz algorithms for solving obstacle problems with elliptic operators are developed and analyzed. Compared with the classical Schwarz algorithms, in which the subproblems are coupled by the Dirichlet boundary conditions, the generalized Schwarz algorithms use Robin conditions with parameters as the transmission conditions on the interface boundaries. As a result, the convergence rate can be speeded up by choosing Robin parameters properly. Convergence of the algorithms is established. This work was supported by 973 national project of China (2004CB719402) and by national nature science foundation of China (10671060).     

Biased random-key genetic algorithms for combinatorial optimization

Random-key genetic algorithms were introduced by Bean (ORSA J. Comput. 6:154–160, 1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are a variant of random-key genetic algorithms, where one of the parents used for mating is biased to be of higher fitness than the other parent. After introducing the basics of biased random-key genetic algorithms, the paper discusses in some detail implementation issues, illustrating the ease in which sequential and parallel heuristics based on biased random-key genetic algorithms can be developed. A survey of applications that have recently appeared in the literature is also given.     

A unified approach to the feasible point method type for nonlinear programming with linear constraints under degeneracy and the convergence properties

In this paper, we introduce a general class of feasible point algorithms for solving nonlinear programming problems with linear constraints under degeneracy. Many wellknown algorithms are its special cases. Also, many new algorithms can be derived from this general class. Under rather simple conditions, we prove the global convergence property for this class of algorithms.This research was partially supported by the National Natural Science Foundation of China. The first author's research was partially also supported by the National Science Foundation of the United States of America under Grant DCR-86-96135.     

解带有Hilbert核的奇异积分方程的高精度组合算法

该文给出了用求积法解带Hilber核的奇异积分方程的高精度组合算法.把网格点分成互不相交的子集合, 在子集合上并行求解离散方程组, 再利用组合算法求得全局网格点的逼近.如果积分方程的系数属于B_δ, 则求积法的精度可达O(e^-nδ). 此外, 使用组合算法不仅能得到更高的精度阶, 而且能够得到后验误差估计. 数值算例的结果表明组合算法是极其有效的.     

Weak and strong convergence theorems for variational inequality problems

In this paper, we study the weak and strong convergence of two algorithms for solving Lipschitz continuous and monotone variational inequalities. The algorithms are inspired by Tseng’s extragradient method and the viscosity method with Armijo-like step size rule. The main advantages of our algorithms are that the construction of solution approximations and the proof of convergence of the algorithms are performed without the prior knowledge of the Lipschitz constant of cost operators. Finally, we provide numerical experiments to show the efficiency and advantage of the proposed algorithms.     

Comparison of strategy learning methods in Farmer–Pest problem for various complexity environments without delays

In this paper effectiveness of several agent strategy learning algorithms is compared in a new multi-agent Farmer–Pest learning environment. Learning is often utilized by multi-agent systems which can deal with complex problems by means of their decentralized approach. With a number of learning methods available, a need for their comparison arises. This is why we designed and implemented new multi-dimensional Farmer–Pest problem domain, which is suitable for benchmarking learning algorithms. This paper presents comparison results for reinforcement learning (SARSA) and supervised learning (Naïve Bayes, C4.5 and Ripper). These algorithms are tested on configurations with various complexity with not delayed rewards. The results show that algorithm performances depend highly on the environment configuration and various conditions favor different learning algorithms.     

Relaxation methods for solving the tensor equation arising from the higher‐order Markov chains

In this paper, we propose several relaxation algorithms for solving the tensor equation arising from the higher‐order Markov chain and the multilinear PageRank. The semi‐symmetrization technique on the original equation is also employed to modify the proposed algorithms. The convergence analysis is given for the proposed algorithms. It is shown that the new algorithms are more efficient than the existing ones by some numerical experiments when relaxation parameters are chosen suitably.     

Parallel coarse‐grid selection

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse‐grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse‐grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd.