The method of ensembles of decision trees for the analysis of the electrical activity produced by the human brain

In this paper, we develop a method for localization of the active domains of the brain by electroencephalography signals on the basis of ensembles of random decision trees. We suggest a method for reducing the problem of localization to the problem of classification of the quality of the dipole sources. We present a localization algorithm, which consists in constructing an ensemble of decision trees for the parameters of the dipole sources (which are responsible for the approximation of the potential detected at various time instants) and finding the most probable source regions on the basis of a special voting procedure. It is demonstrated that the approach that employs the decision trees technique allows a stable determination of the parameters of the transient function between the source and the signal detected, which is essential for the construction of the brain-computer interface. The method suggested is demonstrated to converge both on the exact solutions and on signals of real experiments by the analysis of evoked potentials. Original Russian Text E.A. Popova, 2008, published in Vestnik Moskovskogo Universiteta. Vychislitel’naya Matematika i Kibernetika, 2008, No. 3, pp. 46–55.     

A Genetic/Tabu Thresholding Hybrid Algorithm for the Process Allocation Problem

In this paper we describe an hybrid heuristic approach, which combines Genetic Algorithms and Tabu Thresholding, for the static allocation of interacting processes onto a parallel target system, where the number of processes is greater than the number of available processors. This problem is known to be NP-hard and finds many practical applications, given the increasing diffusion of distributed and parallel computing systems.The algorithm faces infeasibilities due to processors overload by incorporating them into the objective function and by adapting the mutation operator. Global search is performed on the set of local optima obtained by a repair search operator based on a Tabu Thresholding procedure.Extensive computational testing on randomly generated instances with up to 100 processes characterized by different target network topologies with 4 to 25 processors, shows that the algorithm favorably compares with other approaches from the literature.The proposed approach has also been extended to the allocation of parallel objects and classes, where an additional co-residence constraint between each parallel object and the associated class arises.     

Parker-Sochacki method for solving systems of ordinary differential equations using graphics processors

The Parker-Sochacki method, which is used for solving systems of ordinary differential equations, and implementation of this method on graphics processors are described. The solution to the classical N-body problem is considered as a test. The algorithm makes it possible to effectively use massive parallel graphics processors and provides acceptable accuracy with multiple time reduction, as compared to processors of a conventional architecture.     

An efficient modified boosting method for solving classification problems

Based on the Adaboost algorithm, a modified boosting method is proposed in this paper for solving classification problems. This method predicts the class label of an example as the weighted majority voting of an ensemble of classifiers. Each classifier is obtained by applying a given weak learner to a subsample (with size smaller than that of the original training set) which is drawn from the original training set according to the probability distribution maintained over the training set. A parameter is introduced into the reweighted scheme proposed in Adaboost to update the probabilities assigned to training examples so that the algorithm can be more accurate than Adaboost. The experimental results on synthetic and several real-world data sets available from the UCI repository show that the proposed method improves the prediction accuracy, the execution speed as well as the robustness to classification noise of Adaboost. Furthermore, the diversity–accuracy patterns of the ensemble classifiers are investigated by kappa–error diagrams.     

A parallel implementation of Wang’s method for solving tridiagonal systems

In this paper, a parallel implementation of Wang’s method for solving tridiagonal system of equations on the multiprocessor machine using occam language is presented. The parallel algorithm has been designed for shared and distributed memory machine that support data parallel and message passing. The over all performance of this implementation on 9 each of processors is given. The communication times are very important and any improvement on this communication would have a significant performance of the implementation. The significance of these results are discussed.     

Parallel algorithm for training multiclass proximal Support Vector Machines

In this paper we describe a proximal Support Vector Machine algorithm for multiclassification problem by one-vs-all scheme. The computational requirement for the new algorithm is almost the same as training one of its element binary proximal Support Vector Machines. Low rank approximation is taken to reduce computational costs when the kernel matrix is too large. An error bound estimation for the approximated solution is given, which is used as a stopping criteria for low rank approximation. A post-processing strategy is developed to overcome the difficulty arising from unbalanced data and to improve the classification accuracy. A parallel implementation of the algorithm using standard MPI communication routines is provided to handle large-scale problems and to accelerate the training process. Experiment results on several public datasets validate the effectiveness of our proposed algorithm.     

Concurrent stochastic methods for global optimization

The global optimization problem, finding the lowest minimizer of a nonlinear function of several variables that has multiple local minimizers, appears well suited to concurrent computation. This paper presents a new parallel algorithm for the global optimization problem. The algorithm is a stochastic method related to the multi-level single-linkage methods of Rinnooy Kan and Timmer for sequential computers. Concurrency is achieved by partitioning the work of each of the three main parts of the algorithm, sampling, local minimization start point selection, and multiple local minimizations, among the processors. This parallelism is of a coarse grain type and is especially well suited to a local memory multiprocessing environment. The paper presents test results of a distributed implementation of this algorithm on a local area network of computer workstations. It also summarizes the theoretical properties of the algorithm.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NSF cooperative agreement DCR-8420944.     

On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem

As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors.     

Recommendations on performance of parallel DSMC algorithm in solving subsonic nanoflows

We investigate the efficiency of a parallel direct simulation Monte Carlo (PDSMC) algorithm in solving the rarefied subsonic flow through a nanochannel. We use MPI library to transfer data between the processors. It is observed that PDSMC solver shows ideal speed up if sufficient workload is provided for each of processors. Additionally, this study shows that the computational time and speed up of the extended PDSMC solver do not depend (or slightly depend) on the number of cells. In contrary, increasing the total number of particles would result in a better efficiency of the PDSMC.     

A Gridding Method for Bayesian Sequential Decision Problems

This article introduces a numerical method for finding optimal or approximately optimal decision rules and corresponding expected losses in Bayesian sequential decision problems. The method, based on the classical backward induction method, constructs a grid approximation to the expected loss at each decision time, viewed as a function of certain statistics of the posterior distribution of the parameter of interest. In contrast with most existing techniques, this method has a computation time which is linear in the number of stages in the sequential problem. It can also be applied to problems with insufficient statistics for the parameters of interest. Furthermore, it is well-suited to be implemented using parallel processors.     

Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays

This paper addresses a certain type of scheduling problem that arises when a parallel computation is to be executed on a set of identical parallel processors. It is assumed that if two precedence-related tasks are processed on two different processors, due to the information transferring, there will be a task-dependent communication delay between them. For each task, a processing time, a due date and a weight is given while the goal is to minimize the total weighted late work. An integer linear mathematical programming model and a branch-and-bound algorithm have been developed for the proposed problem. Comparing the results obtained by the proposed branch-and-bound algorithm with those obtained by CPLEX, indicates the effectiveness of the method.     

Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.     

A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programs

Multistage stochastic linear programs can represent a variety of practical decision problems. Solving a multistage stochastic program can be viewed as solving a large tree of linear programs. A common approach for solving these problems is the nested decomposition algorithm, which moves up down the tree by solving nodes and passing information among nodes. The natural independence of subtrees suggests that much of the computational effort of the nested decomposition algorithm can run in parallel across small numbers of fast processors. This paper explores the advantages of such parallel implementations over serial implementations and compares alternative sequencing protocols for parallel processors. Computational experience on a large test set of practical problems with up to 1.5 million constraints and almost 5 million variables suggests that parallel implementations may indeed work well, but they require careful attention to processor load balancing. Supported in part by the National Science Foundation under Grants DDM-9215921 and SES-9211937.     

Parallel algorithms for solving linear systems with block-tridiagonal matrices on multi-core CPU with GPU

For solving systems of linear algebraic equations with block-tridiagonal matrices arising in geoelectrics problems, the parallel matrix sweep algorithm, conjugate gradient method with preconditioner, and square root method are proposed and implemented numerically on multi-core CPU Intel with graphics processors NVIDIA. Investigation of efficiency and optimization of parallel algorithms for solving the problem with quasi-model data are performed.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

分布式系统上并行矩阵乘法

1．引言矩阵乘法是最简单的数学问题,同时由于其计算量大而通常被用来对计算机的浮点运算速度进行测试,尤其是对于并行计算机,其并行效率的好坏可通过这个简单的问题反应出来,如果在这个问题上都不能取得很好的效果,对于其它问题就更不可能．此外,为了提高计算性能,对求解数值代数中的问题最终会归结到有矩阵乘法的计算,如LAPACK,ScaLAPACK等,因此有效地并行计算矩阵乘法在实际应用中是非常重要的．矩阵乘法是做C＝A×B,其中A是m×k阵,B是k×n阵,C是m×n阵．设矩阵A,B可以分成p×p块矩阵,即A＝（Ai,j）p×p,B＝（B…     

Corrected explicit-implicit domain decomposition algorithms for two-dimensional semilinear parabolic equations

Corrected explicit-implicit domain decomposition (CEIDD) algorithms are studied for parallel approximation of semilinear parabolic problems on distributed memory processors. It is natural to divide the spatial domain into some smaller parallel strips and cells using the simplest straight-line interface (SI). By using the Leray-Schauder fixed-point theorem and the discrete energy method, it is shown that the resulting CEIDD-SI algorithm is uniquely solvable, unconditionally stable and convergent. The CEIDD-SI method always suffers from the globalization of data communication when interior boundaries cross into each other inside the domain. To overcome this disadvantage, a composite interface (CI) that consists of straight segments and zigzag fractions is suggested. The corresponding CEIDD-CI algorithm is proven to be solvable, stable and convergent. Numerical experiments are presented to support the theoretical results.     

Performance analysis of distributed solution approaches in simulation-based optimization

Applying computationally expensive simulations in design or process optimization results in long-running solution processes even when using a state-of-the-art distributed algorithm and hardware. Within these simulation-based optimization problems the optimizer has to treat the simulation systems as black-boxes. The distributed solution of this kind of optimization problem demands efficient utilization of resources (i.e. processors) and evaluation of the solution quality. Analyzing the parallel performance is therefore an important task in the development of adequate distributed approaches taking into account the numerical algorithm, its implementation, and the used hardware architecture. In this paper, simulation-based optimization problems are characterized and a distributed solution algorithm is presented. Different performance analysis techniques (e.g. scalability analysis, computational complexity) are discussed and a new approach integrating parallel performance and solution quality is developed. This approach combines a priori and a posteriori techniques and can be applied in early stages of the solution process. The feasibility of the approach is demonstrated by applying it to three different classes of simulation-based optimization problems from groundwater management.     

Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

Pipeline implementation of cellular automata for structural design on message-passing multiprocessors

The inherent structure of cellular automata is trivially parallelizable and can directly benefit from massively parallel machines in computationally intensive problems. This paper presents both block synchronous and block pipeline (with asynchronous message passing) parallel implementations of cellular automata on distributed memory (message-passing) architectures. A structural design problem is considered to study the performance of the various cellular automata implementations. The synchronous parallel implementation is a mixture of Jacobi and Gauss–Seidel style iteration, where it becomes more Jacobi like as the number of processors increases. Therefore, it exhibits divergence because of the mathematical characteristics of Jacobi iteration matrix for the structural problem as the number of processors increases. The proposed pipeline implementation preserves convergence by simulating a pure Gauss–Seidel style row-wise iteration. Numerical results for analysis and design of a cantilever plate made of composite material show that the pipeline update scheme is convergent and successfully generates optimal designs.