Berkeley Lab Scientific Computing Seminar

Date:
Thursday, October 25, 2007
Time:
11:00am-12:00pm
Location:
Building 50A-5132
Seminar Speaker:
Victor Korotkikh
Central Queensland University, Australia
Title:
On a New Type of Information Processing for Efficient Management of Complex Systems
Abstract:
It is still unknown how to deal with complex systems efficiently without confronting NP-complete problems. To address the situation we use the description of complex systems in terms of self-organization processes of prime integer relations [1].

The description is realized through the unity of its two equivalent forms, i.e., arithmetical and geometrical [1], [2]. In the arithmetical form a complex system is characterized by nonlocal correlation structures built in accordance with self-organization processes of prime integer relations. In the geometrical form the self-organization processes of prime integer relations become isomorphically represented by certain transformations of two-dimensional patterns determining the dynamics of the complex system. In preserving a complex system as a whole the equivalence of the forms unites the dynamics and the structure of the system. The dynamics of a complex system is determined by spacetime patterns of the parts to fit precisely into the geometrical patterns of the system. If this condition is not met, then one or more of the relationships provided by the prime integer relations for the correlation structures disappear and the complex system collapses. To measure the complexity of a system a concept of complexity, called the structural complexity, is introduced [1]. Starting with integers the self-organization processes of prime integer relations progress to different levels and thus produce a hierarchical complexity order. The higher the level self-organization processes progress to, the greater is the structural complexity of the system. The description suggests a new type of information processing. The correlation structures of a complex system contain information about the parts. By changing some parts the information can be processed with the other parts changing in accordance with the prime integer relations. Since the correlation structures of a complex system can be equivalently represented by two-dimensional geometrical patterns, the entropy of the system, measuring its information content, becomes dependent on the area of the two-dimensional patterns. Thus, in our approach there is a general connection between entropy and area.

To investigate whether the performance of an optimization algorithm for an NP-hard problem might behave as a concave function of the algorithm's structural complexity we conducted computational experiments [3]. The results raise the possibility of an optimality condition of complex systems: if the structural complexity of a system is in a certain relationship with the structural complexity of a problem, then the complex system shows the optimal performance for the problem. The optimality condition presents the structural complexity of a system as a key to its optimization. From its perspective the optimization of a system could be all about the control of the structural complexity of the system to make it consistent with the structural complexity of the problem. Importantly, the experiments indicate that the performance of a complex system may behave as a concave function of the structural complexity. Therefore, once the structural complexity could be controlled as a single entity, the optimization of a complex system would be potentially reduced to a one-dimensional concave optimization irrespective of the number of variables involved its description. This might open a way to efficient management of complex systems.

References:
[1] V. Korotkikh, A Mathematical Structure for Emergent Computation, Kluwer Academic Publishers, Dordrecht/Boston/London, 1999.
[2] V. Korotkikh and G. Korotkikh, Description of Complex Systems in terms of Self-Organization Processes of Prime Integer Relation, in Complexus Mundi: Emergent Patterns in Nature, M. M. Novak (ed.), World Scientific, New Jersey/London, 2006, pp. 63-72, arXiv:nlin/0509008; V. Korotkikh and G. Korotkikh, On an Irreducible Theory of Complex Systems, InterJournal of Complex Systems, 2006, 1751, arXiv:nlin/0606023.
[3] V. Korotkikh, G. Korotkikh and Darryl Bond, On Optimality Condition of Complex Systems: Computational Evidence, arXiv.cs/0504092; V. Korotkikh and G. Korotkikh, "On Principles in Engineering of Distributed Computing Systems", Soft Computing Journal, vol. 2, No. 2, 2008, pp. 201-206.
Sponsor of Seminar:
Ali Pinar
Scientific Computing

Contact Esmond G. Ng EGNg@lbl.gov