Universal computation in fluid neural networks

Fluid neural networks can be used as a theoretical framework for a wide range of complex systems as social insects. In this article we show that collective logical gates can be built in such a way that complex computation can be possible by means of the interplay between local interactions and the collective creation of a global field. This is exemplified by a NOR gate. Some general implications for ant societies are outlined. © 1996 John Wiley & Sons, Inc.     

Complexity,parallel computation and statistical physics

The intuition that a long history is required for the emergence of complexity in natural systems is formalized using the notion of depth. The depth of a system is defined in terms of the number of parallel computational steps needed to simulate it. Depth provides an objective, irreducible measure of history that is applicable to systems of the kind studied in statistical physics. It is argued that physical complexity cannot occur in the absence of substantial depth and that depth is a useful proxy for physical complexity. The ideas are illustrated for a variety of systems in statistical physics. © 2006 Wiley Periodicals, Inc. Complexity 11: 46–64, 2006     

Efficient parallel recognition of cographs

In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced P₄. For a graph on n vertices and m edges, both our cograph recognition and cotree construction algorithms run in time and require O((n+m)/logn) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal O(logn)-time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal O(logn)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced P₄) whenever our algorithms decide that the input graphs are not cographs.     

Optimal equi-partition of rectangular domains for parallel computation

We present an efficient method for the partitioning of rectangular domains into equi-area sub-domains of minimum total perimeter. For a variety of applications in parallel computation, this corresponds to a load-balanced distribution of tasks that minimize interprocessor communication. Our method is based on utilizing, to the maximum extent possible, a set of optimal shapes for sub-domains. We prove that for a large class of these problems, we can construct solutions whose relative distance from a computable lower bound converges to zero as the problem size tends to infinity. PERIX-GA, a genetic algorithm employing this approach, has successfully solved to optimality million-variable instances of the perimeter-minimization problem and for a one-billion-variable problem has generated a solution within 0.32% of the lower bound. We report on the results of an implementation on a CM-5 supercomputer and make comparisons with other existing codes.This research was partially funded by Air Force Office of Scientific Research grant F496-20-94-1-0036 and National Science Foundation grants CDA-9024618 and CCR-9306807.     

A mixed forward-backward dynamic programming method using parallel computation

We consider optimization problems which can be solved by either forward or backward dynamic programming. We propose a method which reduces the computing time by a factor of two when two processors are used in parallel.This research was sponsored by the National Science Foundation, Grant No. INT-78-09263, while the author was visiting at the University of California, Berkeley, California.     

Efficient on-line algorithms for Euler diagram region computation

Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic relationships. Sets are represented by closed curves in the plane and often have wellformedness conditions placed on them in order to enhance comprehensibility. The theoretical underpinning for tool support has usually focussed on the problem of generating an Euler diagram from an abstract model. However, the problem of efficient computation of the abstract model from the concrete diagram has not been addressed before, despite this computation being a necessity for computer interpretations of user drawn diagrams. This may be used, together with automated manipulations of the abstract model, for purposes such as semantic information presentation or diagrammatic theorem proving. Furthermore, in interactive settings, the user may update diagrams “on-line” by adding and removing curves, for example, in which case a system requirement is the update of the abstract model (without the necessity of recomputation of the entire abstract model). We define the notion of marked Euler diagrams, together with a method for associating marked points on the diagram with regions in the plane. Utilising these, we provide on-line algorithms which quickly compute the abstract model of a weakly reducible wellformed Euler diagram (constructible as a sequence of additions or removals of curves, keeping a wellformed diagram at each step), and quickly updates both the set of curves in the plane as well as the abstract model according to the on-line operations. Efficiency is demonstrated by comparison with a common, naive algorithm. Furthermore, the methodology enables a straightforward implementation which has subsequently been realised as an application for the user classification domain.     

Efficient Sparse LU Factorization with Left-Right Looking Strategy on Shared Memory Multiprocessors

An efficient sparse LU factorization algorithm on popular shared memory multi-processors is presented. Pipelining parallelism is essential to achieve higher parallel efficiency and it is exploited with a left-right looking algorithm. No global barrier is used and a completely asynchronous scheduling scheme is one central point of the implementation. The algorithm has been successfully tested on SUN Enterprise, DEC AlphaServer, SGI Origin 2000 and Cray T90 and J90 parallel computers, delivering up to 2.3 GFlop/s on an eight processor DEC AlphaServer for medium-size semiconductor device simulations and structural engineering problems.     

Efficient parallel exponentiation in using normal basis representations

Von zur Gathen proposed an efficient parallel exponentiation algorithm in finite fields using normal basis representations. In this paper we present a processor-efficient parallel exponentiation algorithm in GF(qⁿ) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(qⁿ) can be done in O((log₂n)²/log_qn) time using n/(log₂n)² processors. Hence we get a processor-time bound of O(n/log_qn), which matches the best known sequential algorithm. Finally, we present an efficient on-line processor assignment scheme which was missing in von zur Gathen's algorithm.     

Efficient parallel multivalue hybrid methods for stiff differential equations

A class of efficient parallel multivalue hybrid methods for stiff differential equations are presented, which are all extremely stable at infinity,A-stable for orders 1–3 and A(α)-stable for orders 4–8. Each method of the class can be performed parallelly using two processors with each processor having almost the same computational amount per integration step as a backward differentiation formula (BDF) of the same order with the same stepsize performed in serial, whereas the former has not only much better stability properties but also a computational accuracy higher than the corresponding BDF. Theoretical analysis and numerical experiments show that the methods constructed in this paper are superior in many respects not only to BDFs but also to some other commonly used methods.     

Efficient Algorithms for Tandem Queueing system simulation

Serial and parallel algorithms for simulation of tandem queueing systems with infinite buffers are presented, and their performance are examined. It is shown that the algorithms which are based on a simple computational procedure involve low time and memory requirements.     

A massively parallel exponential integrator for advection-diffusion models

This work considers the Real Leja Points Method (ReLPM), [M. Caliari, M. Vianello, L. Bergamaschi, Interpolating discrete advection-diffusion propagators at spectral Leja sequences, J. Comput. Appl. Math. 172 (2004) 79-99], for the exponential integration of large-scale sparse systems of ODEs, generated by Finite Element or Finite Difference discretizations of 3-D advection-diffusion models. We present an efficient parallel implementation of ReLPM for polynomial interpolation of the matrix exponential propagators and , φ(z)=(exp(z)−1)/z. A scalability analysis of the most important computational kernel inside the code, the parallel sparse matrix-vector product, has been performed, as well as an experimental study of the communication overhead. As a result of this study an optimized parallel sparse matrix-vector product routine has been implemented. The resulting code shows good scaling behavior even when using more than one thousand processors. The numerical results presented on a number of very large test cases gives experimental evidence that ReLPM is a reliable and efficient tool for the simulation of complex hydrodynamic processes on parallel architectures.     

Efficient parallel simulation of biphasic materials in biomechanics

Biphasic materials are widely used for the modelling and the numerical simulation of articular cartilage within joints. In combination with contact, the numerical solution of the arising discrete systems is a demanding task, in particular for realistic geometries. We consider the stability and efficiency of different multilevel approaches for the numerical solution of the resulting non–smooth systems. Moreover, multilevel methods are derived which allow for the efficient numerical simulation of biphasic materials in contact. Numerical examples on problem specific geometries in three space dimensions are given. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains

We describe a distributed memory parallel Delaunay refinement algorithm for simple polyhedral domains whose constituent bounding edges and surfaces are separated by angles between 90° to 270° inclusive. With these constraints, our algorithm can generate meshes containing tetrahedra with circumradius to shortest edge ratio less than 2, and can tolerate more than 80% of the communication latency caused by unpredictable and variable remote gather operations.

Our experiments show that the algorithm is efficient in practice, even for certain domains whose boundaries do not conform to the theoretical limits imposed by the algorithm. The algorithm we describe is the first step in the development of much more sophisticated guaranteed-quality parallel mesh generation algorithms.     

封闭容器中二维自然对流直接数值模拟的一个并行算法

本文对具有不同温度竖壁的封闭容器中二维自然对流问题进行了直接数值模拟,控制方程在非均匀网络上使用空间二阶精度和时间一阶精度进行离散,程序是在国家高性能计算中心（武汉）的并行计算机“曙光１０００Ａ”上实现的,使用４个结点,获得的加速比和效率分别约为２．８９和０．７２。     

On the parallel computation of the biconnected and strongly connected co-components of graphs

In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m edges both run in optimal O(n+m) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search.Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in time using processors. The strong co-connectivity algorithm can also be parallelized to yield an -time and O(m^1.188/logn)-processor solution. As a byproduct, we obtain a simple optimal O(logn)-time parallel co-connectivity algorithm.Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself.     

Massively parallel computation of large-scale spatial price equilibrium models with discriminatory ad valorem tariffs

In this paper, we develop a perfectly competitive spatial equilibrium model in price and quantity variables in the presence of discriminatory ad valorem tariffs, a widely used trade policy instrument. We derive the equilibrium conditions and formulate them as a variational inequality problem. An algorithm is then proposed for the computation of the equilibrium pattern and convergence results established. The algorithm resolves the problem into very simple subproblems, each of which can be solved simultaneously and in closed form. Finally, the algorithm is implemented on the massively parallel Thinking Machines CM-2 and CM-5 architectures, known as the Connection Machines, and numerical results presented.     

Recent advances in automatic classification

Traditional classification methods are divided into two broad types: hierarchical methods and non-hierarchical methods in which the number of classes has to be fixed in advance. Both methods can handle both quantitative and qualitative data. A third type finds a partition optimizing a linear classification criterion (e.g. the Condorcet criterion) in which the number of classes does not have to be fixed in advance, but the data must be qualitative. A recent generalization, the ‘S theory’ can handle simultaneously both quantitative and qualitative data, and both linear and non-linear classification criteria (in the space of paired comparisons of elements). With this ‘S theory’ the partition is obtained in order n (in terms of memory space and elementary operations), n being the number of elements to classify.     

Program for simulation of relay networks

The program described here has been tried out in order to simulate a relay network with such a degree of complexity, that its function can not be satisfactorly surveyed with manual methods. Since the program has a separate part, which translates Boolean equations and conditions of time delay written symbolically into the machine language, the program has got greater range of application and can be used for simulation of all systems, which can be represented in that way.     

Efficient computation of sparse structures

Basic graph structures such as maximal independent sets (MIS's) have spurred much theoretical research in randomized and distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault‐tolerance or load‐balance properties. We propose and study “low‐average degree” or “sparse” versions of such structures. Interestingly, in sharp contrast to, say, MIS's, it can be shown that checking whether a structure is sparse, will take substantial time. Nevertheless, we are able to develop good sequential/distributed (randomized) algorithms for such sparse versions. We also complement our algorithms with several lower bounds. Randomization plays a key role in our upper and lower bound results. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 322–344, 2016