On time and space decomposition of complex structures

ABSTRACT

Models of large and complex systems can often be reduced to smaller sub-models, for easier analysis, by a process known as decomposition. Certain criteria for successful decompositions can be established.

REFERENCES

• 1: Albin, P.S., and Gottinger, H.W. Structure and complexity in economic and social systems. Math. Sot. Sci. 5 (1963), 253-268.
• 2: Alexander, C.W.J. Notes on the synthesis of form. Harvard Univ. Press, Cambridge, Mass., 1964.
• 3: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 4: Bodewig. E. Matrix Calculus. North-Holland Publishing Company, Amsterdam, The Netherlands, 1956.
• 5: Chandy. K.M. Approximate analysis of general queueing networks. IBM\. of Res. Dev. 19. 1 (Jan, 1975), 1, 43-49.
• 6: Chandy. K.M., Herzog, U., and Woo, L. Parametric analysis of queueing networks. JBMJ Res. Dev. 19, 1 (Jan. 19751, 1, 36-42.
• 7: P. J. Courtois, Decomposability, instabilities, and saturation in multiprogramming systems, Communications of the ACM, v.18 n.7, p.371-377, July 1975 [doi>10.1145/360881.360887]
• 8: Courtois, P.J. Decomposability, Queue& and Computer Applications. Academic Press, New York, 1977.
• 9: Courtois, P.J. Error Minimization in Decomposable Stochastic Systems. Vol. 1, Applied Probability-Computer Science: The Interface. Birkhauser, Boston, Cambridge, Mass., 1982, pp. 189-210.
• 10: Courtois. P.J., and Semal, P. Block decomposition and iteration in stochastic matrices. Philips \. Res. 39, 4-5 (Nov. 1964), 178-194.
• 11: P.-J. Courtois , P Semal, Bounds for the Positive Eigenvectors of Nonnegative Matrices and for their Approximations by Decomposition, Journal of the ACM (JACM), v.31 n.4, p.804-825, Oct. 1984 [doi>10.1145/1634.1637]
• 12: Courtois, P.J., and Semal. P. On polyhedra of perron-frobenius eigenvectors. Linear Algebra Appl. 65 (Feb. 1985). 157-170.
• 13: Deneubourg, J.L. Application de l'ordre par fluctuation a la description de certaines &apes de la construction du nid cbez les termites. Insectes Sociaux. J Inf. pour I'etude des arfhropodes sociauw 24, 2 (1977), 117-130.
• 14: Denning, P.J. Thrashing: Its causes and prevention. In Proceedings of fhe AFIPS Fall Joint Cornpurer Conference (San Francisco, Calif., Dec. 9-11). AFIPS Press, Arlington, Va., 1968. pp. 915-922.
• 15: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 16: Gras% P.P. La reconstruction du nid et le travail collectif chez les termites superieurs. J. Psychol. P&ho/. Gen. (1959), 370-396.
• 17: Kemeny, J.G., and Snell. J.L. Finite Markov Chains. Van Nostrand Reinhold Company, New York, 1960.
• 18: Kleinrock, L.. and Lam, S. Packet switching in a multiaccess broadcast channel performance evaluation. IEEE Trans. Commun. 23, 4 (Apr. 1975), 410-423.
• 19: Kuehn, P.J. Approximate analysis of general queueing networks by decomposition. IEEE Trans. Commun. 27, 1 (Jan. 1979). 113-126.
• 20: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 21: Phillips. R.G., and Kokotovic, P.V. A singular perturbation approach to modeling and control of Markov chains. IEEE Trans. AuL Cont. AC-26,5 (Oct. 1981). 1087-1094.
• 22: Prigogine, I., and Stengers. I. La Nouvelle Alliance. Gallimard, Paris, 1983.
• 23: Rolf Schassberger, An Aggregation Principle for Computing Invariant Probability Vectors for Semi-Markovian Models, Proceedings of the International Workshop on Computer Performance and Reliability, p.259-273, September 26-30, 1983
• 24: Herbert A. Simon, The sciences of the artificial (3rd ed.), MIT Press, Cambridge, MA, 1996
• 25: Simon, H.A., and Ando, A. Aggregation of variables in dynamic systems. Economefrica 29 (1961), 111-138.
• 26: Jan A. Spriet , G. C. Vansteenkiste, Computer-Aided Modelling and Simulation, Academic Press, Inc., Orlando, FL, 1982
• 27: G. W. Stewart, Computable Error Bounds for Aggregated Markov Chains, Journal of the ACM (JACM), v.30 n.2, p.271-285, April 1983 [doi>10.1145/322374.322377]
• 28: Theil, H. Linear aggregation in input-output analysis. Economefrica. 25 (1957), 111-122.
• 29: Kishor S. Trivedi, Reliability Evaluation for Fault-Tolerant Systems, Proceedings of the International Workshop on Computer Performance and Reliability, p.403-416, September 26-30, 1983
• 30: Hendrik Vantilborgh, Aggregation with an error of O(&egr;2), Journal of the ACM (JACM), v.32 n.1, p.162-190, Jan. 1985 [doi>10.1145/2455.214107]
• 31: Vantilborgh, H. The error of aggregation. A contribution to the theory of decomposable systems and applications. Doctoral thesis, Univ. Cath. Louvain. 1981.
• 32: Wilson, K.G. Problems in physics with many scales of length. Sci. Am. 241, 2 (Aug. 1979). 140-157.
• 33: Wilson, K.G. Renormalization group methods. Adv. Math. 16 (1975). 170-166.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Design studies

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: General systems theory

General Terms:
Design, Performance, Theory