## Bandwidth, Profile and Frontwidth of Matrix

When we discretize the partial differential equations using the Finite Volume Method (FVM), we get sets of linear algebraic equations with large sparse coefficient matrices that are solved using iterative or direct methods. There is renumberMesh utility in OpenFOAM that is used to reduce the bandwidth of the coefficient matrices by renumbering the cell label list.

The bandwidth is not a special term in OpenFOAM but it is a general concept in the field of solving linear systems of equations. In this blog post, I will try to give a description of it and other important terms such as profile and frontwidth.

Keywords: bandwidth, profile, frontwidth, renumberMesh

 Definitions of bandwidth, profile and frontwidth

The definitions of these terms are clearly described in [1]. Let $$A$$ be an $$N$$ by $$N$$ matrix with symmetric zero-nonzero structure, i.e. , $$a_{ij} \neq 0$$ if and only if $$a_{ji} \neq 0$$.

The $$i$$-th bandwidth of $$A$$ is:

\begin{align}
\beta_i(A) = i \; – \; {\rm min}\{ j \; | \; a_{ij} \neq 0\}. \tag{1} \label{eq:ithBandwidth}
\end{align}

The bandwidth of $$A$$ is defined by

\begin{align}
\beta = \beta(A) &= {\rm max} \{ \beta_i(A) \; | \; 1 \leq i \leq N\} \\
&= {\rm max} \{ |i-j| \; | \; a_{ij} \neq 0 \}. \tag{2} \label{eq:Bandwidth}
\end{align}

The quantity $$|Env(A)|$$ is called the profile or the envelope size of $$A$$, and is defined by:

\begin{align}
|Env(A)| = \sum_{i=1}^{N} \beta_i(A). \tag{4} \label{eq:Profile}
\end{align}

Another quantity called frontwidth is defined by the number of rows of the envelope of $$A$$ which intersect column $$i$$.

\begin{align}
\omega_i(A) = \{ k \; | \; k > i \; and \; \exists l \leq i \; s.t. \; a_{kl} \neq 0 \} \tag{5} \label{eq:frontwidth}
\end{align}

To estimate factorization time, a quantity called root mean square frontwidth is introduced by [2]. This quantity is given by:

\begin{align}
f = \sqrt{\frac{1}{N} \left( \sum_{i=1}^{N} \omega_i^2 \right)}. \tag{8} \label{eq:rmsFrontwidth}
\end{align}

 Output of renumberMesh utility

When the renumberMesh utility is executed, the following data is reported to the screen.

Here, the band, profile and rms frontwidth correspond to \eqref{eq:Bandwidth}, \eqref{eq:Profile} and \eqref{eq:rmsFrontwidth}, respectively. We can confirm that they all decreased after renumbering the cell label using the Cuthill-McKee (CM) algorithm. The distributions of cell labels are visually compared between before and after reordering operations in Figure 1.

 Source code of renumberMesh utility

The getBand function is called from the main function. The variables band, profile and rmsFrontwidth represent \eqref{eq:Bandwidth}, \eqref{eq:Profile} and \eqref{eq:rmsFrontwidth}, respectively.

 References

## Structure of src Directory in OpenFOAM part1

OpenFOAM の各種ライブラリのソースコードは，src ディレクトリ に設置されています．例えば，2015年のオープン CAE シンポジウムの講習会で取り上げた境界条件のライブラリ libfiniteVolume のソースコードは，src/finiteVolume/ 以下に設置されています．第1回目の今回は，以下の4つのディレクトリを取り上げます．

 fvOptions

fvOptions で使用可能なタイプのリストを，こちらのページにまとめています．

 renumber

セル番号の付け替え（Ordering）を行うための手法（Cuthill-McKeeSloan アルゴリズムなど）のソースコードが設置されています．renumberMesh ユーティリティは，このライブラリ librenumberMethods を使用して，セル番号の付け替えにより係数行列のバンド幅を小さくすることで，連立方程式の反復解法の計算時間の短縮化を図ります．デフォルトの手法である Cuthill-McKee 以外の手法を使用するためには，設定ファイルを用意し，実行時に -dict オプションでそのパスを指定します．

• CuthillMcKee: デフォルトの手法
• Sloan: boost C++ ライブラリの Sloan アルゴリズムを使用
• manual
• random
• spring
• structured

 dynamicFvMesh

OpenFOAM では，メッシュの移動変形機能を Dynamic Mesh という名前で呼んでいます．並進・回転などの剛体運動，１次元方向の伸び縮み運動など，トポロジー変化を伴わないメッシュの移動変形のライブラリのソースコードが設置されています．次のスライドで詳しく説明しています．

[slideshare id=31811977&doc=openfoamdynamicmesh20140302-140302022414-phpapp01&w=500]

 topoChangerFvMesh

トポロジー変化を伴うメッシュの移動変形のライブラリのソースコードが設置されています．

その2に続きます．