Functional decomposition

related topics
{math, number, function}
{theory, work, human}
{system, computer, user}
{@card@, make, design}
{area, part, region}

Functional decomposition refers broadly to the process of resolving a functional relationship into its constituent parts in such a way that the original function can be reconstructed (i.e., recomposed) from those parts by function composition. In general, this process of decomposition is undertaken either for the purpose of gaining insight into the identity of the constituent components (which may reflect individual physical processes of interest, for example), or for the purpose of obtaining a compressed representation of the global function, a task which is feasible only when the constituent processes possess a certain level of modularity (i.e., independence or non-interaction).

Contents

Basic mathematical definition

For a multivariate function y = f(x_1,x_2,\dots,x_n), functional decomposition generally refers to a process of identifying a set of functions \{g_1, g_2, \dots g_m\} such that

where φ is some other function. Thus, we would say that the function f is decomposed into functions \{g_1, g_2, \dots g_m\}. This process is intrinsically hierarchical in the sense that we can (and often do) seek to further decompose the functions gi into a collection of constituent functions \{h_1, h_2, \dots h_p\} such that

where γ is some other function. Decompositions of this kind are interesting and important for a wide variety of reasons. In general, functional decompositions are worthwhile when there is a certain "sparseness" in the dependency structure; that is, when constituent functions are found to depend on approximately disjoint sets of variables. Thus, for example, if we can obtain a decomposition of x_1 = f(x_2,x_3,\dots,x_6) into a hierarchical composition of functions {g1,g2,g3} such that x1 = g1(x2), x2 = g2(x3,x4,x5), x5 = g3(x6), as shown in the figure at right, this would probably be considered a highly valuable decomposition.

Full article ▸

related documents
Complexity
Abductive reasoning
Planner (programming language)
Theorem
Relation (mathematics)
John von Neumann
Universal algebra
Probability
Infinite monkey theorem
Number theory
Arrow's impossibility theorem
Reinforcement learning
Hilbert's second problem
Graph theory
Universal quantification
Prototype-based programming
Optimality theory
Optimization (mathematics)
Henri Lebesgue
Polish notation
Supervised learning
Tensor
Sheffer stroke
Integer (computer science)
Ordered pair
Partially ordered set
NP (complexity)
Normal space
Greatest common divisor
Net (mathematics)