高次方程正项分解上溢对策

对文献 (四川师范大学学报 (自然科学版 ) ,2 0 0 0 ,2 3(4) :4 2 5～ 4 2 6 .)介绍的高次方程正项分解方法 ,讨论其计算机程序实现时可能出现的上溢现象和对上溢现象的处理方法 .

C-means-based ant colony algorithm for TSP

To solve the traveling salesman problem with the characteristics of clustering,a novel hybrid algorithm,the ant colony algorithm combined with the C-means algorithm,is presented.In order to improve the speed of convergence,the traveling salesman problem(TSP)data is specially clustered by the C-means algorithm,then,the result is processed by the ant colony algorithm to solve the problem.The proposed algorithm treats the C-means algorithm as a new search operator and adopts a kind of local searching strategy—2-opt,so as to improve the searching performance.Given the cluster number,the algorithm can obtain the preferable solving result.Compared with the three other algorithms—the ant colony algorithm,the genetic algorithm and the simulated annealing algorithm,the proposed algorithm can make the results converge to the global optimum faster and it has higher accuracy.The algorithm can also be extended to solve other correlative clustering combination optimization problems.Experimental results indicate the validity of the proposed algorithm.

Efficient Configuration Space Construction and Optimization for Motion Planning

The configuration space is a fundamental concept that is widely used in algorithmic robotics. Many applications in robotics, computer-aided design, and related areas can be reduced to computational problems in terms of configuration spaces. In this paper, we survey some of our recent work on solving two important challenges related to configuration spaces： ~ how to efficiently compute an approximate representation of high-dimensional configuration spaces; and how to efficiently perform geometric proximity and motion planning queries （n high-dimensional configuration spaces. We present new configuration space construction algorithms based on machine learning and geometric approximation techniques. These algorithms perform collision queries on many configuration samples. The collision query results are used to compute an approximate representation for the configuration space, which quickly converges to the exact configuration space. We also present parallel GPU-based algorithms to accelerate the performance of optimization and search computations in configuration spaces. In particular, we design efficient GPU-based parallel k-nearest neighbor and parallel collision detection algorithms and use these algorithms to accelerate motion planning.

Optimal online algorithms for scheduling on two identical machines under a grade of service

This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.

A New Parallel Algorithm for Mining Association Rules

Mining association rules from large database is very costly. We develop a parallel algorithm for this task on shared-memory multiprocessor (SMP). Most proposed parallel algorithms for association rules mining have to scan the database at least two times. In this article, a parallel algorithm Scan Once (SO) has been proposed for SMP, which only scans the database once. And this algorithm is fundamentally different from the known parallel algorithm Count Distribution (CD). It adopts bit matrix to store the database information and gets the support of the frequent itemsets by adopting Vector-And-Operation, which greatly improve the efficiency of generating all frequent itemsets. Empirical evaluation shows that the algorithm outperforms the known one CD algorithm.

Microblog User Recommendation Based on Particle Swarm Optimization

Considering that there exists a strong similarity between behaviors of users and intelligence of swarm of agents,in this paper we propose a novel user recommendation strategy based on particle swarm optimization(PSO)for Microblog network. Specifically,a PSO-based algorithm is developed to learn the user influence,where not only the number of followers is incorporated,but also the interactions among users(e.g.,forwarding and commenting on other users' tweets). Three social factors,the influence and the activity of the target user,together with the coherence between users,are fused to improve the performance of proposed recommendation strategy. Experimental results show that,compared to the well-known Page Rank-based algorithm,the proposed strategy performs much better in terms of precision and recall and it can effectively avoid a biased result caused by celebrity effect and zombie fans effect.

Research on Parallel K-Medoids algorithm based on MapReduce

In order to solve the bottleneck problem of the traditional K-Medoids clustering algorithm facing to deal with massive data information at the time of memory capacity and processing speed of CPU, the paper proposed a parallel algorithm MapReduce programming model based on the research of K-Medoids algorithm. This algorithm increase the computation granularity and reduces the communication cost ratio based on the MapReduce model. The experimental results show that the improved parallel algorithm compared with other algorithms, speedup and operation efficiency is greatly enhanced.

Fast and accurate calculation of seismic wave travel time in 3D TTI media

The Tilted tilted transversely isotropic(TTI)media,a kind of anisotropic medium,widely exists within the earth.For faster calculation of travel times in the TTI anisotropic media,we modifi ed a minimum traveltime tree algorithm with high effi ciency by dynamical modifi cation of the secondary wave propagation region during the spread of seismic waves.To manage the wavefront points in the modified version,we used a novel minimum heap sorting technique to reduce the time spent on selecting secondary waves points.In this study,seismic group velocities were obtained from analytical solutions in terms of phase angle,and the corresponding phase angles were determined by binary search rather than approximate equations for weakly anisotropic media.For the most time-consuming part of the secondary wave traveltime calculation,the parallel computation was initially performed using multiple cores and threads.Numerical examples showed that the improved method can calculate seismic travel times and ray paths faster and accurately in a 3D TTI medium.For four cores and eight threads,the computing speed increased by six times when compared to the conventional method.

Decomposition Method for Complex 3D Problems in Electron Optics

The decomposition method was successfully used in solving of 3D problems with complex geometry shape in electron optics for the FDM （Finite Difference Method） and FEM （Finite Element Method） mostly to implement fast and robust parallel algorithms and computer codes. We suggest a new version of similar approach for the BEM （Boundary Element Method） based on the alternating method by Schwartz. This approach substantially reduce the dimension of dense global matrix of algebraic system produced by BEM algorithm to solve a complex problem on as single CPU （Central Processor Unit） desktop computer. New algorithm is iterative one, but exponential convergence for the Schwatlz＇s algorithm creates the fast numerical procedures. We describe the results of numerical simulation for a multi electrode ion transport system. The algorithms were implemented in the computer code ＂POISSON-3＂.

APO-Based Parallel Algorithm of Channel Allocation for Cognitive Networks

This article investigates channel allocation for cognitive networks, which is difficult to obtain the optimal allocation distribution. We first study interferences between nodes in cognitive networks and establish the channel allocation model with interference constraints. Then we focus on the use of evolutionary algorithms to solve the optimal allocation distribution. We further consider that the search time can be reduced by means of parallel computing, and then a parallel algorithm based APO is proposed. In contrast with the existing algorithms, we decompose the allocation vector into a number of sub-vectors and search for optimal allocation distribution of sub-vector in parallel. In order to speed up converged rate and improve converged value, some typical operations of evolutionary algorithms are modified by two novel operators. Finally, simulation results show that the proposed algorithm drastically outperform other optimal solutions in term of the network utilization.

Energy optimization of representative barrier algorithms

Too high energy consumption is widely recognized to be a critical problem in large-scale parallel computing systems.The LogP-based energy-saving model and the frequency scaling method were proposed to reduce energy consumption analytically and systematically for other two representative barrier algorithms:tournament barrier and central counter barrier.Furthermore,energy optimization methods of these two barrier algorithms were implemented on parallel computing platform.The experimental results validate the effectiveness of the energy optimization methods.67.12% and 70.95% energy savings are obtained respectively for tournament barrier and central counter barrier on platforms with 2048 processes with 1.55%?8.80% performance loss.Furthermore,LogP-based energy-saving analytical model for these two barrier algorithms is highly accurate as the predicted energy savings are within 9.67% of the results obtained by simulation.

The Methodology of Application Development for Hybrid Architectures

This paper provides an overview of the main recommendations and approaches of the methodology on parallel computation application development for hybrid structures. This methodology was developed within the master＇s thesis project ＂Optimization of complex tasks＇ computation on hybrid distributed computational structures＂ accomplished by Orekhov during which the main research objective was the determination of＂ patterns of the behavior of scaling efficiency and other parameters which define performance of different algorithms＇ implementations executed on hybrid distributed computational structures. Major outcomes and dependencies obtained within the master＇s thesis project were formed into a methodology which covers the problems of applications based on parallel computations and describes the process of its development in details, offering easy ways of avoiding potentially crucial problems. The paper is backed by the real-life examples such as clustering algorithms instead of artificial benchmarks.

Performance evaluations on inner vs. outer decomposition first parallel join algorithms for two nested loop joins

Two popular traditional join algorithms and their parallel versions are introduced. When designing join algorithms in serial computing environment, decomposing inner relation is considered as the right direction to save disk I/Os. However, two different decomposition algorithms are compared, such as inner vs. outer decomposition first algorithms for tuple-based and block-based nested loop joins, showing that the proposed approach is 20% better than general approach. Also lemmas are proved, when we have to use the outer decomposition first parallel join algorithms.

A Parallel Finite Element Algorithm for Navier-Stokes Equations

The authors propose a numerical algorithm for the two-dimensional Navier-Stokes equations written in stream function-vorticity formulation. The total time derivative term is treated with a first order characteristics method. The space approximation is based on a piecewise continuous finite element method. The proposed algorithm is used to simulate the mechanical aeration process in lakes. Such process is used to combat the degradation of the water quality due to the eutrophication phenomena. For this application high computing facilities and capacities are required. In order to optimize the computing time and make possible the simulation of real applications, the authors propose a parallel implementation of the numerical algorithm. The parallelization technique is performed using the Message Passing Interface. The efficiency of the proposed numerical algorithm is illustrated by some numerical results.

Fast wire segmenting algorithm considering layout density and signal integrity

A k-shortest path based algorithm considering layout density and signal integrity for good buffer candidatelocations is proposed in this paper. Theoretical results for computing the maximal distance betweenbuffers are derived under the timing, noise and slew rate constraints. By modifying the traditional uniformwire segmenting strategy and considering the impact of tile size on density penalty function, this work proposesk-shortest path algorithm to find the buffer insertion candidate locations. The experiments show thatthe buffers inserted can significantly optimize the design density, alleviate signal degradation, save thenumber of buffers inserted and the overall run time.

Real-time electromagnetic transient simulation algorithm for integrated power systems based on network level and component level parallelism

The analysis and simulation of power system are becoming more and more challenging as the complexity of system topology and components has been increased. In this paper, a hybrid parallel algorithm is proposed for the real-time electromagnetic transient simulation （EMTS） of integrated power systems containing multiphase machines. The proposed algorithm is com- posed of a novel network partition method called component level parallelization and the Multi-Area Thevenin Equivalent （MATE） method, which extends the flexibility of the network partition in parallel simulation. Moreover, several methods are developed to enhance the efficiency of the communication and computation. Power systems with up to 410 single-phase elec- trical nodes and 336 switches are simulated in a time step of 50 ~ts to validate the proposed algorithm.

A survey of numerical algorithms for trajectory optimization of flight vehicles

As one of the important components of computational flight mechanics and control,numerical algorithms of trajectory optimization for flight vehicles are currently studied by many researchers in aerospace engineering to completely solve these difficult problems,but few papers on the survey of this research field have been published recently.Based on the investigation of more than one hundred literatures,considering the application perspectives of computational flight mechanics and recent developments of trajectory optimization,the numerical algorithms of trajectory optimizations for aerospace vehicles are summarized and systematically analyzed.This paper summarized the basic principle,characteristics and application for all kinds of current trajectory optimization algorithms;and introduced some new methods and theories appearing in recent years.Finally,collaborative trajectory optimization for many flight vehicles,and hypersonic vehicle trajectory optimization were mainly reviewed in this paper.In the conclusion of this paper,the future research properties are presented regarding to numerical algorithms of trajectory optimization and control for flight vehicles as follows:collaboration and antagonization for many flight vehicles and multiple targets,global,real-time online,high accuracy of 7-D trajectory,considering all kinds of unknown random disturbances in trajectory optimization,and so on.

VARIABLE SELECTION FOR RECURRENT EVENT DATA WITH INFORMATIVE CENSORING

Recurrent events data with a terminal event （e.g., death） often arise in clinical and ob- servational studies. Variable selection is an important issue in all regression analysis. In this paper, the authors first propose the estimation methods to select the significant variables, and then prove the asymptotic behavior of the proposed estimator. Furthermore, the authors discuss the computing algorithm to assess the proposed estimator via the linear function approximation and generalized cross validation method for determination of the tuning parameters. Finally, the finite sample estimation for the asymptotical covariance matrix is also proposed.

Parallel computing study for the large-scale generalized eigenvalue problems in modal analysis

In this paper we study the algorithms and their parallel implementation for solving large-scale generalized eigenvalue problems in modal analysis.Three predominant subspace algorithms,i.e.,Krylov-Schur method,implicitly restarted Arnoldi method and Jacobi-Davidson method,are modified with some complementary techniques to make them suitable for modal analysis.Detailed descriptions of the three algorithms are given.Based on these algorithms,a parallel solution procedure is established via the PANDA framework and its associated eigensolvers.Using the solution procedure on a machine equipped with up to 4800processors,the parallel performance of the three predominant methods is evaluated via numerical experiments with typical engineering structures,where the maximum testing scale attains twenty million degrees of freedom.The speedup curves for different cases are obtained and compared.The results show that the three methods are good for modal analysis in the scale of ten million degrees of freedom with a favorable parallel scalability.

Adaptive Clustering Algorithm by Ants＇ Optimization

Inspired by the swarm intelligence in self-organizing behavior of real ant colonies, various ant-based algorithms were proposed recently for many research fields in data mining such as clustering. Compared with the previous clustering approaches such as K-means, the main advantage of ant-based clustering algorithms is that no additional information is needed, such as the initial partitioning of the data or the number of clusters. In this paper, we present an adaptive ant clustering algorithm ACAD. The algorithm uses a digraph where the vertexes represent the data to be clustered. The weighted edges represent the acceptance rate between the two data it connected. The pheromone on the edges is adaptively updated by the ants passing it. Some edges with less pheromone are progressively removed under a threshold in the process. Strong connected components of the final digraph are extracted as clusters. Experimental results on several real datasets and benchmarks indicate that ACAD is conceptually simpler, more efficient and more robust than previous research such as the classical K-means clustering algorithm and LF algorithm which.is also based on ACO