Optimizations in computing the Duquenne–Guigues basis of implications

In this paper, we consider algorithms involved in the computation of the Duquenne–Guigues basis of implications. The most widely used algorithm for constructing the basis is Ganter’s Next Closure, designed for generating closed sets of an arbitrary closure system. We show that, for the purpose of generating the basis, the algorithm can be optimized. We compare the performance of the original algorithm and its optimized version in a series of experiments using artificially generated and real-life datasets. An important computationally expensive subroutine of the algorithm generates the closure of an attribute set with respect to a set of implications. We compare the performance of three algorithms for this task on their own, as well as in conjunction with each of the two algorithms for generating the basis. We also discuss other approaches to constructing the Duquenne–Guigues basis.     

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

Razborov (1996) recently proved that polynomial calculus proofs of the pigeonhole principle must have degree at least ⌈n/2⌉ + 1 over any field. We present a simplified proof of the same result.?Furthermore, we show a matching upper bound on polynomial calculus proofs of the pigeonhole principle for any field of suficiently large characteristic, and an ⌈n/2⌉ + 1 lower bound for any subset sum problem over the field of reals.?We show that these degree lower bounds also translate into lower bounds on the number of monomials in any polynomial calculus proof, and hence on the running time of most implementations of the Gr?bner basis algorithm. Received: October 14, 1997.     

Modification of a two-dimensional fast Fourier transform algorithm with an analog of the Cooley–Tukey algorithm for image processing

Two-dimensional fast Fourier transform (FFT) for image processing and filtering is widely used in modern digital image processing systems. This paper concerns the possibility of using a modification of two-dimensional FFT with an analog of the Cooley–Tukey algorithm, which requires a smaller number of complex addition and multiplication operations than the standard method of calculation by rows and columns.     

CO2RBFN: an evolutionary cooperative–competitive RBFN design algorithm for classification problems

This paper presents a new evolutionary cooperative–competitive algorithm for the design of Radial Basis Function Networks (RBFNs) for classification problems. The algorithm, CO²RBFN, promotes a cooperative–competitive environment where each individual represents a radial basis function (RBF) and the entire population is responsible for the final solution. The proposal considers, in order to measure the credit assignment of an individual, three factors: contribution to the output of the complete RBFN, local error and overlapping. In addition, to decide the operators’ application probability over an RBF, the algorithm uses a Fuzzy Rule Based System. It must be highlighted that the evolutionary algorithm considers a distance measure which deals, without loss of information, with differences between nominal features which are very usual in classification problems. The precision and complexity of the network obtained by the algorithm are compared with those obtained by different soft computing methods through statistical tests. This study shows that CO²RBFN obtains RBFNs with an appropriate balance between accuracy and simplicity, outperforming the other methods considered.     

Probabilistic odd–even: an adaptive wormhole routing algorithm for 2D mesh network-on-chip

Wormhole routing is a popular routing technique used in network-on-chip. It is efficient but susceptible to deadlock, while deadlock will significantly degrade the network performance of NoC. Most existing adaptive wormhole routings avoid deadlock by reducing the degree of adaptiveness and thus sacrificing network performance. In this paper, we address both deadlock and network performance issues jointly, and propose a probabilistic odd–even (POE) routing algorithm that achieves the minimum packet delivery delay. The proposed POE dynamically adjusts the probabilities of constrained turns that may lead to deadlocks according to the current network conditions, and uses an efficient deadlock detection and recovery scheme when a deadlock happens. By adopting constrained turns adaptively to the network status, it not only reduces the frequency of deadlock and allows the network to be swiftly recovered when it occurs, but also greatly improves the degree of adaptiveness to obtain high network performance. Experimental results show that our method achieves a significant performance improvement both in terms of network throughput and average packet latency compared with the existing methods such as XY, odd–even, abacus turn model and fully adaptive routing algorithm while it only has moderate energy consumption.     

A bound for the Rosenfeld–Gröbner algorithm

We consider the Rosenfeld–Gröbner algorithm for computing a regular decomposition of a radical differential ideal generated by a set of ordinary differential polynomials in n$n$ indeterminates. For a set of ordinary differential polynomials F$F$, let M(F)$M\left(F\right)$ be the sum of maximal orders of differential indeterminates occurring in F$F$. We propose a modification of the Rosenfeld–Gröbner algorithm, in which for every intermediate polynomial system F$F$, the bound M(F)?(n−1)!M(_F0)$M\left(F\right)?(n-1)!M\left(F_0\right)$ holds, where _F0$F_0$ is the initial set of generators of the radical ideal. In particular, the resulting regular systems satisfy the bound. Since regular ideals can be decomposed into characterizable components algebraically, the bound also holds for the orders of derivatives occurring in a characteristic decomposition of a radical differential ideal.     

A hybrid genetic algorithm for the discrete time–cost trade-off problem

In this paper we present a hybrid strategy developed using genetic algorithms (GAs), simulated annealing (SA), and quantum simulated annealing techniques (QSA) for the discrete time–cost trade-off problem (DTCTP). In the hybrid algorithm (HA), SA is used to improve hill-climbing ability of GA. In addition to SA, the hybrid strategy includes QSA to achieve enhanced local search capability. The HA and a sole GA have been coded in Visual C++ on a personal computer. Ten benchmark test problems with a range of 18 to 630 activities are used to evaluate performance of the HA. The benchmark problems are solved to optimality using mixed integer programming technique. The results of the performance analysis indicate that the hybrid strategy improves convergence of GA significantly and HA provides a powerful alternative for the DTCTP.     

Numerical strategies for the system of first-order IVPS using the RK–Butcher algorithm

In this article, a new method of analysis for first-order initial-value type ordinary differential equations using the Runge–Kutta (RK)–Butcher algorithm is presented. To illustrate the effectiveness of the RK–Butcher algorithm, 10 problems have been considered and compared with the RK method based on arithmetic mean, and with exact solutions of the problems, and are found to be very accurate. Stability analysis for the first-order initial-value problem (IVP) has been discussed. Error graphs for the first-order IVPs are presented in a graphical form to show the efficiency of this RK–Butcher method. This RK–Butcher algorithm can be easily implemented in a digital computer and the solution can be obtained for any length of time.     

FraRI: an algorithm to account for the discontinuity at 60° N in MODIS temperature products

The Moderate Resolution Imaging Spectroradiometer (MODIS) on NASA's Terra and Aqua satellites conducts continuous monitoring of the Earth's land surface and oceans. Recently, a sharp discontinuity (averaging 1.9°C) has been noticed at 60° N in both MODIS daytime and night-time land surface temperature (LST) products. This linear artefact arises because the CO₂ high cloud test in the operational code for the generation of the MODIS cloud mask product is used only in the non-polar region (between 60° N and 60° S). The resulting discontinuity clearly has negative implications for any statistical applications of these temperature data. In this technical note we present a new algorithm, which minimizes this discontinuity. The method uses edge detection and elimination based on a mixture of Sobel and non-linear Laplacian filters (edge detection and quantification), cubic splines (edge modelling), and a controllable power function for image restoration. The implementation of this algorithm is demonstrated on an image of average minimum night-time LST between 2001 and 2008.     

Computing solutions of the paintshop–necklace problem

How to assign colors to the occurrences of cars in a car factory? How to divide fairly a necklace between thieves who have stolen it? These two questions are addressed in two combinatorial problems that have attracted attention from a theoretical point of view these last years, the first one more by people from the combinatorial optimization community, the second more from the topological combinatorics and computer science point of view.     

A fast algorithm for solving the space–time fractional diffusion equation

In this paper, we propose a fast algorithm for efficient and accurate solution of the space–time fractional diffusion equations defined in a rectangular domain. The spatial discretization is done by using the central finite difference scheme and matrix transfer technique. Due to its nonlocality, numerical discretization of the spectral fractional Laplacian ${(?\Delta )}_s^{\alpha /2}$ results in a large dense matrix. This causes considerable challenges not only for storing the matrix but also for computing matrix–vector products in practice. By utilizing the compact structure of the discrete system and the discrete sine transform, our algorithm avoids to store the large matrix from discretizing the nonlocal operator and also significantly reduces the computational costs. We then use the Laplace transform method for time integration of the semi-discretized system and a weighted trapezoidal method to numerically compute the convolutions needed in the resulting scheme. Various experiments are presented to demonstrate the efficiency and accuracy of our method.     

Blocking and parallelization of the Hari–Zimmermann variant of the Falk–Langemeyer algorithm for the generalized SVD

The paper describes how to modify the two-sided Hari–Zimmermann algorithm for computation of the generalized eigenvalues of a matrix pair (A, B), where B is positive definite, to an implicit algorithm that computes the generalized singular values of a pair (F, G). In addition, we present blocking and parallelization techniques for speedup of the computation.For triangular matrix pairs of a moderate size, numerical tests show that the double precision sequential pointwise algorithm is several times faster than the Lapack DTGSJA algorithm, while the accuracy is slightly better, especially for small generalized singular values.Cache-aware algorithms, implemented either as the block-oriented, or as the full block algorithm, are several times faster than the pointwise algorithm. The algorithm is almost perfectly parallelizable, so parallel shared memory versions of the algorithm are perfectly scalable, and their speedup almost solely depends on the number of cores used. A hybrid shared/distributed memory algorithm is intended for huge matrices that do not fit into the shared memory.     

KSpheres – an efficient algorithm for joining skinning surfaces

Besides classical point based surface design, sphere based creation of characters and other surfaces has been introduced by some of the recently developed modeling tools in computer graphics. ZSpheres^® by Pixologic, or Spore™ by Electronic Arts are just two prominent examples of these softwares. In this paper we introduce a new sphere based modeling tool, which allows us to create smooth, tubular-like surfaces by skinning a user-defined set of spheres. The main advantage of the new method is to provide a parametric surface with more natural and smoother shape, especially at the connection of branches than the surfaces provided by the existing softwares and methods.     

Radial basis function meshless method for the steady incompressible Navier–Stokes equations

A meshless collocation method based on radial basis functions is proposed for solving the steady incompressible Navier–Stokes equations. This method has the capability of solving the governing equations using scattered nodes in the domain. We use the streamfunction formulation, and a trust-region method for solving the nonlinear problem. The no-slip boundary conditions are satisfied using a ghost node strategy. The efficiency of this method is demonstrated by solving three model problems: the driven cavity flows in square and rectangular domains and flow over a backward-facing step. The results obtained are in good agreement with benchmark solutions.     

Genetic algorithm–based training for semi-supervised SVM

The Support Vector Machine (SVM) is an interesting classifier with excellent power of generalization. In this paper, we consider applying the SVM to semi-supervised learning. We propose using an additional criterion with the standard formulation of the semi-supervised SVM (S ³ VM) to reinforce classifier regularization. Since, we deal with nonconvex and combinatorial problem, we use a genetic algorithm to optimize the objective function. Furthermore, we design the specific genetic operators and certain heuristics in order to improve the optimization task. We tested our algorithm on both artificial and real data and found that it gives promising results in comparison with classical optimization techniques proposed in literature.