Counting with rational generating functions

We examine two different ways of encoding a counting function: as a rational generating function and explicitly as a function (defined piecewise using the greatest integer function). We prove that, if the degree and number of input variables of the (quasi-polynomial) function are fixed, there is a polynomial time algorithm which converts between the two representations. Examples of such counting functions include Ehrhart quasi-polynomials, vector partition functions, integer points in parametric polytopes, and projections of the integer points in parametric polytopes. For this last example, this algorithm provides the first known way to compute the explicit function in polynomial time. We rely heavily on results by Barvinok and Pommersheim [Barvinok, A., Pommersheim, J., 1999. An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–97). In: Math. Sci. Res. Inst. Publ., vol. 38. Cambridge Univ. Press, Cambridge, pp. 91–147], and also by Verdoolaege et al. [Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V., Bruynooghe, M., 2007. Counting integer points in parametric polytopes using Barvinok’s rational functions, Algorithmica 48 (1), 37–66].     

Fast interference detection between geometric models

We present efficient algorithms for interference detection between geometric models described by linear or curved boundaries and undergoing rigid motion. The set of models include surfaces described by rational spline patches or piecewise algebraic functions. In contrast to previous approaches, we first describe an efficient algorithm for interference detection between convex polytopes using coherence and local features. Then an extension using hierarchical representation to concave polytopes is presented. We apply these algorithms along with properties of input models, local and global algebraic methods for solving polynomial equations, and the geometric formulation of the problem to devise efficient algorithms for convex and nonconvex curved objects. Finally, a scheduling scheme to reduce the frequency of interference detection in large environments is described. These algorithms have been successfully implemented and we discuss their performance in various environments.     

On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation

We study the problem of generating the monomials of a black box polynomial in the context of enumeration complexity. We present three new randomized algorithms for restricted classes of polynomials with a polynomial or incremental delay, and the same global running time as the classical ones. We introduce TotalBPP, IncBPP and DelayBPP, which are probabilistic counterparts of the most common classes for enumeration problems. Our interpolation algorithms are applied to algebraic representations of several combinatorial enumeration problems, which are so proved to belong to the introduced complexity classes. In particular, the spanning hypertrees of a 3-uniform hypergraph can be enumerated with a polynomial delay. Finally, we study polynomials given by circuits and prove that we can derandomize the interpolation algorithms on classes of bounded-depth circuits. We also prove the hardness of some problems on polynomials of low degree and small circuit complexity, which suggests that our good interpolation algorithm for multilinear polynomials cannot be generalized to degree 2 polynomials. This article is an improved and extended version of Strozecki (Mathematical Foundations of Computer Science, pp. 629–640, 2010) and of the third chapter of the author’s Ph.D. Thesis (Strozecki, Ph.D. Thesis, 2010).     

Classification algorithm based on pairwise comparison of features

We propose an alternative approach to classification that differs from known approaches in that instead of comparing the tuple of values of a test object’s features with similar tuples of features for objects in the training set, in this approach we make independent pairwise comparisons of every pair of feature values for the objects being compared. Here instead of using the notion of a “nearest neighbors” for test object, we introduce the notion of “admissible proximity” for each feature value in the test object. In this approach, we propose an alternative algorithm for classification that has a number of significant practical features. The algorithm’s quality was evaluated on sample problems taken from the well-known UCI repository and related to various aspects of human activity. The results show that the algorithm is competitive compared to known classification algorithms.     

The maximal likelihood enumeration method for the problem of classifying piecewise regular objects

We study the recognition problem for composite objects based on a probabilistic model of a piecewise regular object with thousands of alternative classes. Using the model’s asymptotic properties, we develop a new maximal likelihood enumeration method which is optimal (in the sense of choosing the most likely reference for testing on every step) in the class of “greedy” algorithms of approximate nearest neighbor search. We show experimental results for the face recognition problem on the FERET dataset. We demonstrate that the proposed approach lets us reduce decision making time by several times not only compared to exhaustive search but also compared to known approximate nearest neighbors techniques.     

Six etudes in generating functions

Schutzenberger's philosophy of getting algebraic generating functions out of context-free languages is practiced to obtain short proofs of results of Kreweras, Kreweras-Poupard and Kreweras-Moszkowski, concerning the refined enumeration of legal bracketings according to various parameters. We also mention some ramifications to the enumeration of ordered trees. As an “encore”, we give a short proof of a formula, conjectured by Kirkman and first proved by Cayley, that counts the number of ways of placing m non-intersecting diagonals in a convex polygon of k sides.

1980 Mathematics Subject Classification: 68R05, 68Q45, 05A15.     

一种适用于高维格基约化的综合算法

格基约化算法是求解格上最短向量问题(SVP)的一类算法,在格理论中有重要地位,尤其在格理论构造的公钥密码中发挥重要作用.目前公认效率最高的主流算法是Blockwise-Korkine-Zolotarev(BKZ)及其改进形式BKZ 2.0,主要思想是分块约化,调用多项式次的局部格上SVP算法.但是BKZ类算法仍然存在约...     

Automated network management and configuration using Probabilistic Trans-Algorithmic Search

Online configuration of large-scale systems such as networks requires parameter optimization within a limited amount of time, especially when configuration is needed as a response to recover from a failure in the system. To quickly configure such systems in an online manner, we propose a Probabilistic Trans-Algorithmic Search (PTAS) framework which leverages multiple optimization search algorithms in an iterative manner. PTAS applies a search algorithm to determine how to best distribute available experiment budget among multiple optimization search algorithms. It allocates an experiment budget to each available search algorithm and observes its performance on the system-at-hand. PTAS then probabilistically reallocates the experiment budget for the next round proportional to each algorithm’s performance relative to the rest of the algorithms. This “roulette wheel” approach probabilistically favors the more successful algorithm in the next round. Following each round, the PTAS framework “transfers” the best result(s) among the individual algorithms, making our framework a trans-algorithmic one. PTAS thus aims to systematize how to “search for the best search” and hybridize a set of search algorithms to attain a better search. We use three individual search algorithms, i.e., Recursive Random Search (RRS) (Ye and Kalyanaraman, 2004), Simulated Annealing (SA) (Laarhoven and Aarts, 1987), and Genetic Algorithm (GA) (Goldberg, 1989), and compare PTAS against the performance of RRS, GA, and SA. We show the performance of PTAS on well-known benchmark objective functions including scenarios where the objective function changes in the middle of the optimization process. To illustrate applicability of our framework to automated network management, we apply PTAS on the problem of optimizing link weights of an intra-domain routing protocol on three different topologies obtained from the Rocketfuel dataset. We also apply PTAS on the problem of optimizing aggregate throughput of a wireless ad hoc network by tuning datarates of traffic sources. Our experiments show that PTAS successfully picks the best performing algorithm, RRS or GA, and allocates the time wisely. Further, our results show that PTAS’ performance is not transient and steadily improves as more time is available for search.     

Efficient Processing of Large Data Structures on GPUs: Enumeration Scheme Based Optimisation

The purpose of this paper is to highlight the performance issues of the matrix transposition algorithms for large matrices, relating to the Translation Lookaside Buffer (TLB) cache. The existing optimisation techniques such as coalesced access and the use of shared memory, regardless of their necessity and benefits, are not sufficient enough to neutralise the problem. As the data problem size increases, these optimisations do not exploit data locality effectively enough to counteract the detrimental effects of TLB cache misses. We propose a new optimisation technique that counteracts the performance degradation of these algorithms and seamlessly complements current optimisations. Our optimisation is based on detailed analysis of enumeration schemes that can be applied to either individual matrix entries or blocks (sub-matrices). The key advantage of these enumeration schemes is that they do not incur matrix storage format conversion because they operate on canonical matrix layouts. In addition, several cache-efficient matrix transposition algorithms based on enumeration schemes are offered—an improved version of the in-place algorithm for square matrices, out-of-place algorithm for rectangular matrices and two 3D involutions. We demonstrate that the choice of the enumeration schemes and their parametrisation can have a direct and significant impact on the algorithm’s memory access pattern. Our in-place version of the algorithm delivers up to 100% performance improvement over the existing optimisation techniques. Meanwhile, for the out-of-place version we observe up to 300% performance gain over the NVidia’s algorithm. We also offer improved versions of two involution transpositions for the 3D matrices that can achieve performance increase up 300%. To the best of our knowledge, this is the first effective attempt to control the logical-to-physical block association through the design of enumeration schemes in the context of matrix transposition.     

Kaczmarz extended algorithm for tomographic image reconstruction from limited-data

The algebraic reconstruction technique (ART), based on the well known algorithm proposed by Kaczmarz in 1937, is one of the most important class of solution methods for image reconstruction problems. But unfortunately, almost all the methods from the ART class give satisfactory results only in the case of consistent problems. In the inconsistent case (and unfortunately this is what happens in real applications, because of measurement errors) they give only more or less “controllable” versions of the exact solutions. This is exactly the case that we analyze in the present paper. We start with a theoretical analysis of the classical Kaczmarz’s projection method in the case of an inconsistent linear least-squares problem and we prove that the approximations so obtained are at a certain distance from the set of exact least-squares solutions. This distance is controlled by the component of the right hand side of the problem lying in the orthogonal complement of the range of problem’s matrix, i.e. exactly the component that makes the problem inconsistent. For overcoming this difficulty we consider an extended version of Kaczmarz’s algorithm, previously analyzed by one of the authors. In the numerical experiments described in the last part of the paper we compare the above mentioned extension with two well known (ART) type algorithms for image reconstruction in two electromagnetic geotomography problems. The results indicate that the extended Kaczmarz algorithm gives much better results than the other two.     

Parallel custom instruction identification for extensible processors

With the ability of customization for an application domain, extensible processors have been used more and more in embedded systems in recent years. Extensible processors customize an application domain by executing parts of application code in hardware instead of software. Determining parts of application code as custom instruction generally requires subgraph enumeration and subgraph selection. Both subgraph enumeration problem and subgraph selection problem are computationally difficult problems. Most of previous works focus on sequential algorithms for these two problems. In this paper, we present a parallel implementation of a latest subgraph enumeration algorithm based on a computer cluster. A standard ant colony optimization algorithm (ACO), a modified version of ACO with local optimum search and a parallel ACO algorithm are also proposed to solve the subgraph selection problem in this work. Experimental results show that the parallel algorithms outperform the sequential algorithms in terms of runtime or (and) quality of results. In addition, we have formally proved the upper bound on the number of feasible solutions in subgraph selection problem with or without the overlapping constraint.     

A multicore solution to Block–Toeplitz linear systems of equations

There exist algorithms, also called “fast” algorithms, which exploit the special structure of Toeplitz matrices so that, e.g., allow to solve a linear system of equations in O(n ²) flops. However, some implementations of classical algorithms that do not use this structure (O(n ³) flops) highly reduce the time to solution when several cores are available. That is why it is necessary to work on “fast” algorithms so that they do not lose track of the benefits of new hardware/software. In this work, we propose a new approach to the Generalized Schur Algorithm, a very known algorithm for the solution of Toeplitz systems, to work on a Block–Toeplitz matrix. Our algorithm is based on matrix–matrix multiplications, thus allowing to exploit an efficient implementation of this operation if it exists. Our algorithm also makes use of the thread level parallelism featured by multicores to decrease execution time.     

Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials

We present a lattice algorithm specifically designed for some classical applications of lattice reduction. The applications are for lattice bases with a generalized knapsack-type structure, where the target vectors have bounded depth. For such applications, the complexity of the algorithm improves traditional lattice reduction by replacing some dependence on the bit-length of the input vectors by some dependence on the bound for the output vectors. If the bit-length of the target vectors is unrelated to the bit-length of the input, then our algorithm is only linear in the bit-length of the input entries, which is an improvement over the quadratic complexity floating-point LLL algorithms. To illustrate the usefulness of this algorithm we show that a direct application to factoring univariate polynomials over the integers leads to the first complexity bound improvement since 1984. A second application is algebraic number reconstruction, where a new complexity bound is obtained as well.     

Algorithms for computing association rules using a partial-support tree

This paper presents new algorithms for the extraction of association rules from binary databases. Most existing methods operate by generating “candidate” sets, representing combinations of attributes which may be associated, and then testing the database to establish the degree of association. This may involve multiple database passes, and is also likely to encounter problems when dealing with “dense” data due to the increase in the number of sets under consideration. Our method uses a single pass of the database to perform a partial computation of support for all sets encountered in the database, storing this in the form of a set enumeration tree. We describe algorithms for generating this tree and for using it to generate association rules.     

Verification of Galois field based circuits by formal reasoning based on computational algebraic geometry

Algebraic error correcting codes (ECC) are widely used to implement reliability features in modern servers and systems and pose a formidable verification challenge. We present a novel methodology and techniques for provably correct design of ECC logics. The methodology is comprised of a design specification method that directly exposes the ECC algorithm’s underlying math to a verification layer, encapsulated in a tool “BLUEVERI”, which establishes the correctness of the design conclusively by using an apparatus of computational algebraic geometry (Buchberger’s algorithm for Gröbner basis construction). We present results from its application to example circuits to demonstrate the effectiveness of the approach. The methodology has been successfully applied to prove correctness of large error correcting circuits on IBM’s POWER systems to protect memory storage and processor to memory communication, as well as a host of smaller error correcting circuits.     

Efficient exhaustive listings of reversible one dimensional cellular automata

This paper looks at an algebraic formulation of one dimensional cellular automata. Using the formulation connections to combinatorial structures and graph theory become clear. Strong results about uniqueness and isomorphism allows us to outline effective algorithms for the generation of exhaustive lists of reversible one dimensional cellular automata, and to count the number of distinct examples that exist. These algorithms use the “orderly algorithm” methods to avoid the pitfalls of brute force searches.     

Concurrent depth-first search algorithms based on Tarjan’s Algorithm

We present concurrent algorithms, based on depth-first search, for three problems relevant to model checking: given a state graph, to find its strongly connected components, which states are in loops, and which states are in “lassos”. Each algorithm is a variant of Tarjan’s Algorithm. Our algorithms typically exhibit a three- or four-fold speed-up over the corresponding sequential algorithms on an eight-core machine.     

Linear 0–1 programming: A comparison of implicit enumeration algorithms

This paper compares the following implicit enumeration algorithms for solving a linear zero-one programming (LZOP) problem: Balas' additive algorithm, Hammer-Rudeanu's algorithm, Peterson's algorithm, Zionts' generalized additive algorithm, Geoffrion's improved implicit enumeration algorithm and Zionts' generalized additive algorithm with surrogate constraints. The computational efficiency of these algorithms is compared in terms of computer time and the number of iterations required to solve unstructured problems. Some guidelines for selecting an appropriate algorithm for a given problem size are given.     

The correctness proof of Ben-Or’s randomized consensus algorithm

In a ground-breaking paper that appeared in 1983, Ben-Or presented the first randomized algorithm to solve consensus in an asynchronous message-passing system where processes can fail by crashing. Although more efficient randomized algorithms were subsequently proposed, Ben-Or’s algorithm is still the simplest and most elegant one. For this reason, it is often taught in distributed computing courses and it appears in several textbooks. Even though Ben-Or’s algorithm is widely known and it is very simple, surprisingly a proof of correctness of the algorithm has not yet appeared: previously published proofs make some simplifying assumptions—specifically, they either assume that f < n/3 (n is the total number of processes and f is maximum number of processes that may crash) or that the adversary is weak, that is, it cannot see the process states or the content of the messages. In this paper, we present a correctness proof for Ben-Or’s randomized consensus algorithm for the case that f < n/2 process crashes and the adversary is strong (i.e., it can see the process states and message contents, and schedule the process steps and message receipts accordingly). To the best of our knowledge, this is the first full proof of this classical algorithm. We also demonstrate a counterintuitive problem that may occur if one uses the well-known abstraction of a “global coin” to modularize and speed up randomized consensus algorithms, such as Ben-Or’s algorithm. Specifically, we show that contrary to common belief, the use of a global coin can sometimes be deleterious rather than beneficial: instead of speeding up Ben-Or’s algorithm, the use of a global coin in this algorithm may actually prevent termination.