Keywords

1 Introduction

There are many systems in nature that we can undoubtedly name it as a complex system. Very often, however, calling something as complex, we generally think how complex is its model, not exactly the system itself. For creating a model we employ the conceptual frameworks from the fields of mathematics, physics, chemistry etc. It is obvious, that the selection of these concepts/abstractions significantly determines the nature and complexity of the resulting model.

Because of selectively revealing only some aspects of the complex system, the models are always a restriction of the observed reality. Agreeing with these selectivity of transition from system to its model, we should decide what properties of real system should characterize well-suited projection of mapping the reality. If the behavior of complex system is really complex to our mind, the models we develop are certainly complicated, but they will become simpler when we understand it better. It turns out that complexity reflects inability to develop simple models to describe the behavior of these systems.

Another issue is the choice of tools suitable to model and to analyze complex systems. Along with creating better models, we must also figure out how to evaluate success when choosing tools for working on them. The proper selection of system modeling tools, results in transparent model and facilitates its further analysis. Ill-suited selection of methods and tools leads to increased complexity of the model and indirectly will be a reason of future problems that undoubtedly will appear during analysis of its behavior.

2 Complex Systems Properties

Modern development of computer technology allows for extensive use of parallel computing techniques for modeling a behavior of complex systems. New GPUs and streaming multiprocessor’s card, assisted by the parallel programming technology opens a wide range for their use.

One of the areas, where these new technologies especially comes in handy, is the modeling of complex systems. However, the definition of a complex system is still the basic problem. We can find, in the literature, a lot of opinions what is a complex system. Some papers discuss the relativity of this idea, claiming that; the same system, that by one may be seen as complex and unpredictable, by another may be seen as simple and easily understood. Another researches state that, complexity is a measure of the observer misunderstanding what system is being examined. Before going any further, in this paper we follow Corning, Lloyd, Northrop [3, 5, 9] who argue that complexity generally possess three attributes:

  1. (a)

    a complex system has many parts (items, units, parameters, variables),

  2. (b)

    there are many relationships, interactions between the parts,

  3. (c)

    the parts produce combined effects (synergies) that are not easily foreseen and may often be novel, surprising, unexpected, chaotic.

There are many examples of complex system characterized by having many parts, parameters or states that are functionally interconnected and generally leading to non-intuitive system behavior. For our purpose let us consider a few of them.

3 Computational Complexity

Mathematics occupies special place in the development of the complex systems models. For centuries, mathematicians has been attempting to develop tools to study these problems. So, at the beginning, we start with a pure mathematical example with intricacy measure classified as computational complexity. The problem is referred to as the problem of n-queens and may be formulated as follows: How can N queens be placed on an \(N \times N\) chessboard, so that no two of them attack each other? For the sake of a full problem formulation, it must be recalled that a chessboard queens can attack horizontally, vertically, and diagonally.

The considered problem has no counterparts in nature or technology. Its peculiarity is that the relationships between elements are very clear and simple. One simple sentence surely was enough to describe these relationships precisely. Moreover, it is difficult to find any complex and unpredictable behavior as a whole. Even if the we assume that someone has no computational background and very little mathematical background, essentially it is not difficult to explain him what the problem is. So, where lies the complexity of this issue? The answer is: the multitude of solutions necessary to be checked makes this issue computationally hard. Even if we skillfully perform this check (not brute force), the number of operations required, soared with increasing number of chessboard fields.

Today, \(N = 26\) is the maximum value for which we know the number of N-queens problem solutions. It is an order of magnitude of \(2\cdot 10^{16}\).

The number of all squares in \(N \times N\) chessboard (CB) is defined as \(card (CB)= N^2=26^2=676\), while the number of all subsets of CB is \(Pow (CB) = 2 ^ {card (CB)} = 2 ^{ (N\cdot N )} = 2 ^{ 676} \simeq 3 * 10 ^ {203}\). This is an awfully big number. We reduce it, putting the requirement that every solution must consist of \(N = 26\) elements, although we know that for \(N=8\) the domination number (minimum number) of queens that meet the required condition is 5. As a result we obtain the reduction of the search space to the value of \(N!=26!\simeq 4\cdot 10^{26}\). It’s still a very large number, so we are looking for an algorithms which exploit the idea of propagation and backtracking.

Implementing a backtracking algorithm, and using tree pruning techniques of the state space, the algorithm will examine only a fraction 1 % of the entire state space. It sounds optimistic, but 1 % means that obtained reduction of the entire problem is an order of magnitude \(10^2\), but this is meager compared with the enormous number \(10^{26}\) of states.

So, we are still on the road! Neither the implementation of parallel computing, nor application of special hardware, can improve this situation. Let us remember about the rules governing the parallelization of algorithms (e.g. Amdahl’s rule) and the fact, that even we had an infinite number of cores, we can reach all solutions in linear time. Alas, we do not have an infinite number of cores. Therefore, in this way we can only obtain an speed-up of computation, but not solution of the problem.

Mathematics, while attempting to develop tools to study these (NP-hard) problems, will be sought new conceptual frameworks. The first signal we have already. In complex systems relationships and topological properties play an important role. Considering propagation and backtracking algorithms; they work in state space tree locally (neighborhood is a topological abstraction) using such relations as: subordination (parent-child), tolerance (promising node) and collision (dead end node). To cope with complexity we tend to use both, a wide variety of mathematical techniques (e.g., combinatorial or arithmetic functions and differential equations) as well as topological, relational and set theory frameworks. The latter possess substantive advantages over their analytical counterparts, and are devoid of profound assumptions and some limitations.

4 Structuring a Complex Systems Models

Let us consider water distribution network as another example of a complex system possesses (a), (b) attributes from the Corning, Lloyd, Northrop [3, 5, 9] list presented above.

Water distribution network is a technical system with a large degree of complexity, both structural, technological and computational. It extends over large areas, so it is geographically distributed system. Moreover, it is distributed due to decision-making. The spatial distribution of water consumers demand varies in time. Decisions on this matter are taken by consumers individually. When pressure in network will increase, the consumer reduce tap water, what locally decrease the flow, and affects the activity of whole system. Also, decisions about supply parameters although coordinated, however, strongly depend on the local conditions that temporary prevail in neighborhood of reservoirs and pumping stations.

Multi-loop structure of the pipeline network, multitude and diversity of components (pipes, nodes, valves, tanks, pumps, fittings) entails the diversity of relationships between system elements. So, we have fulfill locally both, functions (especially for pipe sections) as well as relationships which can be calculated from the nomograph of a transit function (in case of fittings). Good knowledge of local physical rules provide us:

  1. (i)

    Darcy-Weisbach equation for a head loss due to the friction along a given length of pipe segment, to the average velocity of the water flow.

  2. (ii)

    Hazen-Williams equation which relates the flow of water in a pipeline with the physical properties of the pipeline and the pressure drop caused by friction.

  3. (iii)

    Mannings equation estimating the average velocity of a water flowing in an open channel (i.e. driven by a gravity).

  4. (iv)

    Hydraulic Grade Line, the sum of pressure head and elevation head

  5. (v)

    Velocity profile in a pipeline, which generally is greatest at the center of the pipe.

Topological properties of a pipeline network as a whole (so globally) are described by incidence matrix \(A_{ [m \times n]}\) (where m denotes the number of nodes, and n is number of pipe segments) and by loop matrix \(B_{[n \times o]}\) (where o represents the number of loops). First and second Kirchhoff’s laws forming two global relationships in whole water distribution network. The first law - material continuity at a node

$$\begin{aligned} A\cdot y=\sigma . \end{aligned}$$
(1)

where \(y\in R^n\) and \(\sigma \in R^m\) is a vector of consumer demands.

The second law - loop equations

$$\begin{aligned} B\cdot x = 0; \quad 0\in R^n \end{aligned}$$
(2)

where x is a vector of head difference between two ends of a pipeline segment.

The model of water distribution network consists of set of Eqs. (1)–(2), determining the global relationships, extended with plenty of local dependencies (i)–(v). While modeling water distribution network [1, 6, 7, 12] we could tackle it using sequential programing. In such a case, putting the expressions (i)–(v) into Eqs. (1)–(2) cause that these latter become nonlinear. Moreover, using sequential approach we have to treat network as a whole, although it is evident that water distribution network consists of many divers elements. Consequently, even when something changes locally, we should re-calculate the model of all network. So, in that case a global perspective overshadow local activity, evoking a number of undesirable computational consequences.

Fig. 1.
figure 1

Three examples of node P topological neighborhood (a.- nodes-edges, first order, b.- nodes-edges, second order, c.- loops-edges neighborhood.)

Full size image
Fig. 2.
figure 2

Different type of tree structure according to global ordering relation(a.- for chosen pipe diameters, b.- minimum spanning tree, c.- trunk pipeline).

Full size image
Fig. 3.
figure 3

Structuring the water supply network model using multicores structure (Kepler GK110, \(3 \cdot 4 \cdot 16 \cdot 15 = 2880\) cores).

Full size image

Local and global activities are not actually in competition, because the best approach is to combine them. That is what we would like to do using parallel programing techniques. Having at our disposal many (hundreds or thousands) cores (Fig. 3), we can harnessed many of them to calculate local dependencies within neighborhoods. Simultaneously, other cores can support the process of casting some global laws (Kirchhoff’s) from the whole network area to the neighborhood.

The incidence (A) and loop (B) matrices reflect a topological properties of the whole pipeline network. Employing the theories of sets and relations, we can shape the neighborhood abstraction, according to individual requirements of modeling (Figs. 1 and 2). The number of possible neighborhoods is huge. More than enough to model (using this topological framework) a very diverse situations that can occur in the water supply network.

5 Modeling of Collective Animal Behavior

Presented in the previous section the water distribution system, despite the high degree of complexity is (as a technical layout) fully predictable. Its mathematical model consisting of set of nonlinear equations, can exhibit unstable, chaotic behavior. However, this chaotic behavior is, in fact, deterministic. Its occurrence, at first may appear random, but for example, the conditions of high frequency oscillation in pipeline are very well known. Not all complex systems possess such a property. In many of occurring in nature complex systems [14] we can observe such features as chaotic behavior and a tipping points. How to model the chaotic behavior?

Flocking starlings is a good example of a natural complex system with collective chaotic behavior, so it is worth to spend some time on it. The papers dealing with complexity of a natural complex systems appear regularly in journals. Plenty of them raises the issue of collective animal behavior.

At first glance it seems that flocking birds or shoaling fish, using the classification outlined in Chapter 2, should be characterized by all three attributes (a), (b), (c). It means; has many parts; there are many relationships between the parts; and the parts produce combined effects that are not easily foreseen and may often be novel, surprising, unexpected, chaotic. However, the most authors emphasize that in these collectivizes there are no many relationships between the members.

One of the best known model of the birds collective behavior was proposed by Reynolds [11]. He claims that, in order to properly model the collective behavior of birds, is sufficient to consider three types of local interactions between individuals forming the flock. Each bird should follow three rules:

  • Dispersion, as a result of the collision avoidance. The bird maintains a minimum distance from other birds thereby avoid collisions with the neighbors.

  • Alignment, as a result of the velocity matching, i.e. birds matches its own velocity (as a vector) with the neighbors.

  • Cohesion, as attraction toward the birds within the neighborhood. The bird steer to move toward the average position of local flockmates.

Remarkably, these three very simple rules govern the local interactions between neighbors to each other, and produce a realistic-looking flocking behavior. The Craig model confirms that complex behavior, like flocking, need not have many and complex rules.

Craig’s work has shown, how the control of local activity has an impact on the behavior of the whole, but only for one, selected (starlings) group of birds. Craig’s model does not explain how a delta of ducks or V-shaped formation of geese [13] are formed. To do this, we use parallel programming, the set theory [4], and relations defined on them.

If we use the topological abstractions, we can structure the flock (using ordering relation), and to obtain the encountered in the nature, well shaped structures of birds flock. Usage of the relations; subordination (\(\pi \)), tolerance (\(\vartheta \)) and collision (\(\varkappa \)) is indirect descendant of Craig’s ideas. Indeed, subordination is global exemplification of Alignment while both global tolerance and collision are analogue to local Cohesion, and Dispersion.

A three global relations; subordination, tolerance and collision allow coordination of the behavior of individuals in the group as a whole. And so, dwindling subordination produces the effects of chaos noticeable in the behavior of flocking starlings. Consistently, strengthen coordination with simultaneous reduction in the tolerance, resulting in the formation as delta of ducks or V-shaped formation of geese and finally line of oystercatchers, as we observe on the sky [8]. Finally, the presence in the model of these three relations, allows to model the influence of environmental stimuli on whole group behavior. Predator - prey interactions like flash expansions of flocking birds forming eddies on the sky or bait balls of schooling fish cruising parabolas [10] are good examples of such behavior.

6 Conclusion

A major challenge in dealing with complex system is, how to formulate its mathematical model [2, 9], which allow us to predict the system’s behavior. For this purpose, unprecedented technological progress in the construction of computer hardware realizing highly paralleled computing, has given us a new tool to perform computer calculations. Parallel computations are the tool which have the biggest impact on complex system modeling.

Parallel computing tools accelerate calculation in case of problem that’s hard because of computational complexity, but above all that, with its help we can more accurately model real complex systems. Having at our disposal a computer operating parallel, we are looking for solutions tailored just for such equipment.

As a result, now we can model distributed system, using neighborhood relation in natural way, as a set of distributed elements cooperating with each other. Moreover, we can use relations to insulate us from reductionism and single-cause thinking, as people deal with complexity before. Our experience has indicated that (for complex, distributed systems) it is generally more effective to try multiple inputs in parallel way, than assigning single causes for any outputs.