Search

In the ensemble feature selection method, if the weight adjustment is performed on each feature subset used, the ensemble effect can be significantly different; therefore, how to find the optimized weight vector is a key and challenging problem. Aiming at this optimization problem, this paper proposes an ensemble feature selection approach based on genetic algorithm (EFS-BGA). After each base feature selector generates a feature subset, the EFS-BGA method obtains the optimized weight of each feature subset through genetic algorithm, which is different from traditional genetic algorithm directly processing single features. We divide the EFS-BGA algorithm into two types. The first is a complete ensemble feature selection method; based on the first, we further propose the selective EFS-BGA model. After that, through mathematical analysis, we theoretically explain why weight adjustment is an optimization problem and how to optimize. Finally, through the comparative experiments on multiple data sets, the advantages of the EFS-BGA algorithm in this paper over the previous ensemble feature selection algorithms are explained in practice. [ABSTRACT FROM AUTHOR]

This paper presents a GPU-accelerated implementation of an image encryption algorithm. The algorithm uses the concepts of a modified XOR cipher to encrypt and decrypt the images, with an encryption pad, generated using the shared secret key and some initialization vectors. It uses a genetically optimized pseudo-random generator that outputs a stream of random bytes of the specified length. The proposed algorithm is subjected to a number of theoretical, experimental, and mathematical analyses, to examine its performance and security against a number of possible attacks, using the following metrics - histogram analysis, correlation analysis, information entropy analysis, NPCR and UACI. The performance analysis carried out shows an average speedup-ratio of 3.489 for encryption, and 4.055 for decryption operation, between the serial and parallel implementations using GPU. The algorithm aims to provide better performance benchmarks, which can significantly improve the experience in the relevant use-cases, like real-time media applications. [ABSTRACT FROM AUTHOR]

This paper proposes an efficiency quantum image steganography protocol based on improved exploiting modification direction algorithm (QIS-IEMD). The new methods of expanding modification range and dynamically sharing between subgroups are introduced in the new protocol. Compared with the quantum image steganography protocol based on EMD algorithm (QIS-EMD), secret information can be embedded on multiple bit planes after expanding pixel's modification range, and the carrier pixel groups can be dynamically shared to achieve higher embedding efficiency, embedding rate and larger capacity. In addition, in order to reflect the feasibility and practicability of QIS-IEMD, dedicated quantum circuits for embedding and extracting secret information are designed for it. Finally, the experimental results and detailed mathematical analysis prove that, compared with QIS-EMD, QIS-IEMD not only performs well in imperceptibility, but also significantly increases embedding efficiency, embedding rate and capacity. [ABSTRACT FROM AUTHOR]

In this paper we study the bounded perturbation resilience of the extragradient and the subgradient extragradient methods for solving a variational inequality (VI) problem in real Hilbert spaces. This is an important property of algorithms which guarantees the convergence of the scheme under summable errors, meaning that an inexact version of the methods can also be considered. Moreover, once an algorithm is proved to be bounded perturbation resilience, superiorization can be used, and this allows flexibility in choosing the bounded perturbations in order to obtain a superior solution, as well explained in the paper. We also discuss some inertial extragradient methods. Under mild and standard assumptions of monotonicity and Lipschitz continuity of the VI's associated mapping, convergence of the perturbed extragradient and subgradient extragradient methods is proved. In addition we show that the perturbed algorithms converge at the rate of $O(1/t)$ . Numerical illustrations are given to demonstrate the performances of the algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose an improved quantum algorithm for the minimum mean square error-based massive multiple-input multiple-output (MIMO) uplink. The new algorithm can reduce the dependency on the assumptions on the input vector, the channel matrix entries and the low rank of the channel matrix, which are indispensable in our previous results. Our improved quantum algorithm applies the quantum block-encoding technology, which depends on the quantum-accessible data structure. Moreover, we design an efficient algorithm for outputting classical data, which makes sure that output data can be utilized in classical devices. Both theoretically mathematical analyses and simulation realizations in massive MIMO systems confirm the applicability of the improved quantum algorithm. With desired precision, and theoretical and numerical analysis, our improved quantum algorithm can achieve a quadratic or even an exponential speedup over classical counterparts. [ABSTRACT FROM AUTHOR]

Virtual machine (VM) placement is a fundamental problem about resource scheduling in cloud computing; however, the design and implementation of an efficient VM placement algorithm are very challenging. To better multiplex and share physical hosts in the cloud data centers, this paper presents a VM placement algorithm based on the peak workload characteristics, which models the workload characteristics of VMs with mathematical method, and measures the similarity of VMs' workload with VM peak similarity. Avoiding virtual machines whose workload has high correlation are placed together, it places the virtual machines with peak workload staggering at different time together, which achieves better VM consolidation through VM peak similarity. This paper focuses on the mathematical analysis of VM peak similarity, and proves that compared to cosine-similarity method and correlation-coefficient method, peak-similarity method is better theoretically. Finally, numerical simulations and algorithm experiments show that our proposed peak-similarity-based placement algorithm outperforms the random placement algorithm and correlation-coefficient-based placement algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a refinement of the Cipolla-Lehmer type algorithm given by H. C. Williams in 1972, and later improved by K. S. Williams and K. Hardy in 1993. For a given r-th power residue c∈Fq where r is an odd prime, the algorithm of H. C. Williams determines a solution of Xr=c in O(r3logq) multiplications in Fq, and the algorithm of K. S. Williams and K. Hardy finds a solution in O(r4+r2logq) multiplications in Fq. Our refinement finds a solution in O(r3+r2logq) multiplications in Fq. Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SageMath shows a substantial speed-up compared with the existing algorithms. It should be mentioned that our method also works for a composite r. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new hierarchy of large cardinals between I3 and I2, the iterability hierarchy, and we prove that every step of it strongly implies the ones below. [ABSTRACT FROM AUTHOR]

This paper is concerned with mathematical and numerical analysis of the system of radiative integral transfer equations. The existence and uniqueness of solution to the integral system is proved by establishing the boundedness of the radiative integral operators and proving the invertibility of the operator matrix associated with the system. A collocation-boundary element method is developed to discretize the differential-integral system. For the non-convex geometries, an element-subdivision algorithm is developed to handle the computation of the integrals containing the visibility factor. An efficient iterative algorithm is proposed to solve the nonlinear discrete system and its convergence is also established. Numerical experiment results are also presented to verify the effectiveness and accuracy of the proposed method and algorithm. [ABSTRACT FROM AUTHOR]

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f:Z+n→R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1-1/e-ϵ)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/e-ϵ)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. [ABSTRACT FROM AUTHOR]

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro. [ABSTRACT FROM AUTHOR]

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Many evolutionary multi-objective optimization (EMO) methodologies have been proposed and performed very well on finding a representative set of Pareto-optimal solutions, but this advantage will be weakened with the increasing number of objectives. And in real applications, what decision makers (DMs) want is a unique solution or a set of solutions rather than the overall Pareto-optimal front. It is a difficult task to solve many-objective problems by using preference information provided by decision maker (DM) during optimization process. In this paper, a new angle-based preference selection mechanism is proposed, which replaces the traditional crowding distance with the aid of preference information provided by the DMs. Particularly, we combine it with a multi-objective immune algorithm with non-dominated neighbor-based selection. The proposed method has been extensively compared with other recently proposed preference-based EMO approaches over DTLZ1, DTLZ2, and DTLZ3 test problems with 4-100 objectives. The results of the experiment indicate that the proposed algorithm can achieve competitive and better results. [ABSTRACT FROM AUTHOR]

In this paper, we prove that for a linearly ordered skewfield the groups of quotients of the semigroup Gn(픻) coincides with the group GLn(픻) for n ≥ 3. [ABSTRACT FROM AUTHOR]

Abstract. This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value m( n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains at least k vertices of each color. In this paper, we obtain upper bounds of m( n) for small k and n, the exact value of m(8), and a lower bound for m(7). [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a new coloring problem of a graph called the dominated coloring. A dominated coloring of a graph $$G$$ is a proper vertex coloring of $$G$$ such that each color class is dominated by at least one vertex of $$G$$ . The minimum number of colors among all dominated colorings is called the dominated chromatic number, denoted by $$\chi _{dom}(G)$$ . In this paper, we establish the close relationship between the dominated chromatic number $$\chi _{dom}(G)$$ and the total domination number $$\gamma _t(G)$$ ; and the equivalence for triangle-free graphs. We study the complexity of the problem by proving its NP-completeness for arbitrary graphs having $$\chi _{dom}(G) \ge 4$$ and by giving a polynomial time algorithm for recognizing graphs having $$\chi _{dom}(G) \le 3$$ . We also give some bounds for planar and star-free graphs and exact values for split graphs. [ABSTRACT FROM AUTHOR]

In this paper, we present an algorithm which can prove algebraic relations involving η -quotients, where η is the Dedekind eta function. [ABSTRACT FROM AUTHOR]

In this paper, we introduce an algorithm for presentation of an inner estimation of the solution set of a complex interval linear system, where the coefficient matrix is a crisp complex-valued matrix and the right-hand-side vector is an interval complex-valued vector. Also, we show that under some certain conditions, the obtained inner estimation is, in fact, an algebraic solution. [ABSTRACT FROM AUTHOR]

In this paper, we proposed an implementation of stochastic perturbation of reduced gradient and bisection (SPRGB) method for optimizing a non-convex differentiable function subject to linear equality constraints and non-negativity bounds on the variables. In particular, at each iteration, we compute a search direction by reduced gradient, and optimal line search by bisection algorithm along this direction yields a decrease in the objective value. SPRGB method is desired to establish the global convergence of the algorithm. An implementation and tests of SPRGB algorithm are given, and some numerical results of large-scale problems are presented, which show the efficient of this approach. [ABSTRACT FROM AUTHOR]

In this paper, two arctangent-based normalized subband adaptive filter (Arc-NSAF) algorithms are proposed, which are derived from two different forms of arctangent cost function and their difference is the order of the arctangent computation and the summation operation of the normalized subband error signal. Benefiting from the excellent property of the arctangent function for suppressing impulsive interferences, the proposed Arc-NSAF algorithms not only possess good robustness against impulsive interferences, but also obtain faster convergence rate for the colored input signals. To further improve the convergence performance of the Arc-NSAFs when identifying sparse system, the proportionate versions of the Arc-NSAF algorithms are also proposed. Simulation results have demonstrated the superiority of the proposed algorithms in impulsive interferences environments as compared to their respective competitors. [ABSTRACT FROM AUTHOR]

The nonmonotone globalization technique is useful in difficult nonlinear problems, because of the fact that it may help escaping from steep sided valleys and may improve both the possibility of finding the global optimum and the rate of convergence. This paper discusses the nonmonotonicity degree of nonmonotone line searches for the unconstrained optimization. Specifically, we analyze some popular nonmonotone line search methods and explore, from a computational point of view, the relations between the efficiency of a nonmonotone line search and its nonmonotonicity degree. We attempt to answer this question how to control the degree of the nonmonotonicity of line search rules in order to reach a more efficient algorithm. Hence in an attempt to control the nonmonotonicity degree, two adaptive nonmonotone rules based on the morphology of the objective function are proposed. The global convergence and the convergence rate of the proposed methods are analysed under mild assumptions. Numerical experiments are made on a set of unconstrained optimization test problems of the CUTEr (Gould et al. in ACM Trans Math Softw 29:373-394, 2003) collection. The performance data are first analysed through the performance profile of Dolan and Moré (Math Program 91:201-213, 2002). In the second kind of analyse, the performance data are analysed in terms of increasing dimension of the test problems. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of simulating multivariate random fields with stationary Gaussian increments in a d-dimensional Euclidean space. To this end, one considers a spectral turning-bands algorithm, in which the simulated field is a mixture of basic random fields made of weighted cosine waves associated with random frequencies and random phases. The weights depend on the spectral density of the direct and cross variogram matrices of the desired random field for the specified frequencies. The algorithm is applied to synthetic examples corresponding to different spatial correlation models. The properties of these models and of the algorithm are discussed, highlighting its computational efficiency, accuracy and versatility. [ABSTRACT FROM AUTHOR]

Scheduling of jobs and resources on a shop floor is an ever green optimization problem. Job shop scheduling problem (JSSP) is an allocation of 'n' jobs on 'm' machines so as to complete processing of all jobs in a minimum possible time. The JSSP has been addressed by various direct, indirect methods, programs, and algorithms in the last 40 year of literature. This paper presents a new paradigm of invasive weed optimization which mimics the process of weed colonization and distribution to solve JSSPs. The algorithm had shown encouraging and promising outputs on standard benchmarking problems. [ABSTRACT FROM AUTHOR]

In this paper, it is shown that there is a gap in the paper [Chidume, C. E., Shahzad, N.: Weak convergence theorems for a finite family of strict pseudo-contractions. Nonlinear Anal., 72, 1257-1265 (2010)], consequently, the main results of the paper do not hold in uniformly smooth Banach spaces. Meanwhile, it is also shown that the main results (Lemma 3.4, Theorems 3.5-3.6, 3.8-3.9) in the paper [Cholamjiak, P., Suantai, S.: Weak convergence theorems for a countable family of strict pseudo-contractions in Banach spaces. Fixed Point Theory Appl., 2010, Article ID 632137, 16 pages (2010)] do not hold in L for p > 3. Finally, some modified results are presented in the setting of uniformly smooth and uniformly convex Banach spaces which include L for p ≥ 2 as special cases. Furthermore, our arguments are also different from the ones given by the authors above. [ABSTRACT FROM AUTHOR]

The paper aims at answering the following question, in the scalar as well in the vector case: What do the famous Aitken's $\Delta ^{2}$ and Wynn's $\varepsilon $-algorithm exactly do with the terms of the input sequence? Inspecting the rules of these algorithms from a geometric point of view leads to change the question into another one: By what kind of geometric object can the parallel (or harmonic) sum be represented? Thus, the paper begins with geometric considerations on the parallel addition and the parallel subtraction of vectors, including equivalent definition, and properties derived from the new point of view. It is shown how the parallel sum of vectors is related to the Bézier parabola controlled by these vectors and to their interpolating equiangular spiral. In the second part, observing that Aitken's $\Delta ^{2}$ and Wynn's $\varepsilon $-algorithm may be defined through hybrid sums, mixing standard and parallel sums, the consequences are drawn regarding the way one can define and analyze these algorithms. New explanatory rules are derived for the $\varepsilon $-algorithm, providing a better understanding of its basic step and of its cross-rule. [ABSTRACT FROM AUTHOR]

An improved particle swarm optimization algorithm based on the model of refracting opposite learning, called refrPSO, is applied to design and optimize FIR low pass and high pass digital filters with linear phase. According to the refraction principle of light, the process of opposition-based learning is ameliorated, and then a new model of opposition-based learning, which is applied for improvement of particle swarm optimization, is proposed. For enhancing the performance of FIR digital filters, in this paper, the optimal combination of the filter coefficients is found out by applying the refrPSO for the design of FIR digital filters. Meanwhile, some well-known algorithms such as classic Parks-McClellan, standard Particle Swarm optimization and Particle Swarm optimization based on opposite learning are used to design FIR digital filters for comparison. Extensive experimental results show that the performance of FIR digital filters optimized by the refrPSO outperforms the one optimized by other algorithms obviously. [ABSTRACT FROM AUTHOR]

In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans-Steuer) algorithm (Math Program 5(1):54-72, 1973). Different from it, the proposed algorithm works in the parameter space and does not aim to find the set of all efficient solutions. Instead, it finds a solution in the sense of Löhne (Vector optimization with infimum and supremum. Springer, Berlin, 2011), that is, it finds a subset of efficient solutions that allows to generate the whole efficient frontier. In that sense, it can also be seen as a generalization of the parametric self-dual simplex algorithm, which originally is designed for solving single objective linear optimization problems, and is modified to solve two objective bounded LVOPs with the positive orthant as the ordering cone in Ruszczyński and Vanderbei (Econometrica 71(4):1287-1297, 2003). The algorithm proposed here works for any dimension, any solid pointed polyhedral ordering cone C and for bounded as well as unbounded problems. Numerical results are provided to compare the proposed algorithm with an objective space based LVOP algorithm [Benson's algorithm in Hamel et al. (J Global Optim 59(4):811-836, 2014)], that also provides a solution in the sense of Löhne (2011), and with the Evans-Steuer algorithm (1973). The results show that for non-degenerate problems the proposed algorithm outperforms Benson's algorithm and is on par with the Evans-Steuer algorithm. For highly degenerate problems Benson's algorithm (Hamel et al. 2014) outperforms the simplex-type algorithms; however, the parametric simplex algorithm is for these problems computationally much more efficient than the Evans-Steuer algorithm. [ABSTRACT FROM AUTHOR]

In this work, we focus on building an efficient succinct dynamic dictionary that significantly improves the query time of the current best known results. The algorithm that we propose suffers from only a $$ O((\log \log n)^2 )$$ multiplicative slowdown in its query time and a $$O(\frac{1}{\epsilon } \log n)$$ slowdown for insertion and deletion operations, where n is the sum of all of the patterns' lengths, the size of the alphabet is $$\textit{polylog}(n)$$ and $$\epsilon \in (0,1)$$ . For general alphabet the query time is $$ O((\log \log n) \log \sigma )$$ , where $$\sigma $$ is the size of the alphabet. A byproduct of this paper is an Aho-Corasick automaton that can be constructed with only a compact working space, which is the first of its type to the best of our knowledge. [ABSTRACT FROM AUTHOR]

Mutation region detection is the first step of searching for a disease gene and has facilitated the identification of several hundred human genes that can harbor mutations leading to a disease phenotype. Recently, the closest shared center problem (CSC) was proposed as a core to solve the mutation region detection problem when the pedigree is not given (Ma et al. in IEEE ACM Trans Comput Biol Bioinform 9(2):372-384, 2012). A ratio-2 approximation algorithm was proposed for the CSC problem in Ma et al. (IEEE ACM Trans Comput Biol Bioinform 9(2):372-384, 2012). In this paper, we will design a polynomial time approximation scheme for this problem. [ABSTRACT FROM AUTHOR]

Given a set $${\mathcal {P}}$$ of h pairwise-disjoint polygonal obstacles with a total of n vertices in the plane, we study the problem of computing the (weak) visibility polygon from a polygonal obstacle $$P^*$$ (an island) in $${\mathcal {P}}$$ . The problem was previously solved in $$O(n^4)$$ time, which has been proved worst-case optimal. However, since h may be much smaller than n, it is desirable to have an algorithm whose running time is also a function of h. In this paper, we present such an algorithm of $$O(n^2h^2)$$ time, and our algorithm improves the previous result when $$h=o(n)$$ . In addition, when all obstacles in $${\mathcal {P}}$$ (including $$P^*$$ ) are convex, our algorithm runs in $$O(n+h^4)$$ time. [ABSTRACT FROM AUTHOR]

The concept of rainbow connection was introduced by Chartrand et al. [] in 2008. It is interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow k-connectivity, k-rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems and questions. [ABSTRACT FROM AUTHOR]

A graph is computable if there is an algorithm which decides whether given vertices are adjacent. Having a procedure for deciding the edge set might not help compute other properties or features of the graph, however. The goal of this paper is to investigate the extent to which features related to the planarity of a graph might or might not be computable. We propose three definitions for what it might mean for a computable graph to be computably planar and for each build a computable planar graph which fails to be computably planar. We also consider these definitions in the context of highly computable graphs, those for which there is an algorithm which computes the degree of a given vertex. [ABSTRACT FROM AUTHOR]

Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information, where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information. [ABSTRACT FROM AUTHOR]

The scheduling in grids is known to be a NP-hard problem. The distributed deployment of nodes, their heterogeneity and their fluctuations in terms of workload and availability make the design of an effective scheduling algorithm a very complex issue. The scientific literature has proposed several heuristics able to tackle this kind of optimization problem using techniques and strategies inspired by nature. The algorithms belonging to ant colony optimization (ACO) paradigm represent an example of these techniques: each one of these algorithms uses strategies inspired by the self-organization ability of real ants for building effective grid schedulers. In this paper, the authors propose an on line, non-clairvoyant, distributed scheduling solution for multi-broker grid based on the alienated ant algorithm (AAA), a new ACO inspired technique exploiting a 'non natural' behavior of ants and an inverse interpretation of pheromone trails. The paper introduces the proposed algorithm, explains the differences with other classical ACO approaches, and compares AAA with two different algorithms. The results of simulations show that the AAA guarantees good performance in terms of makespan, average queue waiting time and load balancing capability. [ABSTRACT FROM AUTHOR]

In this paper, we describe the BIBasis package designed for REDUCE and Macaulay2 computer algebra systems, which allows one to compute Boolean involutive bases and Gröbner bases. The implementations and user interfaces of the package for both systems are described in the respective sections of the paper. Also, we present results of comparisons of BIBasis with other packages and algorithms for constructing Boolean Gröbner bases available in the computer algebra systems. [ABSTRACT FROM AUTHOR]

Matrix-Matrix Multiplication (MMM) is a highly important kernel in linear algebra algorithms and the performance of its implementations depends on the memory utilization and data locality. There are MMM algorithms, such as standard, Strassen-Winograd variant, and many recursive array layouts, such as Z-Morton or U-Morton. However, their data locality is lower than that of the proposed methodology. Moreover, several SOA (state of the art) self-tuning libraries exist, such as ATLAS for MMM algorithm, which tests many MMM implementations. During the installation of ATLAS, on the one hand an extremely complex empirical tuning step is required, and on the other hand a large number of compiler options are used, both of which are not included in the scope of this paper. In this paper, a new methodology using the standard MMM algorithm is presented, achieving improved performance by focusing on data locality (both temporal and spatial). This methodology finds the scheduling which conforms with the optimum memory management. Compared with (Chatterjee et al. in IEEE Trans. Parallel Distrib. Syst. 13:1105, ; Li and Garzaran in Proc. of Lang. Compil. Parallel Comput., ; Bilmes et al. in Proc. of the 11th ACM Int. Conf. Super-comput., ; Aberdeen and Baxter in Concurr. Comput. Pract. Exp. 13:103, ), the proposed methodology has two major advantages. Firstly, the scheduling used for the tile level is different from the element level's one, having better data locality, suited to the sizes of memory hierarchy. Secondly, its exploration time is short, because it searches only for the number of the level of tiling used, and between (1, 2) (Sect. 4) for finding the best tile size for each cache level. A software tool (C-code) implementing the above methodology was developed, having the hardware model and the matrix sizes as input. This methodology has better performance against others at a wide range of architectures. Compared with the best existing related work, which we implemented, better performance up to 55% than the Standard MMM algorithm and up to 35% than Strassen's is observed, both under recursive data array layouts. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm to compute the law of the Lie algebra $\mathfrak{g}_{n}$ associated with the Lie group G, formed of all the n× n upper-unitriangular matrices. The goal of this paper is to show the algorithm that computes the law of $\mathfrak{g}_{n}$ and its implementation using the symbolic computation package MAPLE. In addition, the complexity of the algorithm is described. [ABSTRACT FROM AUTHOR]

In this paper, we study the link between a Chance-Constrained optimization Problem (CCP) and its sample counterpart (SP). SP has a finite number, say N, of sampled constraints. Further, some of these sampled constraints, say k, are discarded, and the final solution is indicated by $x^{\ast}_{N,k}$. Extending previous results on the feasibility of sample convex optimization programs, we establish the feasibility of $x^{\ast}_{N,k}$ for the initial CCP problem. Constraints removal allows one to improve the cost function at the price of a decreased feasibility. The cost improvement can be inspected directly from the optimization result, while the theory here developed permits to keep control on the other side of the coin, the feasibility of the obtained solution. In this way, trading feasibility for performance is put on solid mathematical grounds in this paper. The feasibility result here obtained applies to a vast class of chance-constrained optimization problems, and has the distinctive feature that it holds true irrespective of the algorithm used to discard k constraints in the SP problem. For constraints discarding, one can thus, e.g., resort to one of the many methods introduced in the literature to solve chance-constrained problems with discrete distribution, or even use a greedy algorithm, which is computationally very low-demanding, and the feasibility result remains intact. We further prove that, if constraints in the SP problem are optimally removed-i.e., one deletes those constraints leading to the largest possible cost improvement-, then a precise optimality link to the original chance-constrained problem CCP in addition holds. [ABSTRACT FROM AUTHOR]

Surface multiresolution processing is an important subject in CAGD. It also poses many challenging problems including the design of multiresolution algorithms. Unlike images which are in general sampled on a regular square or hexagonal lattice, the meshes in surfaces processing could have an arbitrary topology, namely, they consist of not only regular vertices but also extraordinary vertices, which requires the multiresolution algorithms have high symmetry. With the idea of lifting scheme, Bertram (Computing 72(1-2):29-39, ) introduces a novel triangle surface multiresolution algorithm which works for both regular and extraordinary vertices. This method is also successfully used to develop multiresolution algorithms for quad surface and $\sqrt 3$ triangle surface processing in Wang et al. (Vis Comput 22(9-11):874-884, ; IEEE Trans Vis Comput Graph 13(5):914-925, ) respectively. When considering the biorthogonality, these papers do not use the conventional $L^2({{\rm I}\kern-.2em{\rm R}}^2)$ inner product, and they do not consider the corresponding lowpass filter, highpass filters, scaling function and wavelets. Hence, some basic properties such as smoothness and approximation power of the scaling functions and wavelets for regular vertices are unclear. On the other hand, the symmetry of subdivision masks (namely, the lowpass filters of filter banks) for surface subdivision is well studied, while the symmetry of the highpass filters for surface processing is rarely considered in the literature. In this paper we introduce the notion of 4-fold symmetry for biorthogonal filter banks. We demonstrate that 4-fold symmetric filter banks result in multiresolution algorithms with the required symmetry for quad surface processing. In addition, we provide 4-fold symmetric biorthogonal FIR filter banks and construct the associated wavelets, with both the dyadic and $\sqrt 2$ refinements. Furthermore, we show that some filter banks constructed in this paper result in very simple multiresolution decomposition and reconstruction algorithms as those in Bertram (Computing 72(1-2):29-39, ) and Wang et al. (Vis Comput 22(9-11):874-884, ; IEEE Trans Vis Comput Graph 13(5):914-925, ). Our method can provide the filter banks corresponding to the multiresolution algorithms in Wang et al. (Vis Comput 22(9-11):874-884, ) for dyadic multiresolution quad surface processing. Therefore, the properties of the scaling functions and wavelets corresponding to those algorithms can be obtained by analyzing the corresponding filter banks. [ABSTRACT FROM AUTHOR]

Term rewrite systems are useful in many areas of computer science. Two especially important areas are decision procedures for the word problem of some algebraic systems and rule-based programming. One of the most studied properties of rewrite systems is confluence, and one of the primary benefits of having a confluent rewrite system is that the system also has uniqueness of normal forms. However, uniqueness of normal forms is an interesting property in its own right and well studied. Also, confluence can be too strong a requirement for some applications. In this paper, we study the decidability of uniqueness of normal forms. Uniqueness of normal forms is decidable for ground rewrite systems, but is undecidable in general. This paper shows that the uniqueness of normal forms problem is decidable for the class of linear shallow term rewrite systems, and gives a decision procedure that is polynomial as long as the arities of the function symbols are bounded or the signature is fixed. [ABSTRACT FROM AUTHOR]

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied. [ABSTRACT FROM AUTHOR]

This paper presents a numerical compression strategy for the boundary integral equation of acoustic scattering in two dimensions. These equations have oscillatory kernels that we represent in a basis of wave atoms, and compress by thresholding the small coefficients to zero. This phenomenon was perhaps first observed in 1993 by Bradie, Coifman, and Grossman, in the context of local Fourier bases (Bradie et al. in Appl. Comput. Harmon. Anal. 1:94–99, ). Their results have since then been extended in various ways. The purpose of this paper is to bridge a theoretical gap and prove that a well-chosen fixed expansion, the non-standard wave atom form, provides a compression of the acoustic single- and double-layer potentials with wave number k as O( k)-by- O( k) matrices with C ε δ k1+ δ non-negligible entries, with δ>0 arbitrarily small, and ε the desired accuracy. The argument assumes smooth, separated, and not necessarily convex scatterers in two dimensions. The essential features of wave atoms that allow this result to be written as a theorem are a sharp time-frequency localization that wavelet packets do not obey, and a parabolic scaling (wavelength of the wave packet) ∼ (essential diameter)2. Numerical experiments support the estimate and show that this wave atom representation may be of interest for applications where the same scattering problem needs to be solved for many boundary conditions, for example, the computation of radar cross sections. [ABSTRACT FROM AUTHOR]

Abstract  In this paper, we study the problems of enumerating cuts of a graph by non-decreasing weights. There are four problems, depending on whether the graph is directed or undirected, and on whether we consider all cuts of the graph or only s-t cuts for a given pair of vertices s,t. Efficient algorithms for these problems with delay between two successive outputs have been known since 1992, due to Vazirani and Yannakakis. In this paper, improved algorithms are presented. The delays of the presented algorithms are O(nmlog (n 2/m)). Vazirani and Yannakakis’s algorithms have been used as basic subroutines in the solutions of many problems. Therefore, our improvement immediately reduces the running time of these solutions. For example, for the minimum k-cut problem, the upper bound is immediately reduced by a factor of for k=3,4,5,6. [ABSTRACT FROM AUTHOR]

Consider a combinatorial identity that can be proved by induction. In this paper, we describe a general method for translating the inductive proof into a recursive bijection. Furthermore, we will demonstrate that the resulting recursive bijection can often be defined in a direct, non-recursive way. Thus, the translation method often results in a bijective proof of the identity that helps illuminate the underlying combinatorial structures. This paper has two main parts: First, we describe the translation method and the accompanying Maple code; and second, we give a few examples of how the method has been used to discover new bijections. [ABSTRACT FROM AUTHOR]

Abstract  The study and research of evolutionary algorithms (EAs) is getting great attention in recent years. Although EAs have earned extensive acceptance through numerous successful applications in many fields, the problem of finding the best combination of evolutionary parameters especially for population size that need the manual settings by the user is still unresolved. In this paper, our system is focusing on differential evolution (DE) and its control parameters. To overcome the problem, two new systems were carried out for the self-adaptive population size to test two different methodologies (absolute encoding and relative encoding) in DE and compared their performances against the original DE. Fifty runs are conducted for every 20 well-known benchmark problems to test on every proposed algorithm in this paper to achieve the function optimization without explicit parameter tuning in DE. The empirical testing results showed that DE with self-adaptive population size using relative encoding performed well in terms of the average performance as well as stability compared to absolute encoding version as well as the original DE. [ABSTRACT FROM AUTHOR]

Abstract  This paper introduces a novel version of the particle swarm optimisation (PSO) algorithm which we call self-organising swarm SOSwarm. SOSwarm can be used for unsupervised learning. In the algorithm, input vectors are projected into a lower-dimensional map space producing a visual representation of the input data in a manner similar to a self-organising map (SOM). In SOSwarm, particles react to input data during the learning process by modifying their velocities using an adaptation of the PSO velocity update function. SOSwarm is successfully applied to ten benchmark problems drawn from the UCI Machine Learning repository. The paper also demonstrates how the canonical SOM can be explored within the PSO paradigm. Illustrating this linkage between the heretofore distinct literatures of SOM and PSO opens up several new avenues of research for the development of novel self-organising algorithms. [ABSTRACT FROM AUTHOR]

In this paper, exact algorithms for solving the simple assembly line balancing type I problem are presented. The proposed algorithms consist of a constructive and two destructive algorithms. Several well-known lower-bound computational methods are also applied in these algorithms. Computational experiments were carried out to test the performance of the proposed algorithms based on a set of benchmark problem instances. The computational results show that the algorithms proposed in this paper are efficient in solving the simple assembly line balancing benchmark problem instances. Moreover, a problem instance whose optimal solution had previously been unknown is solved by one of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Let F be a function on pairs of vertices. An F-labeling scheme is composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute F( u, v) for any two vertices u and v directly from their labels. As applications for labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. This paper investigates labeling schemes for dynamic trees. We consider two dynamic tree models, namely, the leaf-dynamic tree model in which at each step a leaf can be added to or removed from the tree and the leaf-increasing tree model in which the only topological event that may occur is that a leaf joins the tree. A general method for constructing labeling schemes for dynamic trees (under the above mentioned dynamic tree models) was previously developed in Korman et al. (Theory Comput Syst 37:49–75, 2004). This method is based on extending an existing static tree labeling scheme to the dynamic setting. This approach fits many natural functions on trees, such as distance, separation level, ancestry relation, routing (in both the adversary and the designer port models), nearest common ancestor etc.. Their resulting dynamic schemes incur overheads (over the static scheme) on the label size and on the communication complexity. In particular, all their schemes yield a multiplicative overhead factor of Ω(log n) on the label sizes of the static schemes. Following (Korman et al., Theory Comput Syst 37:49–75, 2004), we develop a different general method for extending static labeling schemes to the dynamic tree settings. Our method fits the same class of tree functions. In contrast to the above paper, our trade-off is designed to minimize the label size, sometimes at the expense of communication. Informally, for any function k( n) and any static F-labeling scheme on trees, we present an F-labeling scheme on dynamic trees incurring multiplicative overhead factors (over the static scheme) of $$O(\log_{k(n)} n)$$ on the label size and $$O(k(n)\log_{k(n)} n)$$ on the amortized message complexity. In particular, by setting $$k(n) = n^{\epsilon}$$ for any $$0 < \epsilon < 1$$ , we obtain dynamic labeling schemes with asymptotically optimal label sizes and sublinear amortized message complexity for the ancestry relation, the id-based and label-based nearest common ancestor relation and the routing function. [ABSTRACT FROM AUTHOR]

This paper focuses on a class of discrete-time interconnected pendulumlike systems. Sufficient conditions for the global convergence of systems with both structured and unstructured uncertainties in its linear part are established in terms of linear matrix inequalities (LMIs). In the traditional decentralized control of large scale systems, the effects of interconnections were seldom studied. In this paper, a square matrix specifying the interconnecting structure is introduced in order to discuss the effects of nonlinear interconnections. It is shown that the global convergence of the whole interconnected system can be achieved by designing an appropriate interconnection matrix. In order to solve the nonlinear matrix inequalities (NMIs) arising in the synthesis problem, a global optimization algorithm is presented which can be used to handle a class of NMI problems. An illustrative example is given to demonstrate the applicability and validity of the main results and the presented algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes several globally convergent geometric optimization algorithms on Riemannian manifolds, which extend some existing geometric optimization techniques. Since any set of smooth constraints in the Euclidean space Rn (corresponding to constrained optimization) and the Rn space itself (corresponding to unconstrained optimization) are both special Riemannian manifolds, and since these algorithms are developed on general Riemannian manifolds, the techniques discussed in this paper provide a uniform framework for constrained and unconstrained optimization problems. Unlike some earlier works, the new algorithms have less restrictions in both convergence results and in practice. For example, global minimization in the one-dimensional search is not required. All the algorithms addressed in this paper are globally convergent. For some special Riemannian manifold other than Rn, the newalgorithms are very efficient. Convergence rates are obtained. Applications are discussed. [ABSTRACT FROM AUTHOR]