An experimental comparison of four graph drawing algorithms

In this paper we present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms take as input general graphs (with no restrictions whatsoever on connectivity, planarity, etc.) and construct orthogonal grid drawings, which are widely used in software and database visualization applications. The test data (available by anonymous ftp) are 11,582 graphs, ranging from 10 to 100 vertices, which have been generated from a core set of 112 graphs used in “real-life” software engineering and database applications. The experiments provide a detailed quantitative evaluation of the performance of the four algorithms, and show that they exhibit trade-offs between “aesthetic” properties (e.g., crossings, bends, edge length) and running time.     

Linkless symmetric drawings of series parallel digraphs

In this paper, we present a linear time algorithm for constructing linkless drawings of series parallel digraphs with maximum number of symmetries. Linkless drawing in three dimensions is a natural extension to planar drawing in two dimensions. Symmetry is one of the most important aesthetic criteria in graph drawing. More specifically, we present two algorithms: a symmetry finding algorithm which finds maximum number of three dimensional symmetries, and a drawing algorithm which constructs linkless symmetric drawings of series parallel digraphs in three dimensions.     

“Drawings since hit tables in lotteries” and a new multivariate geometric distribution

In number lotteries people choose r numbers out of s. Weekly published “drawings since hit tables” indicate how many drawings have taken place since each of the s numbers was last selected as a winning number. Among many lotto players, they enhance the widespread belief that numbers should be “due” if they have not come up for a long time. Under the assumptions of independence of the drawings and equiprobability of all possible combinations, the random s-vectors Y_n, n 1, of entries in a drawings since hit table after n drawings form a Markov chain. The limit distribution of Y_n as n → ∞ is a new multivariate generalization of the geometric distribution. The determination of the distribution of the maximum entry in a drawings since hit table within the first n draws of a lottery seems to be an open problem.     

Nondeterministic dynamic programming on a parallel coprocessing system

We describe how nondeterministic dynamic programming (DP) algorithms can be designed for a new class of parallel coprocessing systems using “functional memory”, an architecture based upon dataflow computer principles. We also show how Petri nets can be used to model and express such parallel DP algorithms. Finally, we discuss architectural improvements that would facilitate the processing of Petri net models of nondeterministic DP algorithms on functional memory computers (FMC).     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

Intrinsically parallel solution of systems of linear partial differential equations

We give here an intrinsically parallel algorithm, which solves systems of linear partial differential equations. The mathematical foundations of the algorithm rely upon a particular representation of polynomials on a structure called “hypercube”, introduced by Beauzamy-Frot-Millour, and use Bombieri's scalar product. This scalar product also permits a detailed study of the stability of the algorithm. Boundary conditions and compatibility conditions are handled by the algorithm in an intrinsically parallel manner. This algorithm has been implemented on a Connection Machine CM5, at the “Etablissement Technique Central de l'Armement” (Arcueil, France). We give here several numerical examples.     

On behavior of two-dimensional non-plane parallel turbulent flows of inviscid gas

The time behavior of two-dimensional flows of inviscid gas in which the velocity component normal to the plane of independent variables and the vorticity components parallel to this plane are different from zero, is investigated. Equations of such flows form two different subsystems. The first subsystem describes a plane parallel (“primary”) flow without the third velocity component, and is independent of the second subsystem consisting of a single equation for the third velocity component and determining the “secondary” flow. The flows are analyzed with sufficient detail without using numerical integration which carries with it unavoidable errors, and without linearization, both of which are employed to a lesser or greater degree in the study of the evolution of vortical structures (see /1–6/).     

Planar and axially symmetric configurations which are circumvented with the maximum critical mach number

The structure of planar and axially symmetric configurations which, by satisfying a number of geometrical constraints, are circumvented in a boundless space or in a cylindrical channel by an ideal (non-viscous and non-thermally conducting) gas with a maximal critical Mach number M* is found. The analysis is carried out using the “rectilinearity property” of a sonic line in “subsonic” flows (SF), the “principle of a maximum” for an SF and “comparison theorems” which are either taken from /1/ or serve as a generalization of the corresponding assertions from /1/. Following /1/, configurations are considered which have a plane or axis of symmetry parallel to the velocity V_∞ of the approach stream, while flows in which (including the boundary) the Mach number M 1 are said to be “subsonic”. As usual, by M* we mean a value of M_∞ such that the inequality M1, which is satisfied in the whole stream when M_∞ M*, is violated when M_∞>M*.

The configurations investigated include closed bodies and the leading (trailing) parts of a semi-infinite plate or a circular cylinder in an unbounded flow and in a channel as well as lattices of symmetric profiles. Both in /1/, where the structure of closed planar and axially symmetric bodies was found, as well as in /2/, where such bodies were constructed numerically, the generatrices of all the configurations investigated contain the end planes or the segments replacing them of the maximum permissible slope (in modulus) and the “free” streamlines with M 1. Now, however, unlike in /1, 2/, segments of the horizontals are added to it in the general case. Furthermore, in the case of flows in channels and lattices, the configurations which have been found can be circumvented with the development of finite domains of advancing sonic flow.     

Fuzzy logic in measurements

Our main interest in this paper is to translate from “natural language” into “system theoretical language”. This is of course important since a statement in system theory can be analyzed mathematically or computationally. We assume that, in order to obtain a good translation, “system theoretical language” should have great power of expression. Thus we first propose a new frame of system theory, which includes the concepts of “measurement” as well as “state equation”. And we show that a certain statement in usual conversation, i.e., fuzzy modus ponens with the word “very”, can be translated into a statement in the new frame of system theory. Though our result is merely one example of the translation from “natural language” into “system theoretical language”, we believe that our method is fairly general.     

Parallel iteration across the steps of high-order Runge-Kutta methods for nonstiff initial value problems

For the parallel integration of nonstiff initial value problems (IVPs), three main approaches can be distinguished: approaches based on “parallelism across the problem”, on “parallelism across the method” and on “parallelism across the steps”. The first type of parallelism does not require special integration methods and can be exploited within any available IVP solver. The method-parallelism approach received much attention, particularly within the class of explicit Runge-Kutta methods originating from fixed point iteration of implicit Runge-Kutta methods of Gaussian type. The construction and implementation on a parallel machine of such methods is extremely simple. Since the computational work per processor is modest with respect to the number of data to be exchanged between the various processors, this type of parallelism is most suitable for shared memory systems. The required number of processors is roughly half the order of the generating Runge-Kutta method and the speed-up with respect to a good sequential IVP solver is about a factor 2. The third type of parallelism (step-parallelism) can be achieved in any IVP solver based on predictor-corrector iteration and requires the processors to communicate after each full iteration. If the iterations have sufficient computational volume, then the step-parallel approach may be suitable for implementation on distributed memory systems. Most step-parallel methods proposed so far employ a large number of processors, but lack the property of robustness, due to a poor convergence behaviour in the iteration process. Hence, the effective speed-up is rather poor. The dynamic step-parallel iteration process proposed in the present paper is less massively parallel, but turns out to be sufficiently robust to achieve speed-up factors up to 15.     

How Emergent Models May Foster the Constitution of Formal Mathematics

This article deals with the role that so-called emergent models can play in the process of constituting formal mathematics. The underlying philosophy is that formal mathematics is something that is, or should be, constituted by the students themselves. In the instructional design theory for realistic mathematics education, models always have been employed to foster a process in which formal mathematics is reinvented by the students themselves. This article describes how the use of models became more and more explicated over time and developed into the notion of emergent models. The design of an instructional sequence, which deals with flexible mental computation strategies for addition and subtraction up to 100, is taken as an instance for elaborating what is meant by emergent models and what role they play in fostering the constitution of formal mathematics. The analysis shows that there are 3 interrelated processes. First. at a more holistic level, there is a global transition in which “the model” initially emerges as a model of informal mathematical activity and then gradually develops into a model for more formal mathematical reasoning. Second, the transition from “model of” to “model for” involves the constitution of anew mathematical reality that can be denoted formal in relation to the original starting points of the students. Third, in the series of instructional activities, there is not 1 model, but the model actually is shaped as a series of signs, in which each new sign comes to signify activity with a previous sign in a chain of signification.     

A global approach to automatic solution of jigsaw puzzles

We present a new algorithm for automatically solving jigsaw puzzles by shape alone. The algorithm can solve more difficult puzzles than could be solved before, without the use of backtracking or branch-and-bound. The algorithm can handle puzzles in which pieces border more than four neighbors, and puzzles with as many as 200 pieces. Our overall strategy follows that of previous algorithms but applies a number of new ideas, such as robust fiducial points, “highest-confidence-first” search, and frequent global reoptimization of partial solutions.     

A Linear Time Algorithm for Constructing Maximally Symmetric Straight Line Drawings of Triconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. To draw graphs symmetrically, we employ two steps. The first step is to find appropriate automorphisms. The second step is to draw the graph to display the automorphisms. Our aim in this paper is to construct maximally symmetric straight line drawings of triconnected planar graphs in linear time. Previously known algorithms run in quadratic time. We show that an algorithm of Fontet can be used to find an embedding in the plane with the maximum number of symmetries, and present a new algorithm for finding a straight line drawing that achieves that maximum. Both algorithms run in linear time.     

What Monte Carlo models can do and cannot do efficiently?

The question “what Monte Carlo models can do and cannot do efficiently” is discussed for some functional spaces that define the regularity of the input data. Data classes important for practical computations are considered: classes of functions with bounded derivatives and Hölder type conditions, as well as Korobov-like spaces.

Theoretical performance analysis of some algorithms with unimprovable rate of convergence is given. Estimates of computational complexity of two classes of algorithms – deterministic and randomized for both problems – numerical multidimensional integration and calculation of linear functionals of the solution of a class of integral equations are presented.     

Generalizing the modeling of fuzzy logic controllers by parameterized aggregation operators

We describe the type of reasoning used in the typical fuzzy logic controller, the Mamdani reasoning method. We point out the basic assumptions in this model. We discuss the S-OWA operators which provide families of parameterized “andlike” and “orlike” operators. We generalize the Mamdani model by introducing these operators. We introduce a method, which we call Direct Fuzzy Reasoning (DFR), which results from one choice of the parameters. We develop some learning algorithms for the new method. We show how the Takagi-Sugeno-Kang (TSK) method of reasoning is an example of this DFR method.     

Polygonal chains cannot lock in 4D

We prove that, in all dimensions d4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be achieved by algorithms that use polynomial time in the number of vertices, and result in a polynomial number of “moves”. These results contrast to those known for d=2, where trees can “lock”, and for d=3, where open and closed chains can lock.     

Students' Critical Awareness of Voice and Agency in Mathematics Classroom Discourse

This account of my extended conversation with a high school mathematics class focuses on voice and agency. As an investigation of possibilities opened up by introducing mathematics students to what Fairclough (1992) called “critical language awareness” (p. 2), I prompted the students daily to become ever more aware of their language practices in class. The tensions in this conversation proved parallel to the tension in mathematics between individual initiative and convention, a tension that Pickering (1995) called the “dance of agency” (p. 21). Participant students in this classroom-based research resisted the idea of linguistic reference to human agency, although their actual language practice revealed some recognition of human agency.     

A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Minimum cost multicommodity flows are a useful model for bandwidth allocation problems. These problems are arising more frequently as regional service providers wish to carry their traffic over some national core network. We describe a simple and practical combinatorial algorithm to find a minimum cost multicommodity flow in a ring network. Apart from 1 and 2-commodity flow problems, this seems to be the only such “combinatorial augmentation algorithm” for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each link by one, we may also find an integral routing of no greater cost. The “pivots” in the algorithm are determined by choosing an >0, increasing and decreasing sets of variables, and adjusting these variables up or down accordingly by . In this sense, it generalizes the cycle cancelling algorithms for (single source) mincost flow. Although the algorithm is easily stated, proof of its correctness and polynomially bounded running time are more complex.     

Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.     

A generalization of the zero–one principle for sorting algorithms

In this paper a new general approach for the so-called “zero-one principle” for sorting algorithms is described. A theorem from propositional logic that states the connection between two-valued logic and many-valued logic is used to prove this zero-one principle. As a consequence a zero-one principle for a more general class of sorting algorithms is derived.