next up previous contents
Next: Appendix B: STL Iterator Analysis Up: 4 Applied Concepts Previous: 10. Summary and Outlook


Appendix A: Common Mathematical Terms

Basic mathematical terms are reviewed. The readers' familiarity with sets and subsets [2] is required in the following. All sets which contain only one element (singleton) can be used to describe a vertex.

Definition 44 (Relation)   A relation $ R$ between sets $ {\ensuremath{A}}$ and $ {\ensuremath{B}}$ is a collection of ordered pairs $ (a,b)$ such that $ a \in {\ensuremath{A}}$ and $ b \in
{\ensuremath{B}}$ , if $ (a,b) \in {\ensuremath{R}}$ .

Figure: A relation $ R$ of a set $ A$ and a set $ B$ .
\begin{figure}\begin{center}
\small\psfrag{A} [c]{{\ensuremath{A}}}\psfrag{B...
...e=figures/relation_function.eps, width=0.35\textwidth}\end{center}\end{figure}

Definition 45 (Function)   A function or mapping $ f$ is a rule that assigns to each element $ a \in {\ensuremath{A}}$ exactly one element $ b \in
{\ensuremath{B}}$ . So $ f$ maps $ a$ into $ b$ . This is denoted by $ {\ensuremath{f}}(a) = b$ .

A permutation of a finite set is usually given by its action on the elements of the set. An example is given by the basic set $ \{1,2,3,4,5
\}$ with a transformation into $ \{ 5,4,3,2,1 \}$ where the notation states that the permutation maps $ 1 \rightarrow 5$ , $ 2 \rightarrow 4$ and so on. Thereby all permutations of a finite set can be placed into two sets.

Definition 46 (Parity)   A permutation of a finite set can be expressed as either an even or an odd number of transpositions, but not both. In the former case, the permutation is called even, in the latter it is odd.

Definition 47 (Image)   Let $ A$ and $ B$ be sets, $ f$ be the function $ {\ensuremath{f}} : {\ensuremath{A}} \rightarrow {\ensuremath{B}}$ , and $ a \in {\ensuremath{A}}$ . Then the image of $ a$ under $ f$ , denoted by $ {\ensuremath{\textnormal{im} \; {{\ensuremath{f}}}}}$ , is the unique member $ b \in
{\ensuremath{B}}$ that $ f$ associates with $ a$ .

$\displaystyle {\ensuremath{f}}({\ensuremath{A}}) = \{b = {\ensuremath{f}}(a)\vert \quad a \in {\ensuremath{A}}\}$ (11.1)

Figure: The image of $ a$ under $ f$ .
\begin{figure}\begin{center}
\small\psfrag{A} [c]{{\ensuremath{A}}}\psfrag{B...
...gure=figures/relation_image.eps, width=0.35\textwidth}\end{center}\end{figure}

Definition 48 (Composite Function)   If $ f$ and $ g$ are functions with $ {\ensuremath{f}} : {\ensuremath{A}} \rightarrow {\ensuremath{B}}$ and $ {\ensuremath{g}}: {\ensuremath{B}}
\rightarrow {\ensuremath{C}}$ , then there is a natural function mapping $ {\ensuremath{A}}$ into $ {\ensuremath{C}}$ , the composite function, consisting of $ {\ensuremath{f}}$ followed by $ {\ensuremath{g}}$ . It can be written $ {\ensuremath{g}}({\ensuremath{f}}(a)) = c$ the composition of functions is denoted by $ {\ensuremath{g}} \circ {\ensuremath{f}}$ .

Definition 49 (Preimage)   The preimage (fiber, inverse image) of a set $ {\ensuremath{B}} \subseteq {\ensuremath{Y}}$ under $ {\ensuremath{f}}$ is the subset of $ {\ensuremath{X}}$ defined by

$\displaystyle {\ensuremath{f}}^{-1}({\ensuremath{B}}) = \{x \in {\ensuremath{X}} \vert {\ensuremath{f}}(x) \in {\ensuremath{B}}\}$ (11.2)

The preimage of a singleton, $ {\ensuremath{f}}^{-1}(y)$ , is a fiber or a level set. A fiber can also be the empty set $ \emptyset$ . The union set of all fibers of a function is called the total space, E.

Definition 50 (Group)   A group $ (G,*)$ is a set $ G$ with a binary operation $ *: G \times G \rightarrow G$ , such that the following axioms are satisfied:

Definition 51 (Abelian)   A group $ G$ is Abelian, if its binary operation $ *$ is commutative.

Definition 52 (Subgroup)   A subset $ H \subseteq G$ of a group $ (G,*)$ is a subgroup of $ G$ if $ H$ is a group and closed under the operation $ *$ . The subgroup consists of the identity element of $ G$ , whereas $ \{ e \}$ is the trivial subgroup of $ G$ . All other subgroups are nontrivial.

Definition 53 (Injective)   A mapping $ f: A \rightarrow B$ is called injective if there is at most one value $ b = f(a) \in B$ for each element $ a \in D$ . This means that every preimage in $ B$ has an image in $ A$ but there may be elements in $ A$ which are not obtained as images.

Definition 54 (Surjective)   A mapping $ f: A \rightarrow B$ is called surjective if $ b=f(a)$ has at least one solution $ b \in B$ for every $ a \in A$ . Several identical images in $ A$ may have different preimages in $ B$ .

Definition 55 (Bijective)   A mapping $ f: A \rightarrow B$ that is both injective and surjective is called bijective. It maps every preimage from $ B$ to a distinct image in $ A$ . There are no elements in $ A$ that cannot be obtained as images.

Definition 56 (Vector Space)   A vector space $ \mathcal{V}$ over a field $ \mathbb{F}$ is a set associated with two binary operations. The elements of $ \mathcal{V}$ are called vectors, while the elements of $ \mathbb{F}$ are called scalars. The binary operations are addition

$\displaystyle +: {\ensuremath{\mathcal{V}}} \times {\ensuremath{\mathcal{V}}} \rightarrow {\ensuremath{\mathcal{V}}}$ (11.3)

which is commutative as well as associative and which possesses a neutral as well as an inverse element, and scalar multiplication

$\displaystyle \cdot: {\ensuremath{\mathbb{F}}} \times {\ensuremath{\mathcal{V}}} \rightarrow {\ensuremath{\mathcal{V}}}$ (11.4)

which is distributive with addition. $ \mathcal{V}$ is closed under its two binary operations.

Definition 57 (Linear Mapping)   A mapping $ f: {\ensuremath{\mathcal{U}}} \rightarrow {\ensuremath{\mathcal{V}}}$ is called linear, if the following relation holds

$\displaystyle f (\lambda \; u + \mu \; v)$ $\displaystyle = \lambda \; f(u) + \mu \; f(v)$ (11.5)

A mapping

$\displaystyle g : L \times M \rightarrow N$ (11.6)

that is linear in both of its arguments, as in the following relations

$\displaystyle \varphi(\lambda \; u + \mu \; v$ $\displaystyle , w)$ $\displaystyle = \lambda \; \varphi(u, w) + \mu \; \varphi(v, w)$ (11.7)
$\displaystyle \varphi(u$ $\displaystyle , \lambda \; w + \mu \; x)$ $\displaystyle = \lambda \; \varphi(u, w) + \mu \; \varphi(u, x)$ (11.8)

is called bilinear.

The extension of this notion to more than two arguments is called a multi-linear mapping.

Definition 58 (Homomorphism)   A map $ {\ensuremath{f}}$ of a group $ G$ into a group $ G'$ is a homomorphism if $ {\ensuremath{f}}(ab) = {\ensuremath{f}}(a){\ensuremath{f}}(b), 
\forall a,b \in G$ . For any groups $ G$ and $ G'$ , there is always at least one homomorphism $ {\ensuremath{f}}: G \rightarrow G'$ , namely the trivial homomorphism defined by $ {\ensuremath{f}}(g) = e',  \forall g
\in G$ , where $ e'$ is the identity element in $ G'$ .

Definition 59 (Kernel)   Let $ {\ensuremath{f}}: G \rightarrow G'$ be a homomorphism. The subgroup $ {\ensuremath{f}}^{-1}(\{e'\}) \subseteq G$ , consisting of all elements of $ G$ mapped by $ {\ensuremath{f}}$ into the identity $ e'$ of $ G'$ , is the kernel of $ {\ensuremath{f}}$ , denoted by $ {\ensuremath{\textnormal{ker} \; {{\ensuremath{f}}}}}$ .

Figure: The kernel of $ f$ .
\begin{figure}\begin{center}
\small\psfrag{G} [c]{G}\psfrag{G'} [c]{G'}\ps...
...gure=figures/relation_kernel.eps, width=0.5\textwidth}\end{center}\end{figure}


next up previous contents
Next: 12. STL Iterator Analysis Up: 4 Applied Concepts Previous: 10. Summary and Outlook

R. Heinzl: Concepts for Scientific Computing