Some applications of propositional logic to cellular automata

In this paper we give a new proof of Richardson's theorem [31]: a global function G_?? of a cellular automaton ?? is injective if and only if the inverse of G_?? is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamics groups of asynchronous cellular automata

We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) is π-independent if its set of periodic points are independent of the order that the local functions are applied. In this case, the local functions permute the periodic points, and these permutations generate the dynamics group. We have previously shown that exactly 104 of the possible 2²³=2562^{2^{3}}=256 cellular automaton rules are π-independent. In the article, we classify the periodic states of these systems and describe their dynamics groups, which are quotients of Coxeter groups. The dynamics groups provide information about permissible dynamics as a function of update sequence and, as such, connect discrete dynamical systems, group theory, and algebraic combinatorics in a new and interesting way. We conclude with a discussion of numerous open problems and directions for future research.     

Fast calculation based on a spatial two-grid finite element algorithm for a nonlinear space–time fractional diffusion model

In this article, a spatial two-grid finite element (TGFE) algorithm is used to solve a two-dimensional nonlinear space–time fractional diffusion model and improve the computational efficiency. First, the second-order backward difference scheme is used to formulate the time approximation, where the time-fractional derivative is approximated by the weighted and shifted Grünwald difference operator. In order to reduce the computation time of the standard FE method, a TGFE algorithm is developed. The specific algorithm is to iteratively solve a nonlinear system on the coarse grid and then to solve a linear system on the fine grid. We prove the scheme stability of the TGFE algorithm and derive a priori error estimate with the convergence result O(Δt² + h^{r + 1 − η} + H^{2r + 2 − 2η}) . Finally, through a two-dimensional numerical calculation, we improve the computational efficiency and reduce the computation time by the TGFE algorithm.     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

On large-scale diagonalization techniques for the Anderson model of localization

We propose efficient preconditioning algorithms for an eigenvalue problem arising in quantum physics, namely the computation of a few interior eigenvalues and their associated eigenvectors for large-scale sparse real and symmetric indefinite matrices of the Anderson model of localization. Our preconditioning approaches for the shift-and-invert symmetric indefinite linear system are based on maximum weighted matchings and algebraic multi-level incomplete LDL^T factorizations. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques for the highly ill-conditioned symmetric indefinite Anderson matrices. Our numerical examples reveal that recent algebraic multi-level preconditioning solvers can accelerate the computation of a large-scale eigenvalue problem corresponding to the Anderson model of localization by several orders of magnitude. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

FFTs on the Rotation Group

We discuss an implementation of an efficient algorithm for the numerical computation of Fourier transforms of bandlimited functions defined on the rotation group SO(3). The implementation is freely available on the web. The algorithm described herein uses O(B ⁴) operations to compute the Fourier coefficients of a function whose Fourier expansion uses only (the O(B ³)) spherical harmonics of degree at most B. This compares very favorably with the direct O(B ⁶) algorithm derived from a basic quadrature rule on O(B ³) sample points. The efficient Fourier transform also makes possible the efficient calculation of convolution over SO(3) which has been used as the analytic engine for some new approaches to searching 3D databases (Funkhouser et al., ACM Trans. Graph. 83–105, [2003]; Kazhdan et al., Eurographics Symposium in Geometry Processing, pp. 167–175, [2003]). Our implementation is based on the “Separation of Variables” technique (see, e.g., Maslen and Rockmore, Proceedings of the DIMACS Workshop on Groups and Computation, pp. 183–237, [1997]). In conjunction with techniques developed for the efficient computation of orthogonal polynomial expansions (Driscoll et al., SIAM J. Comput. 26(4):1066–1099, [1997]), our fast SO(3) algorithm can be improved to give an algorithm of complexity O(B ³log ² B), but at a cost in numerical reliability. Numerical and empirical results are presented establishing the empirical stability of the basic algorithm. Examples of applications are presented as well. First author was supported by NSF ITR award; second author was supported by NSF Grant 0219717 and the Santa Fe Institute.     

Injective linear cellular automata and sofic groups

Let V be a finite-dimensional vector space over a field and let G be a sofic group. We show that every injective linear cellular automaton τ: V ^G → V ^G is surjective. As an application, we obtain a new proof of the stable finiteness of group rings of sofic groups, a result previously established by G. Elek and A. Szabó using different methods.     

A graph isomorphism algorithm using pseudoinverses

For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn ²) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time.     

Amenability and Linear Cellular Automata Over Semisimple Modules of Finite Length

Let M be a semisimple left module of finite length over a ring R and let G be an amenable group. We show that an R-linear cellular automaton τ:M^G → M^G is surjective if and only if it is pre-injective.     

Computational methods for Conway's Game of Life cellular automaton

The cellular automaton model of computation has drawn the interest of researchers from different disciplines including computer science, biology, mathematics, economy, biochemistry and philosophy. Although a cellular automaton is based on a set of simple rules, over time complex patterns may evolve. We present computational methods for implementing and optimizing a well known two-state cellular automaton, Conway's Game of Life, on a 16-core Intel Xeon. The evaluation is based on three multicore algorithms. The first algorithm is coherent and utilizes shared memory and barrier synchronization. The remaining two algorithms are distributed and utilize private memories and explicit core-to-core message passing. We provide a link to our open source simulation software.     

Optimal query error of quantum approximation on some Sobolev classes

We study the approximation of the imbedding of functions from anisotropic and general-ized Sobolev classes into Lq([0,1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from LpN to LNq , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(Wpr ([0,1]d)) to Lq([0,1]d) space for all 1 q,p ∞ and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup roughly up to a squaring of the rate in the classical deterministic and randomized settings.     

Algorithms for Leader Election by Cellular Automata

We present two cellular algorithms, in O(n) and respectively in O(w²), for the leader election problem on finite connected rings F and respectively finite connected subsets of ^d, of eccentricity w, for any fixed d. The problem consists of finding an algorithm such that when setting the elements of F to a special state, and all the others to a state #, the cellular automaton iterates a finite number of steps and sets only one precise element of F to a special state called leader state, and all the others to a different state. We describe the algorithms in detail, give their proofs and complexities, and discuss the possible extensions.     

Directed acyclic subsequence graph—Overview

The subsequence matching problem is to decide, for given strings S and T, whether S is a subsequence of T. The string S is called the pattern and the string T the text. We consider the case of multiple texts and show how to solve the subsequence matching problem in time linear in the length of the pattern. For this purpose we build an automaton that accepts all subsequences of given texts. This automaton is called the Directed Acyclic Subsequence Graph (DASG). We prove an upper bound for its number of states. Furthermore, we consider a modification of the subsequence matching problem: given a string S and a finite language L, we are to decide whether S is a subsequence of any string in L. We suppose that a finite automaton accepting L is given and present an algorithm for building the DASG for language L. We also mention applications of the DASG to some problems related to subsequences.     

An O(n 3 L) adaptive path following algorithm for a linear complementarity problem

In this paper we propose an O(n ³ L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n ³ L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n ³ L).Research supported in part by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research supported in part by NSF grants ECS-8602534 and DMS-8904406 and ONR contract N-00014-87-K0212.     

Unitals in Finite Desarguesian Planes

We show that a suitable 2-dimensional linear system of Hermitian curves of PG(2,q ²) defines a model for the Desarguesian plane PG(2,q). Using this model we give the following group-theoretic characterization of the classical unitals. A unital in PG(2,q ²) is classical if and only if it is fixed by a linear collineation group of order 6(q + 1)² that fixes no point or line in PG(2,q ²).     

On Representation Formulas and Radiation Conditions

Solutions of linear elliptic partial differential equations in unbounded domains can be represented by boundary potentials if they satisfy certain conditions at infinity. These radiation conditions depend on the fundamental solution chosen for the integral representation. We prove some basic results about radiation conditions in a rather general framework. Fundamental solutions G are considered that are defined only on the complement of a compact set. It turns out, however, and we present examples for this, that the more interesting results only hold if G is defined on all of ℝⁿ or if it is a Green function for an exterior boundary value problem. © 1997 by B.G. Teubner Stuttgart-John Wiley & Sons, Ltd.     

Efficient Computation of the Hausdorff Distance Between Polytopes by Exterior Random Covering

In this paper, a simple yet efficient randomized algorithm (Exterior Random Covering) for finding the maximum distance from a point set to an arbitrary compact set in R^d is presented. This algorithm can be used for accelerating the computation of the Hausdorff distance between complex polytopes.     

Unique Maximum Matching Algorithms

We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log⁴ n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of planar graphs, we improve the algorithm to run in O(n log n) time. Second, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented using depth-first search. A generalization of Kotzig's theorem proved by Jackson and Whitty allows us to give a modification of the first algorithm that tests whether a given graph has a unique f-factor, and find it if it exists. We also show how to modify the second algorithm to check whether a given f-factor is unique. Both extensions have the same time bounds as their perfect matching counterparts. For the weighted case, we can test in linear time whether a maximum-weight matching is unique, given the output from Edmonds' algorithm for computing such a matching. The method is an extension of our algorithm for the unweighted case.     

A fast algorithm for numerical solutions to Fortet's equation

A fast algorithm for computation of default times of multiple firms in a structural model is presented. The algorithm uses a multivariate extension of the Fortet's equation and the structure of Toeplitz matrices to significantly improve the computation time. In a financial market consisting of M1 firms and N discretization points in every dimension the algorithm uses O(nlogn·M·M!·N^M(M-1)/2) operations, where n is the number of discretization points in the time domain. The algorithm is applied to firm survival probability computation and zero coupon bond pricing.